 # ZCO Dynamic Programming problems

#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*= max(sol[i-1],sol[i-2]+cost*), for all i such that 2<=i<=n
base case:
sol=0;
sol=cost;
``````

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.

#2

Does your code for IPL work properly?

#3

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

#4

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*,for all i from 1 to N)
Best[N,1] = sum(Work*,for all i from 1 to N)-Work[N]
Best[N,2] = sum(Work*,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.

#5

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

#6

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…

#7

Okay.I hope you understand this is DP.The Pseudocode(for IPL):

``````Initialize the Base Cases
Fees=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]``````

#8

and what would the function best contain ??

#9

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.

#10

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* = dp[i-1];
dp* = min(dp[i-2] + a*, dp[i-1]+a*);

#11

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,c,c]
for i in range(3,n):
cost.append(c* + min(cost[i-3:i]))
print(min(cost[n-3:]))
``````

#12
``````> /*SUPW*/
#include<iostream>
#include<stdio.h>
#include<stdlib.h>

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]<a[min])
min=j+i;
}
return min;
}
int main()
{
int n,*a,cnt=0;
cin>>n;
a=new int[n];
for(int i=0;i<n;i++)
cin>>a*;
for(int i=0;i<n;i++)
{
i=axm(a,n,i);
cnt+=a*;
if(i+2>=n)
break;
}
cout<<cnt;
return 0;
}``````

#13

Code for SUPW

``````#include <iostream>
#include <vector>
#include <algorithm>

int main(){
int n;
std::cin >> n;
std::vector<int>dutyTime(n);
for(int i=0;i<n;i++){
std::cin >> dutyTime*;
}
std::vector<int>bestTime(n);
bestTime = dutyTime;
bestTime = dutyTime;
bestTime = dutyTime;
for(int i=3;i< n;i++){
bestTime* = dutyTime*+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 <vector>
#include <iostream>

int main(){
int n;
std::cin >> n;
std::vector<int>nums(n);
for(int i=0;i<n;i++){
std::cin >> nums*;
}
std::vector<std::vector<bool> > table(n,std::vector<bool>(n,false)); // table to say whether the given sequence is pallindrome or not
int maxLength = 1;
for(int i=0;i<n;i++){
table** = true; // Every number is a pallindrome of itself
}

for(int i=0;i<n-1;i++){
if(nums*==nums[i+1]){
table*[i+1] = true; // same consecutive numbers are also pallindromes
maxLength = 2;
}
}

for(int i=3;i<=n;i++){
for(int j=0;j<n-i+1;j++){
int k = j+i-1;
if(table[j+1][k-1] && nums[j] == nums[k]){
table[j][k] = true;
if(i > maxLength){
maxLength = i;
}
}
}
}

std::cout << maxLength << std::endl;
return 0;
}``````

#14

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.

#15

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.

#16

I was also stuck there…

#17

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.

#18

Can you please tell the sub-problem formula?

#19

Yes it does

#20

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.