rajshekhariitr123's blog

By rajshekhariitr123, history, 7 weeks ago, In English

why the logic fails???

I separated the values equal to x from the array and sorted the rest...I took sum=0 and then I used left and right pointers... I checked the left value,if it's >= next multiple of x(starting from 1) then I added up the left value in bonus coins and sum...else I checked the sum of left and right values...if that's >= next multiple of x...I added up the right value in bonus coins and left and right values in sum ...else I just added the left value in sum... problem link-https://mirror.codeforces.com/problemset/problem/2161/C

  • Vote: I like it
  • -11
  • Vote: I do not like it

»
7 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by rajshekhariitr123 (previous revision, new revision, compare).

»
7 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by rajshekhariitr123 (previous revision, new revision, compare).

»
7 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

If somebody can figure out what's wrong in the logic pls help...

  • »
    »
    7 weeks ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    The idea of using left and right pointer is fine but since you need to make the maximum possible bonus points you should use greedy strategy by always adding the value of the right pointer whenever it is possible. you should never add the small value to your bonus(i.e. the value of the left pointer, since you need to maximize the bonus points). in your approach when you are getting the (sum + left value >= next multiple of X) you are adding the small value to your bonus but in this case what you should do is you should add the value of the right pointer and that will surely be greater than the next multiple of X(since the value of the right pointer is greater than left pointer value) and so you will get a better bonus score than when you would have added the left pointer value. also to the sum variable, this time don't add the left value pointer, instead since you added the right pointer value to bonus score you have to add the right pointer value to your sum variable(don't forget to decrease the right pointer by one).

    I think this would help.