You are not logged in. Please login at www.codechef.com to post your questions!

×

ZCO Dynamic Programming problems

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

asked 02 Dec '14, 23:00

swagatochatt's gravatar image

0★swagatochatt
1536
accept rate: 0%

edited 03 Dec '14, 16:27

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.

(03 Dec '14, 09:41) sampritipanda5★

I was also stuck there.....

link

answered 19 Nov '16, 20:44

lud1161's gravatar image

2★lud1161
1418
accept rate: 58%

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

link

answered 03 Dec '14, 19:03

rishikeshwar's gravatar image

4★rishikeshwar
1112
accept rate: 0%

edited 03 Dec '14, 19:03

Seconded!!

(03 Dec '14, 19:30) sandy9992★

So can u ? sandy999 ?

(03 Dec '14, 19:35) rishikeshwar4★

Does your code for IPL work properly?

link

answered 03 Dec '14, 01:45

aaha97's gravatar image

3★aaha97
-31
accept rate: 0%

Yes it does

(03 Dec '14, 16:55) swagatochatt0★

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

(03 Dec '14, 21:10) aaha973★

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

(04 Dec '14, 22:45) swagatochatt0★

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

link

answered 03 Dec '14, 12:20

Organic-Shilling's gravatar image

0★Organic-Shilling
93118
accept rate: 11%

edited 03 Dec '14, 12:20

Can you please tell the sub-problem formula?

(03 Dec '14, 16:29) swagatochatt0★

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.

(03 Dec '14, 18:05) Organic-Shilling0★

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.

link

answered 03 Dec '14, 16:53

swagatochatt's gravatar image

0★swagatochatt
1536
accept rate: 0%

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

link

answered 04 Dec '14, 11:50

aaha97's gravatar image

3★aaha97
-31
accept rate: 0%

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

answered 04 Dec '14, 22:58

swagatochatt's gravatar image

0★swagatochatt
1536
accept rate: 0%

edited 05 Dec '14, 10:03

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

(04 Dec '14, 23:09) sandy9992★

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

(04 Dec '14, 23:13) superty3★

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

(05 Dec '14, 10:21) swagatochatt0★

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

(05 Dec '14, 21:10) sandy9992★

and what would the function best contain ??

link

answered 05 Dec '14, 00:58

rishikeshwar's gravatar image

4★rishikeshwar
1112
accept rate: 0%

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.

link

answered 05 Dec '14, 16:54

aaha97's gravatar image

3★aaha97
-31
accept rate: 0%

Its wrong the memo table must be 2d

(05 Dec '14, 17:43) swagatochatt0★

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

(05 Dec '14, 17:56) superty3★
(05 Dec '14, 18:35) superty3★
(05 Dec '14, 19:04) swagatochatt0★

its IPL... i thought if i could get this then SUPW was peice of cake... :/

(05 Dec '14, 20:34) aaha973★
1

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

(05 Dec '14, 21:11) swagatochatt0★
1

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

(05 Dec '14, 21:30) superty3★
showing 5 of 8 show all

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

link

answered 30 Mar '16, 19:37

stblackout's gravatar image

4★stblackout
664
accept rate: 16%

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:]))
link

answered 30 Oct '16, 02:12

mathecodician's gravatar image

6★mathecodician
2.6k1932
accept rate: 7%

> /*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;
}
link

answered 05 Nov '16, 10:13

varunchhangani's gravatar image

1★varunchhangani
1
accept rate: 0%

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

answered 06 Nov '16, 00:06

mz54's gravatar image

2★mz54
15613
accept rate: 30%

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.

link

answered 19 Nov '16, 11:56

alphatron99's gravatar image

4★alphatron99
261
accept rate: 33%

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.

link

answered 19 Nov '16, 11:59

alphatron99's gravatar image

4★alphatron99
261
accept rate: 33%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,167
×424
×242
×177
×37

question asked: 02 Dec '14, 23:00

question was seen: 7,690 times

last updated: 19 Nov '16, 20:44