TADELIVE - Editorial

editorial
, , , ,
21

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

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

23

Your solution failed for last test case

24

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

25

What happens when A[i] == B[i], who is assigned to collect the tip? I got 10 for my submission and although the code is similar to the one provided in the editorial I am unable to figure what is (logically)wrong in my code.

Help would really appreciated.

Regards, Ankit

Link to code

26

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ā€¦

27

Can somebody explain the last test case mentioned above?

28

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
29

Your code fails with

2 1 1
6 8
5 6

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

30

Are there some good tutorials on state dp ?

31

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ā€¦!!

32

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));
    }
33

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

34

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

35

@dev8546: Yes, corrected.

36


My code works for all these test cases. But in the contest it was wrong for one of the cases for 30 points and one for 60 points.Rest all it was correct answer.

37

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ā€¦

38

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ā€¦

39

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

40

no it should be 7+4+9

3 2 1

7 4 9

7 2 3

Hope you understoodā€¦!! :slight_smile: