Hello, It can seem strange to ask this question to some of you but I am actually not getting convinced or not something very obvious is intuitive to me. So below is the problem :

The question: Why in knapsack we always chose prefix instead of something like range (l,j). Before you get angry please read my full question.

Like how we are so sure that in taking the prefix of the items we are going to consider all the cases possible that are also lying same if we consider range of the items.

Atcoder example problem

Like in this problem we have to count the different pairs of permutations whose similarity is equal to K .

In the editorial, DP is defined by considering the prefix instead of something like range (I,J). And this is not intuitive to me ?

So in a way the question can be rephrased as How we have to decide in DP when to take prefix and when to take range of the array with the thought in mind that no cases are left out as in case of the above problem example I have given??

If any one can reply it will be of great help to me as this part is not very intuitive/convincing to me.

Hello,there I know it's a irrelevant question to some of you .But, I want to ask as I have spent a long time and have a feeling that this DP approach could be correct(I think so) . But , yeah it could also be wrong and I want to ask why it can be wrong? So, yeah here it goes -->

Let dp(i,pos) = Min no of days to get money i and in getting money i optimally you reached the position pos.

And here will be the transitions according to me

dp(i,pos)--> dp(i + a[pos],pos) OR --> dp(i-b[pos],pos+1)

WHERE a and b are the arrays given in the question and the answer will be the DP[c][x] ( c is the total cost of new computer and x lies in range from position 1 to N in the array and we will take minimum dp of that.)

This is what I have thought of this question after spending some time . And I think time complexity will be in N^2 but I am interested whether this approach will lead to right answer. If not I really want to know the reason why it will fail?

I know some people can think it is rude to write a whole blog on it you can just ask in the comments but this round happened months ago so I will not get answer quickly.So I asked here.

Thank you everyone

Hello, Hi there , if anyone know the below problem solution please tell. I thought this problem using binary search , greedy, but no use. So finally i think it will be possible by DP. (but not getting possible states and transitions). If anyone helps, that would be very nice of you. So the problem goes like this -->

A bus stops at n bus stops, each bus stop having a[i] people. The bus needs to take in all the people on the bus. People from 1 bus stop get down before the next bus stop arrives. They use a resizing tech which allows the bus to be resized to whatever capacity they want. This action can be done only b times at max. The uselessness of the bus is the summation of a total number of unoccupied seats across n stops. Find the minimum uselessness the bus can achieve if the resizing tech is used optimally.

1<=a[i]<=10^6, 1<=b<=n<=400

Ex 1: a = [10 20] b = 0 Ans:10 Explanation – the resizing tech cannot be applied. hence the capacity of the bus is 20 initially. in the first stop, 20-10 seats were unused. in the second stop 20 – 20 seats are unused. Total unused seats = 10

Ex 2: a = [10 20 30] b = 1 Ans: 10 Explanation – the resizing tech can be applied only once. The capacity of the bus is 10 initially. In the first stop 10-10 seats unused = 0. in the second stop, the tech is used to resize to 30. 30 – 20 seats unused.

In the third stop, 30-30 seats unused

Total unused seats = 10.

If anyone know how to do it, please explain .

THANK YOU.

Hello all, this is my first ever blog on codeforces . If i make some mistakes, please forgive me .

Actually i am thinking on the 1485A - Add and Divide and its tutorial is using greedy approach.

But i have read that all optimisation problems can be solved using DP through its optimal substructure and overlapping property .

I am thinking this problem for quite a long time using DP .

So, please tell me how we will define the state for DP and transitions in DP for this problem as they are the most creative part for me .

So how you actually think to make it all easier ? (to differentiate between DP and greedy ) and when to use which technique ?

And , please tell how you decide which problem to solve using greedy and which using DP as both are working on optimisation problems . ------------------

So how you actually differentiate so fast in contest ?

Your answers and clarifications will be very helpful to me .

Thank you all.