fork download
copy 
  1. /*******************************************************
  2. 1) InMobi OA — Minimum Active Towers in a Circle
  3.  
  4. Problem:
  5. - n towers in a circle (0..n-1)
  6. - activate i => neutralizes all towers within circular distance R[i] (including itself)
  7. - find minimum activations to neutralize all towers
  8.  
  9. Idea:
  10. - Convert each tower to a coverage interval on the circle
  11. - Unroll circle to a line of length 2n
  12. - Then solve "minimum intervals to cover a segment of length n"
  13. - Greedy "extend farthest" + binary lifting (jump pointers) for speed
  14.  
  15. Time: O(n log n)
  16. *******************************************************/
  17.  
  18. #include <bits/stdc++.h>                 // include almost all standard C++ headers (common in CP)
  19. using namespace std;                     // avoid writing std:: everywhere
  20.  
  21. int main() {                             // program starts here
  22.     ios::sync_with_stdio(false);         // faster I/O
  23.     cin.tie(nullptr);                    // faster I/O
  24.  
  25.     int n;                               // number of towers
  26.     cin >> n;                            // read n
  27.     vector<long long> R(n);              // R[i] = radius for tower i (use long long for safety)
  28.     for (int i = 0; i < n; i++) cin >> R[i]; // read all radii
  29.  
  30.     // If any tower covers the whole circle by itself, answer is 1.
  31.     for (int i = 0; i < n; i++) {        // loop all towers
  32.         if (2LL * R[i] + 1 >= n) {       // coverage size in circle is (2*R+1); if >= n => covers all
  33.             cout << 1 << "\n";           // print 1 activation
  34.             return 0;                    // exit early
  35.         }
  36.     }
  37.  
  38.     int P = 2 * n;                       // total "unrolled" positions: 0..2n-1 (we call that P)
  39.     int LAST = P - 1;                    // last valid index in unrolled range is 2n-1
  40.  
  41.     vector<int> bestAtL(P, -1);          // bestAtL[l] = farthest right endpoint among intervals starting at l
  42.  
  43.     auto norm = [&](long long x) -> int { // function to wrap any integer x into [0..n-1]
  44.         x %= n;                          // take modulo n
  45.         if (x < 0) x += n;               // if negative, shift into positive range
  46.         return (int)x;                   // return as int
  47.     };
  48.  
  49.     // Build intervals for each tower i.
  50.     for (int i = 0; i < n; i++) {        // go through each tower
  51.         long long rad = R[i];            // radius of coverage
  52.  
  53.         long long rawL = (long long)i - rad; // left boundary (may be negative)
  54.         long long rawR = (long long)i + rad; // right boundary (may exceed n-1)
  55.  
  56.         int L = norm(rawL);              // normalize left into [0..n-1]
  57.         int RR = norm(rawR);             // normalize right into [0..n-1]
  58.  
  59.         // helper to add an interval [l, r] to bestAtL (clamped to our unrolled array)
  60.         auto addInterval = [&](long long l, long long r) { // lambda function for adding interval
  61.             if (l > LAST) return;        // if start is beyond useful range, ignore
  62.             if (l < 0) return;           // safety check (shouldn't happen here)
  63.             r = min<long long>(r, LAST); // clamp r to LAST so we don't go beyond array
  64.             bestAtL[(int)l] = max(bestAtL[(int)l], (int)r); // keep only farthest reach for that start l
  65.         };
  66.  
  67.         if (L <= RR) {                   // case 1: interval does NOT wrap around circle
  68.             addInterval(L, RR);          // add interval in base copy [0..n-1]
  69.             addInterval((long long)L + n, (long long)RR + n); // add same interval shifted by +n for unrolled copy
  70.         } else {                         // case 2: interval wraps around (covers end and start of circle)
  71.             addInterval(L, (long long)RR + n); // represent wrap as one continuous interval in unrolled line
  72.             addInterval((long long)L + n, (long long)RR + 2LL * n); // second copy shifted by +n again
  73.         }
  74.     }
  75.  
  76.     vector<int> farthest(P, -1);         // farthest[x] = best reach among all intervals with start <= x
  77.     for (int x = 0; x < P; x++) {        // build prefix maximum
  78.         farthest[x] = bestAtL[x];        // start with interval that starts exactly at x
  79.         if (x) farthest[x] = max(farthest[x], farthest[x - 1]); // also consider earlier starts (prefix max)
  80.     }
  81.  
  82.     vector<int> nxt(P + 1, P);           // nxt[x] = next uncovered position after taking 1 greedy step
  83.     for (int x = 0; x < P; x++) {        // compute nxt for each x
  84.         if (farthest[x] < x) nxt[x] = x; // if we cannot even cover x, we're stuck (no progress)
  85.         else nxt[x] = farthest[x] + 1;   // else jump to one past farthest covered point
  86.     }
  87.     nxt[P] = P;                          // if already at end, stay at end
  88.  
  89.     int LOG = 1;                         // number of levels for binary lifting
  90.     while ((1 << LOG) <= P + 1) LOG++;   // increase LOG until 2^LOG is big enough
  91.  
  92.     vector<vector<int>> up(LOG, vector<int>(P + 1, P)); // up[j][x] = position after 2^j greedy steps
  93.     up[0] = nxt;                         // base case: 2^0 = 1 step is nxt
  94.  
  95.     for (int j = 1; j < LOG; j++) {      // build higher jumps
  96.         for (int x = 0; x <= P; x++) {   // for every position
  97.             up[j][x] = up[j - 1][ up[j - 1][x] ]; // jump twice using previous layer
  98.         }
  99.     }
  100.  
  101.     const int INF = 1e9;                 // a large number for "min answer"
  102.     int ans = INF;                       // store best answer
  103.  
  104.     // Try starting segment at each s in [0..n-1] covering [s, s+n-1]
  105.     for (int s = 0; s < n; s++) {        // try each start
  106.         int target = s + n;              // we want to reach at least this position (one past end)
  107.  
  108.         if (nxt[s] == s) continue;       // if stuck at start, skip
  109.  
  110.         int pos = s;                     // current position we need to cover
  111.         int steps = 0;                   // number of activations used
  112.  
  113.         // Use binary lifting to take big jumps while still not reaching target
  114.         for (int j = LOG - 1; j >= 0; j--) { // from largest jump down to smallest
  115.             if (up[j][pos] < target) {   // if taking 2^j steps still keeps us before target
  116.                 pos = up[j][pos];        // apply the jump
  117.                 steps += (1 << j);       // add number of steps taken
  118.             }
  119.         }
  120.  
  121.         if (nxt[pos] == pos) continue;   // if we are stuck before finishing, skip
  122.         steps++;                         // take one more greedy step
  123.         pos = nxt[pos];                  // update position
  124.  
  125.         if (pos >= target) ans = min(ans, steps); // if covered full segment, update answer
  126.     }
  127.  
  128.     cout << (ans == INF ? -1 : ans) << "\n"; // print answer (or -1 if impossible)
  129.     return 0;                             // exit
  130. }
Runtime error #stdin #stdout 1.11s 2096004KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/RCQMgD
language:
C++14 (gcc 8.3)
created:
117 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!