Hello this is my first blog post, could you please help me with this problem? You are given a stack of N elements, you want to pop all the elements performing one of the three operations: Pop 1 element, Pop 2 elements, Pop half elements. Every operations has a cost in money, based on the number of elements in the stack. You are given 3 arrays, array U, D and M. The i-th element of the array is the cost (in money) of performing the operation when the stack has i+1 elements in it. Every operation has also a cost in energy: Pop 1 restores 1 energy, Pop 2 doesn't change your energy, Pop half costs 1 energy. You start with E energy, and can never go under 0 energy. Find the minimum cost in money you need to pop all the stack, while remaining with non-negative energy. Input limits: N <= E <= 1000000, Ui and Di and Mi <= 10^9, memory limit 1MiB, time limit 1s.
The 3 arrays are given in the form of 4 integers each, V0, A, B, C. Every element i-th of each array can be generated using the formula Vi = (Vi-1 *A + B)%C
For example the integers:
13 4 7 17
1 3 9 19
7 9 9 13
with N = 5 generate the arrays U = [ 13,8,5,0,13 ] D = [ 1,12,7,11,4 ] M = [ 7,7,7,7,7 ]
I tried to use dynamic programming to solve this problem. If the only operations possible were pop1 and pop2, i could keep only 2 rows of the dp table at a time, and it would be fine, but since there is the pop half operation, i need to remember N/2 states and it goes out of memory.
I am not sure how you do your dp, but did you notice that since N <= 1000000 < 220, and therefore, you will need at most 20 energy?
Yes, that's how i do my dp. I keep N/2 rows of 20 energy, and every i-th row modifies the state of the i-1 row, i-2 row and i/2 row.
can I have the source of the problem? but isnt reading the input itself already 12 MB?
You are given each array in the form of 4 integers V0, A, B, C, and you can generate each Vi as ( V(i-1) * A + B ) % C. For example the integers:
13 4 7 17
1 3 9 19
7 9 9 13
with N = 5 generate the arrays U = [ 13,8,5,0,13 ] D = [ 1,12,7,11,4 ] M = [ 7,7,7,7,7 ]
Generating the sequence bottom-up shouldn't be the issue while solving the problem.
dude.... this might be important information to solve the problem. Please do not change the problem when you ask a question, or you will be wasting ppl's time. Can you give the constraints on V(0), A,B and C as well?
they are all <= 10^9 there are no other constraints on them, just 4 integers.
Maybe you can do the following. Let's store log n pairs of rows. First pair for calculating dp[i], second for calculating dp[i / 2], third for dp[(i / 2) / 2] and so on. When you need to calculate dp[i], if your value of i / 2 didn't change, you can just use one of the rows of the second pair. But if it changed you need to calculate new row for the second pair, you look at value of (i / 2) / 2. If it didn't change, you just use stored value, else you are going to ((i / 2) / 2) / 2 and so on. Thus, you will need O(log n) rows. Complexity remains the same, because in total the first pair of rows will make n transitions to next state, the second n / 2, the third n / 4, etc. n + n / 2 + n / 4... = 2n.
It's Radewoosh's chef from finals of 24 Polish Olympiad in Informatics. You can refer to the official booklet :)
The correct solution is to maintain logN "machines of dynamic programming' instead of one. One costs you logN memory, so it's fine