ZCO Dynamic Programming problems

general
, , , ,
21

Its wrong the memo table must be 2d

22

Which problem is this? In any case I have solved both with just a 1d memo table so it is not necessary

23

http://pastebin.com/9gaeQKrP

24

@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 )

25

its IPLā€¦ i thought if i could get this then SUPW was peice of cakeā€¦ :confused:

26

@superty can you please answer this ( http://discuss.codechef.com/questions/57419/zco-practice-server-inoi-2013-problem-sequenceland )

27

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! :slight_smile:

28

@superty can you tell me what thought process you undergo while solving DP?

1 Like
29

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

1 Like
30

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]);

31

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:]))
32 
> /*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;
}
33

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;
}
34

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.

35

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.

36

I was also stuck thereā€¦

1 Like