TADELIVE - Editorial

editorial
, , , ,
41

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

42

should not second last case output be 26… as 1st would deliver 7 and second one would 2+9+8=19
and hence 19+7=26… and please help me where my code is wrong?
http://www.codechef.com/viewsolution/5661711

43

4 1 3
7 5 2 2
6 2 9 8
should it not be 28?
6+5+9+8
the second last test case
http://www.codechef.com/viewsolution/5663226

1 Like
44

yes it should be 28

1 Like
45

it should be 28

6+5+9+8

1 Like
46

Thanks :slight_smile: now I get it…

47

subtracting the price array and sorting and then optimizing works… i have solved this ques by the same method… is the approach accurate??

1 Like
48

Guys give attention to sorting d[i] in decreasing order rather than increasing…

49

i got 40 points for this solution
http://www.codechef.com/viewsolution/5663762 plz tell where my code is lacking :confused:
thanks in advance :slight_smile:
@betlista can u help :slight_smile:

50

@dpraveen: do add the psuedocode for backward dp in subtask 2.

51

Test these

8 6 8
15 50 77 52 27 62 63 61 
350 271 916 438 281 998 125 241

your output:3588
correct output:3620


9 5 9
60 98 21 52 9 15 62 74 83 
552 893 44 920 52 830 155 40 557 

your output:4054 
correct output:4077

you may check these links:

Your Code: http://ideone.com/KCvugn

AC Code:http://ideone.com/rOMkjI

2 Likes
52

i forgot to check the condition
thanks :slight_smile:

1 Like
53

Can be go via Merge_Sort.

54

welcome… :slight_smile:

55

@ankitdhall
given the solution is greedy you should make that choice greedily too. Consider that you have sorted the difference array in ascending order. Now if A[i]==B[i] then you know that the difference is zero therefore it will always be beneficial for Bob to take that order(if he can) because further orders ahead will generate more tip for Andy.

Consider the simple case

2 1 1

5 6

5 5

Sorted difference array is : 0 1

if Andy takes the first order, total tips are 10.

Greedily choosing we always give the order to Bob(if we can) when the difference is zero. In that case tips=11.

56

http://www.codechef.com/viewsolution/5658539

plz somebody check what i missed and got 10 points :frowning:
(my code clears all above test cases)

57

found lot of cases on which your code fails:

Check these:

Your Output: http://ideone.com/CXnUov

AC output: http://ideone.com/rOMkjI

58

@ironmandhruv yea thanks for clearing my doubt! I had done the same thing but I still seem to get WA for 2 cases. Could you help me figure where the logical problem could be? Here’s my code: http://www.codechef.com/viewsolution/5665140

59

I got AC on 10 pts and 30 pts on my sol and TLE on some test-cases of the 60 pts. I was finding the maximum in each case which was the problem. So I decided to sort it. Now it runs fast but getting WA in test case of 30 pts and 1 in 60 pts.
And My Code is clearing all the test-cases mentioned below…I think some minor mistake i am making.

Here are my two codes :

Getting 40 pts :

http://www.codechef.com/viewsolution/5659672

Getting 10 pts :

http://www.codechef.com/viewsolution/5666065

Someone pls point out the mistake i am making…

Edit 1 :
Got a test case for which i get WA.

6 5 5

76 8 64 12 77 56

397 240 293 287 137 433

My 2nd code gives 1466 and first code gives 1727 (which is the correct one)

I still cant figure out the mistake while i am making while sorting.

60

You are sorting vector v and then you are not using it. I missed something?