Can anyone please help me with these ZCO problems concerning Dynamic Programming. The first Problem I want to speak of is ROUNDTABLE(The Problem): This problem is seems analogous to Choosing Chocolates(Statement) for which I used the following code:
Now if I change the The second problem is SUPW(Statement): The problem is similar to IPL(Statement) for which I used the subproblem formula:
Now too, if I change the asked 02 Dec '14, 23:00

Your Solution for IPL looks cool .. but i am not able to understand it clearly can u give me a detailed explanation of your program and your logic and if possible a simple pseudo code ... thanks answered 03 Dec '14, 19:03

The reason your round tables is not working is because the table is cyclic so you'll have to change your code. answered 03 Dec '14, 12:20
Can you please tell the subproblem formula?
(03 Dec '14, 16:29)
Even I don't know. I have been trying to solve it but my attempts have been unsuccessful. http://pastebin.com/mvgHACH5 here is what I have come up with. This is failing on a few test cases.
(03 Dec '14, 18:05)

I have solved SUPW: The trick is to subtract not add. I have made the following changes:
How foolish of me, I did not realize the maximum work he could do is the sum of all Work Solution:
Thanks to sampritipanda and OrganicShilling for telling me to make the subproblem for a cyclic table(for the Problem RoundTable) I am trying it. Any help regarding this is Welcome. answered 03 Dec '14, 16:53

http://code.hackerearth.com/7c93d9C here is my code. can you help me identify what have i done wrong there? i got first 3 outputs correct but others wrong. maybe provide a test case where it fails. please i am really confused... answered 04 Dec '14, 11:50

Okay.I hope you understand this is DP.The Pseudocode(for IPL):
answered 04 Dec '14, 22:58
What should we loop from N1 to 0? Shouldn't we loop from 0 to N1 instead?
(04 Dec '14, 23:09)
You cannot find the value for i without first knowing the values for i + 1;
(04 Dec '14, 23:13)
See that at the base case I am initializing Best[N,0] to Fees[N], and as @superty pointed out the the new values of Best[i,] cannot be found without knowing the value of Best[i+1,].Think it like this way,we are writing an unmemoized code where Best(0,0) would return the solution.The recursive procedure would continue until it hits the Base Case and then backtrack the solution from the Best(N,...).So the base case is a necessity and since we have set the Base case with regards to N, we have to loop from N1 to 0. You can try to loop from 1 to N by setting Best[0,1]=Fees[1].
(05 Dec '14, 10:21)
Thanks a lot @superty and @swagatochatt! Sorry, this kind of thinking never occurred to me as I hadn't got the hang of recursion, I spent over hours poring over this simple pseudocode, finally understood, that was one amazing logic! I got it accepted now. Thanks again! :)
(05 Dec '14, 21:10)

that is my function to be iterated. x[] is for memoization and a[] has the input array. tell me if i have done anything wrong there. answered 05 Dec '14, 16:54
Its wrong the memo table must be 2d
(05 Dec '14, 17:43)
Which problem is this? In any case I have solved both with just a 1d memo table so it is not necessary
(05 Dec '14, 17:56)
(05 Dec '14, 18:35)
@superty can you help me in solving Little Red Riding Hood here ( http://discuss.codechef.com/questions/57313/zcoproblemlittleredridinghood ) and Save Spaceman Spiff here (http://discuss.codechef.com/questions/30653/savespacemenspiff )
(05 Dec '14, 19:04)
its IPL... i thought if i could get this then SUPW was peice of cake... :/
(05 Dec '14, 20:34)
@superty can you please answer this ( http://discuss.codechef.com/questions/57419/zcopracticeserverinoi2013problemsequenceland )
(05 Dec '14, 20:56)
1
It's just practice, there is really not much to explain... Well upon seeing the problem I realized that it's not really much different from other problems like SUPW and all, just that the table is circular. So now we have to see how to deal with the circular part. What I did was I considered two cases for the pair of adjacent tables 1 and N, taking 1 or taking N. Then for each case do the DP and find the minimum cost of the cases
(05 Dec '14, 21:30)
showing 5 of 8
show all

for round table, I took 2 cases case 1: u make dish for 1st knight => min(dish for last, NO dish for last) = a (let's say) case 2: u don't make dish for 1st knight => dish for last = b(let's say) ans will be min(a, b); and formula for dp can be dp[i][0] = dp[i1][1]; dp[i][1] = min(dp[i2][1] + a[i], dp[i1][1]+a[i]); answered 30 Mar '16, 19:37

Can someone tell me why this python code of mine is showing runtime on test case 2. It is giving correct on all the other test cases. I can't ask it myself as I don't have enough karma.
answered 30 Oct '16, 02:12

answered 05 Nov '16, 10:13

Code for SUPW
Well I am getting a wrong answer for the break up problem though it is theoretically fully correct,
answered 06 Nov '16, 00:06

In SUPW you could just use the IPL code to find the max work he can do if the instructions were to work at most 2 consecutive days and then subtract the answer from total working hours. This solutions works perfectly because it is actually maximising the work done on the days that he will skip. answered 19 Nov '16, 11:56

In SUPW you could just use the IPL code to find the max work he can do if the instructions were to work at most 2 consecutive days and then subtract the answer from total working hours. This solutions works perfectly because it is actually maximising the work done on the days that he will skip. answered 19 Nov '16, 11:59

In the problem of ROUNDTABLE, since the knights the sitting in a circle, the first and the last are adjacent to each other. So you need to take care of that.