TADELIVE - Editorial

dynamic-programming
editorial
greedy
ltime19
simple

#41

Hey btw @betlista how can you edit an answer? Are you in admin panel or is this because of your Karmas?


#42

Your solution failed for last test case


#43

@rishabhprsd7: According to this - http://blog.codechef.com/2014/11/18/the-new-karma-system/ it’s because of karma…


#44

i edited that case because according to constraints 0 cannot be the tip value… but if your code was passing previous case then it will pass this too…!! also as @betlista mentioned your code fails on last case add by @betlista


#45

Because both can deliver just one, the max is when Andy deliver first one for 5 and Bob second one for 8. Bob cannot deliver both…


#46

Your code fails with

2 1 1
6 8
5 6

should be 13, your code returns 12 - http://ideone.com/CpHHDI


#47

Are there some good tutorials on state dp ?


#48

as both can deliver only one so there can be two combinations either (bob get 6 and andy get 6 which is equal to 12) or (andy get 5 and bob get 8 which is equal to 13), so 13 is the answer and not 12…!!


#49

For the DP solution should be this part

    BobOrders = i - j;
    if (BobOrders + 1 <= Y) {
        res = max(res, B* + dp(i + 1, j + 1));
    }
   
    BobOrders = i - j;
    if (BobOrders + 1 <= Y) {
        res = max(res, B* + dp(i + 1, j));
    }

#50

@betlista I know my code is failing for cases but what is logically incorrect with my code and the code in the editorial?
Also, when both A* and B* are same who do we assign to collect the tip?


#51

@betlista please don’t check with what I have submitted, i had better solution but couldn’t submit in time :-/


#52

@dev8546: Yes, corrected.


#53

Your code returns 18 for

3 2 1
7 4 9
7 2 3

correct answer is 20, I kind of do not like cmp function, but maybe I’m wrong…


#54

I think (but didn’t test it yet) that logical problem is in if(v->first<=0 && a<x) you want handle diff == 0 as last option…


#55

@betlista I guess that’s where the error might be. But, when diff==0 how do we decide who to assign the tip to Andy or Bob?


#56

no it should be 7+4+9

3 2 1

7 4 9

7 2 3

Hope you understood…!! :slight_smile:


#57

Thanks . I was doing a silly mistake of interchanging bob and alice’s turns. It got accepted now


#58

yes it should be 28


#59

it should be 28


6+5+9+8


#60

Thanks :slight_smile: now I get it…