devil_17's blog

By devil_17, 4 years ago, In English

I was solving the problem 607A - Chain Reaction and got WA on test case 11. Here's my submission 82317236. dp[i] is basically the number of destroyed beacons if we consider the coordinates [0,i]. numBeacons[i] is the total number of beacons again in [0,i]. Please help me where I am wrong. Have been stuck in this problem for a while now.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 years ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

try initializing ii by int ii = numBeacons[0]; instead of having int ii = 0;

since your loop that is evaluating the dp starts from 1 in cases where initial poisition of some Beacon is 0 the powers are being shifted (as ii is still 0). i.e. the instead of power of Beacon 1 power of Beacon 0 is being used and so on.

Example test case:

4
0 1
1 2
2 4
3 2

Actual ans : 2

Your Output : 3

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Thank you so much man! I knew I had made some silly mistake but couldn't figure it out.