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

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

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

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

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[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:]))
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[i];
	for(int i=0;i<n;i++)
	{
		i=axm(a,n,i);
		cnt+=a[i];
		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[i];
    }
    std::vector<int>bestTime(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 <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[i];
    }
    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[i][i] = true; // Every number is a pallindrome of itself
    }
    
    for(int i=0;i<n-1;i++){
        if(nums[i]==nums[i+1]){
            table[i][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…

1 Like
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. #include <iostream>using namespace std;int main(){ int n; cin >> n - Pastebin.com here is what I have come up with. This is failing on a few test cases.