TADELIVE - Editorial

dynamic-programming
editorial
greedy
ltime19
simple

#61

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


#62

i forgot to check the condition
thanks :slight_smile:


#63

welcomeā€¦ :slight_smile:


#64

@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*==B* 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.


#65

found lot of cases on which your code fails:

Check these:


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

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


#66

@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


#67

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


#68

i will edit the mistake in a secā€¦but still isnā€™t it weird the code passed all but 2 test casesā€¦?


#69

@krish2311: Added, sorry for being so late :frowning:


#70

that was so lame what i had doneā€¦thank u for pointing out the mistakeā€¦


#71

Test cases are not very strongā€¦


#72

Believe me, Iā€™m very good in doing similar mistakes :smiley:


#73

Why difference array is been considered? I m not able to understand the logic behind it, even after reading greedy exchange.


#75

The question is about to choose from either form A or form B,
When we have big difference it make more effect to final ans, less difference doesnā€™t make that much effect, So first of all we utilize our X and Y in such a way that we can get more tip.


#76

@jenish_9599 How can we infer that more difference will have more effect on the answer?


#78

if ,
X = 5
Y = 1
A = 1 2 3
B= 10 20 100
Diff = [9,18,97]

sorted_object = [3,2,1] (element_index )
Current X = 5 and Y = 1
first will take 3rd element and B[3] > A[2] So point += 100
X = 5 and Y = 0

Now y is zero so we have to select all elements from A only, points +=(1 + 2)
total ans = 103

if we consider other sequence, it will always gives less ans.

like for [1,2,3]
X = 5 and Y = 1
points = 0

we will check for first element A[1]<B[1]
so we select B[1] and points += 10;
X = 5 and y = 0;

Now we have to select all elements form A only.
So points += (2 + 3)
total points is 15 which is less than 103.


#79

Thanks!! Now I understood the solution.


#81

have someone can help me whats wrong with my codeā€¦it passed all testcase given here but still able to score 10 pts

https://www.codechef.com/viewsolution/23770539


#82

can you please explain the dp approach of this question by any example and also how can anyone reach to this solution.


#83

Can anyone say whats wrong in my code, i am getting only 10/100.
https://www.codechef.com/viewsolution/24265362