TADELIVE - Editorial

editorial
, , , ,
37

@abcdexter24: I added one more test case (last one), you code returns 14 for this one…

1 Like
38

dont check solution…just saw your edit for case 1 and 2

39

Check last test case

2 1 1
5 6
6 8
40

@abcdexter24: Actually if one solves this problem completely after the contest, he can practice bitmask, dp, recursion and greedy all in one :slight_smile:

2 Likes
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 - The new Karma system | CodeChef 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…

1 Like
46

Your code fails with

2 1 1
6 8
5 6

should be 13, your code returns 12 - CpHHDI - Online C++ Compiler & Debugging Tool - Ideone.com

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[i] + dp(i + 1, j + 1));
    }
   
    BobOrders = i - j;
    if (BobOrders + 1 <= Y) {
        res = max(res, B[i] + 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[i] and B[i] 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…

1 Like
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: