×

# ZCO Dynamic Programming problems

 1 1 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: sol[i]= max(sol[i-1],sol[i-2]+cost[i]), for all i such that 2<=i<=n base case: sol[0]=0; sol[1]=cost[1];  Now if I change the max() to min() it is not helping. Please Help. The second problem is SUPW(Statement): The problem is similar to IPL(Statement) for which I used the sub-problem formula: Best[j,0] means he does not play match j Best[j,1] means he plays match j, not j+1 Best[j,2] means he plays match j, j+1, not j+2 Best[j,0] = max(Best[j+1,0],Best[j+1,1],Best[j+1,2]) Consider Best[j,1] --- he plays match j and the consecutive sequence of mathces starting at j is of length 1, so he does not play j+1. But he does get this match fee. So: Best[j,1] = Fee[j] + Best[j+1,0] Best[j,2] = Fee[j] + Best[j+1,1] Base Cases: Best[N,0] = 0 Best[N,1] = Fee[N] Best[N,2] = 0  Now too, if I change the max() to min() it is not helping. Please Help. The contest is on 05.12.2014 I am in need of desperate help.Any ideas are welcome. asked 02 Dec '14, 23:00 15●3●6 accept rate: 0% 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. (03 Dec '14, 09:41)

 2 I was also stuck there..... answered 19 Nov '16, 20:44 2★lud1161 14●18 accept rate: 58%
 1 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 11●1●2 accept rate: 0% Seconded!! (03 Dec '14, 19:30) sandy9992★ So can u ? sandy999 ? (03 Dec '14, 19:35)
 0 Does your code for IPL work properly? answered 03 Dec '14, 01:45 3★aaha97 -3●1 accept rate: 0% Yes it does (03 Dec '14, 16:55) oh so u changed it. i have done same thing in my code. except i didn't use best[j,0] in comparison. is that even needed?? (03 Dec '14, 21:10) aaha973★ Yes it is because the solution would be stored in Best[0,0]. (04 Dec '14, 22:45)
 0 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 93●1●1●8 accept rate: 11% Can you please tell the sub-problem 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)
 0 I have solved SUPW: The trick is to subtract not add. I have made the following changes: Best[j,0] means he does not work on day j Best[j,1] means he does work on day j, not j+1 Best[j,2] means he does work on day j, j+1, not j+2 Now: Best[j,0] = min(Best[j+1,0],Best[j+1,1],Best[j+1,2]) Best[j,1] = Work[j] - Best[j+1,0] Best[j,2] = Work[j] - Best[j+1,1] Base Cases: Best[N,0] = sum(Work[i],for all i from 1 to N) Best[N,1] = sum(Work[i],for all i from 1 to N)-Work[N] Best[N,2] = sum(Work[i],for all i from 1 to N)  How foolish of me, I did not realize the maximum work he could do is the sum of all Work Solution: Best[0,0]  Thanks to sampritipanda and Organic-Shilling for telling me to make the sub-problem for a cyclic table(for the Problem RoundTable) I am trying it. Any help regarding this is Welcome. answered 03 Dec '14, 16:53 15●3●6 accept rate: 0%
 0 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 3★aaha97 -3●1 accept rate: 0%
 0 Okay.I hope you understand this is DP.The Pseudocode(for IPL): Initialize the Base Cases Fees[0]=0 Loop j from N-1 to 0 Best[j,0] = max(Best[j+1,0],Best[j+1,1],Best[j+1,2]) Best[j,1] = Fee[j] + Best[j+1,0] Best[j,2] = Fee[j] + Best[j+1,1] End of Loop Print Best[0,0]  answered 04 Dec '14, 22:58 15●3●6 accept rate: 0% What should we loop from N-1 to 0? Shouldn't we loop from 0 to N-1 instead? (04 Dec '14, 23:09) sandy9992★ You cannot find the value for i without first knowing the values for i + 1; (04 Dec '14, 23:13) superty3★ 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 N-1 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) sandy9992★
 0 and what would the function best contain ?? answered 05 Dec '14, 00:58 11●1●2 accept rate: 0%
 0 long long func(int k){ long long s1,s2; if(k>=N){ return 0; } if(x[k+2]!=-1){ s1=x[k+2]+a[k]; } else{ x[k+2]=func(k+2); s1=x[k+2]+a[k]; } if(x[k+3]!=-1){ s2=x[k+3]+a[k]+a[k+1]; } else{ x[k+3] = func(k+3); s2=x[k+3]+a[k]+a[k+1]; } return s1>s2?s1:s2; }  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 3★aaha97 -3●1 accept rate: 0% 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) superty3★ http://pastebin.com/9gaeQKrP (05 Dec '14, 18:35) superty3★ @superty can you help me in solving Little Red Riding Hood here ( http://discuss.codechef.com/questions/57313/zco-problem-little-red-riding-hood ) and Save Spaceman Spiff here (http://discuss.codechef.com/questions/30653/save-spacemen-spiff ) (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) aaha973★ @superty can you please answer this ( http://discuss.codechef.com/questions/57419/zco-practice-server-inoi-2013-problem-sequenceland ) (05 Dec '14, 20:56) 1 @superty can you tell me what thought process you undergo while solving DP? (05 Dec '14, 21:11) 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) superty3★ showing 5 of 8 show all
 0 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[i-1][1]; dp[i][1] = min(dp[i-2][1] + a[i], dp[i-1][1]+a[i]); answered 30 Mar '16, 19:37 66●4 accept rate: 16%
 0 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. n = int(input()) c = list(map(int,input().strip().split())) if n < 3: print(min(c)) else: cost = [c[0],c[1],c[2]] for i in range(3,n): cost.append(c[i] + min(cost[i-3:i])) print(min(cost[n-3:]))  answered 30 Oct '16, 02:12 2.6k●1●9●32 accept rate: 7%
 0 > /*SUPW*/ #include #include #include using namespace::std; int axm(int *a,int n,int i) { int min=i; for(int j=0;j<=2;j++) { if(a[j+i]>n; a=new int[n]; for(int i=0;i>a[i]; for(int i=0;i=n) break; } cout<
 0 Code for SUPW #include #include #include int main(){ int n; std::cin >> n; std::vectordutyTime(n); for(int i=0;i> dutyTime[i]; } std::vectorbestTime(n); bestTime[0] = dutyTime[0]; bestTime[1] = dutyTime[1]; bestTime[2] = dutyTime[2]; for(int i=3;i< n;i++){ bestTime[i] = dutyTime[i]+std::min(bestTime[i-1],std::min(bestTime[i-2],bestTime[i-3])); } std::cout << std::min(bestTime[n-1],std::min(bestTime[n-2],bestTime[n-3])) << std::endl; return 0; }  Well I am getting a wrong answer for the break up problem though it is theoretically fully correct, #include #include int main(){ int n; std::cin >> n; std::vectornums(n); for(int i=0;i> nums[i]; } std::vector > table(n,std::vector(n,false)); // table to say whether the given sequence is pallindrome or not int maxLength = 1; for(int i=0;i maxLength){ maxLength = i; } } } } std::cout << maxLength << std::endl; return 0; }  answered 06 Nov '16, 00:06 2★mz54 156●1●3 accept rate: 30%
 0 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 26●1 accept rate: 33%
 0 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 26●1 accept rate: 33%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,167
×424
×242
×177
×37

question asked: 02 Dec '14, 23:00

question was seen: 7,690 times

last updated: 19 Nov '16, 20:44