ZCO Dynamic Programming problems

general
, , , ,
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.

1 Like
2

Does your code for IPL work properly?

3

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.

4

The reason your round tables is not working is because the table is cyclic so you’ll have to change your code.

5

Can you please tell the sub-problem formula?

6

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.

7

Yes it does

8

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.

9

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

1 Like
10

Seconded!!

11

So can u ? sandy999 ?

12

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??

13

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…

14

Yes it is because the solution would be stored in Best[0,0].

15

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]
16

What should we loop from N-1 to 0? Shouldn’t we loop from 0 to N-1 instead?

17

You cannot find the value for i without first knowing the values for i + 1;

18

and what would the function best contain ??

19

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].

20

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.