Link to the problem: http://codeforces.net/problemset/problem/607/A
Latest submission: http://codeforces.net/contest/607/submission/18781430
Code with comments: http://ideone.com/qlKrkI
I am trying an approach which uses DP to find the maximum number of previously activated beacon at position i, and finding the first out of range beacon by using binary search.
It seems that I am over-counting the activatable beacon in test 11, any thoughts why it went wrong? :/
Thanks for any help in advance.
Test:
3
1 1
3 1
5 4
The answer is 1. (Your solution prints 2).
When you find this bug, try this test:
4
1 1
3 1
5 4
7 1
The answer is 2.
if you get right answers for these tests, I am sure that you will get Accepted)
Oh! Now I see... I thought I had the freedom of skipping some bulbs, seems that is not the case :P
Update: Now I get AC, no wonder why everyone was only using a one dimensional array. XP Thanks a lot for the hint/hack test cases.
I can not understand where I am stuck. I am getting 1 and 2 as answer to the sample test case in your above comment, But I'am getting WA in 9th test case:
Sort your pair array I had same problem too