haleyk100198's blog

Stucked at 607A — Chain Reaction
By haleyk100198, history, 8 years ago, In English

Link to the problem: http://mirror.codeforces.com/problemset/problem/607/A

Latest submission: http://mirror.codeforces.com/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.

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh! Now I see... I thought I had the freedom of skipping some bulbs, seems that is not the case :P

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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.

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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:

    //
// Created by sourabh on 15/2/18.
//
#include <bits/stdc++.h>
using namespace std;

long long int binarySearch(long long int start, long long int dis, long long int pwr) {
    long long int end = 1;
    while(start > end) {
        int mid = end + (start - end) / 2 + 1;
        if(dis - mid >= pwr)
            end = mid;
        else
            start = mid - 1;
    }
    if(dis - start > pwr)
        return start + 1;
    return start;
}

int main() {
    long long int n, resl = INT_MAX;
    cin >> n;
    pair<long long int, long long int> ar[n];
    long long int prefix[n+1] = {0};

    for(auto &i : ar) {
        cin >> i.first;
        cin >> i.second;
    }

    for(long long int i = 2; i <= n; ++i) {
        long long int pos = binarySearch(i - 1, ar[i-1].first, ar[i-1].second);
        prefix[i] = i - pos + prefix[pos-1];
    }

    for(long long int i = n; i >= 1; --i)
        resl = min(resl, n - i + prefix[i]);
    cout << resl;
}
    → Reply