Блог пользователя rajshekhariitr123

Автор rajshekhariitr123, история, 7 недель назад, По-английски

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

  • Проголосовать: нравится
  • -11
  • Проголосовать: не нравится

»
7 недель назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 недель назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 недель назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 недель назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    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.