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
i forgot to check the condition
thanks
1 Like
@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.
found lot of cases on which your code fails:
Check these:
Your Output: http://ideone.com/CXnUov
AC output: http://ideone.com/rOMkjI
@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: CodeChef: Practical coding for everyone
You are sorting vector v
and then you are not using it. I missed something?
i will edit the mistake in a secā¦but still isnāt it weird the code passed all but 2 test casesā¦?
@krish2311: Added, sorry for being so late
that was so lame what i had doneā¦thank u for pointing out the mistakeā¦
Test cases are not very strongā¦
Believe me, Iām very good in doing similar mistakes
1 Like
Why difference array is been considered? I m not able to understand the logic behind it, even after reading greedy exchange.
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.
2 Likes
@jenish_9599 How can we infer that more difference will have more effect on the answer?
1 Like
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.
2 Likes
Thanks!! Now I understood the solution.
1 Like
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
can you please explain the dp approach of this question by any example and also how can anyone reach to this solution.
Can anyone say whats wrong in my code, i am getting only 10/100.
https://www.codechef.com/viewsolution/24265362