ZCO Dynamic Programming problems

dynamic-programming
ico
ioi
zco
zco2015

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


#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]=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*[0] = dp[i-1][1];
dp*[1] = min(dp[i-2][1] + a*, dp[i-1][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[0],c[1],c[2]]
    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[0] = dutyTime[0];
    bestTime[1] = dutyTime[1];
    bestTime[2] = dutyTime[2];
    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.