Manya and sticks || State Space Reduction

      No Comments on Manya and sticks || State Space Reduction

Manya is  playing with sticks

Pussycat Mnya placed  sticks on a straight line. The ith stick is located at position xi and has height . There are no two sticks located at the same position. Manya can push sticks to make them fall to the left or the right side. While falling, a stick can touch its neighbors and make them also fall in the same direction (like dominoes).

More formally: if a stick at position x with height h is falling to the left, it will make all the sticks at positions …x inclusive fall to the left. Similarly, if a stick is falling to the right it will make all the sticks at positionsx…(x+h) inclusive fall to the right.

Now Manya is interested in finding the minimal number of sticks she needs to push to make all N sticks fall.

Input

The first line contains one integer N  the number of sticks.
Each of the next N lines contains two integers xi,hi  position and height of the ith stick.

Output format:
Print the minimal number of sticks Manya needs to push.

Constraints

15 points

10 points

10 points

65 points
Original constraints

SAMPLE INPUT

5
1 2
3 1
6 2
7 1
9 2

SAMPLE OUTPUT

2

Solution With explanation

This problem could be solved with dynamic programming. But first we need to calculate some additional information about the sticks.

Let’s sort them all by positions in ascending order. If we push i−th stick to the left it may cause some neighbouring sticks also fall to the left. Let l be the leftmost such stick. In a similar way let be the rightmost such stick if we push i−th stick to the right.

Let  be the minimal number of pushes needed to make fall all the sticks in positions  inclusive. We need to consider two options and select one with the minimal value:

Make i-th stick fall to the left
In this case we just need to push i−th stick to the left. And it’ll take  pushes in total.

Make i-th stick fall to the right
Let’s consider all such sticks that if we push one to the right it will make  stick also fall to the right. Suppose current such stick is . Then it will take  pushes to make all i sticks fall. So we need to select such stick that this value is minimal.

Let’s consider implementation details.

In the second option when we try to make i−th stick fall to the right we don’t actually need to consider each stick j all the time. Let’s just store all these sticks and keep them sorted by  values. We’re only interested in a stick with the minimal such value. It can be done with Priority Queue and cost ) for each query. Also do not forget to delete from this storage all such sticks  that rightmostLyingPos(j)<i.

To calculate leftmostLyingPos(i) first we need to find such leftmost stick j that . It can be easily done with Binary Search. And then we need to select minimal number among leftmostLyingPos(j)…leftmostLyingPos(i−1). This part can be done with Segment Tree. Both Binary Search and Segment Tree work in  for each query.

In a similar way to calculate  we need to find such rightmost stick  that . And then we need to select maximal number among .

Total time complexity is 

  1. #pragma comment(linker, "/STACK:500000000")
  2. #define _CRT_SECURE_NO_WARNINGS
  3. #include <algorithm>
  4. #include <assert.h>
  5. #include <bitset>
  6. #include <functional>
  7. #include <iostream>
  8. #include <list>
  9. #include <map>
  10. #include <math.h>
  11. #include <set>
  12. #include <stack>
  13. #include <stdio.h>
  14. #include <stdlib.h>
  15. #include <string>
  16. #include <string.h>
  17. #include <time.h>
  18. #include <queue>
  19. //#include <unordered_map>
  20. //#include <unordered_set>
  21. #include <utility>
  22. #include <vector>
  23. using namespace std;
  24. #define y0 y0ChloeGraceMoretz
  25. #define y1 y1ChloeGraceMoretz
  26. typedef long long ll;
  27. const double PI = acos(-1.0);
  28. const double EPS = 1e-9;
  29. const int INF = (int)2e9;
  30. struct Stick {
  31. int x, h;
  32. Stick() {}
  33. Stick(int _x, int _h) {
  34. x = _x;
  35. h = _h;
  36. }
  37. const bool operator<(Stick other) const {
  38. return x < other.x;
  39. }
  40. };
  41. int leftmostLyingPos[4 * (int)5e5 + 9];
  42. int rightmostLyingPos[4 * (int)5e5 + 9];
  43. int queryMin(int x, int l, int r, int i, int j) {
  44. if (i > r || l > j) {
  45. return INF;
  46. } else if (l >= i && r <= j) {
  47. return leftmostLyingPos[x];
  48. } else {
  49. return min(queryMin(2 * x + 1, l, (l + r) / 2, i, j),
  50. queryMin(2 * x + 2, (l + r) / 2 + 1, r, i, j));
  51. }
  52. }
  53. int queryMax(int x, int l, int r, int i, int j) {
  54. if (i > r || l > j) {
  55. return -INF;
  56. } else if (l >= i && r <= j) {
  57. return rightmostLyingPos[x];
  58. } else {
  59. return max(queryMax(2 * x + 1, l, (l + r) / 2, i, j),
  60. queryMax(2 * x + 2, (l + r) / 2 + 1, r, i, j));
  61. }
  62. }
  63. void updateMin(int x, int l, int r, int pos, int y) {
  64. if (l == r) {
  65. leftmostLyingPos[x] = y;
  66. } else {
  67. if (pos <= (l + r) / 2) {
  68. updateMin(2 * x + 1, l, (l + r) / 2, pos, y);
  69. } else {
  70. updateMin(2 * x + 2, (l + r) / 2 + 1, r, pos, y);
  71. }
  72. leftmostLyingPos[x] = min(leftmostLyingPos[2 * x + 1], leftmostLyingPos[2 * x + 2]);
  73. }
  74. }
  75. void updateMax(int x, int l, int r, int pos, int y) {
  76. if (l == r) {
  77. rightmostLyingPos[x] = y;
  78. } else {
  79. if (pos <= (l + r) / 2) {
  80. updateMax(2 * x + 1, l, (l + r) / 2, pos, y);
  81. } else {
  82. updateMax(2 * x + 2, (l + r) / 2 + 1, r, pos, y);
  83. }
  84. rightmostLyingPos[x] = max(rightmostLyingPos[2 * x + 1], rightmostLyingPos[2 * x + 2]);
  85. }
  86. }
  87. int main() {
  88. int n;
  89. scanf("%d", &n);
  90. assert(1 <= n && n <= (int)5e5);
  91. vector<Stick> sticks(n);
  92. for (int i = 0; i < n; ++i) {
  93. int x, h;
  94. scanf("%d %d", &x, &h);
  95. assert(1 <= x && x <= (int)2e9);
  96. assert(1 <= h && h <= (int)2e9);
  97. sticks[i] = Stick(x, h);
  98. }
  99. sort(sticks.begin(), sticks.end());
  100. int s = 2;
  101. while (s < n) {
  102. s *= 2;
  103. }
  104. for (int i = 0; i <= 2 * (s - 1); i++) {
  105. leftmostLyingPos[i] = INF;
  106. rightmostLyingPos[i] = -INF;
  107. }
  108. for (int i = 0; i < n; ++i) {
  109. int curLeftmostLyingPos = (int) (upper_bound(sticks.begin(), sticks.begin() + i + 1, Stick(max((ll)sticks[i].x - sticks[i].h - 1, (ll)0), INF + 1)) - sticks.begin());
  110. curLeftmostLyingPos = min(curLeftmostLyingPos, queryMin(0, 0, s - 1, curLeftmostLyingPos, i - 1));
  111. updateMin(0, 0, s - 1, i, curLeftmostLyingPos);
  112. }
  113. for (int i = n - 1; i >= 0; --i) {
  114. int curRightmostLyingPos = (int) (--upper_bound(sticks.begin() + i, sticks.end(), Stick(min((ll)sticks[i].x + sticks[i].h, (ll)INF), INF + 1)) - sticks.begin());
  115. curRightmostLyingPos = max(curRightmostLyingPos, queryMax(0, 0, s - 1, i + 1, curRightmostLyingPos));
  116. updateMax(0, 0, s - 1, i, curRightmostLyingPos);
  117. }
  118. vector<int> dp(n);
  119. priority_queue<pair<int, int> > pushedRightSticks; // {pos, value}
  120. multiset<int> pushedRightValues;
  121. for (int i = 0; i < n; ++i) {
  122. while (!pushedRightSticks.empty()) {
  123. int curRightmostPos = -pushedRightSticks.top().first;
  124. if (curRightmostPos >= i) {
  125. break;
  126. }
  127. int value = pushedRightSticks.top().second;
  128. pushedRightSticks.pop();
  129. pushedRightValues.erase(pushedRightValues.find(value));
  130. }
  131. int value = 1 + ((i - 1 < 0) ? 0 : dp[i - 1]);
  132. pushedRightSticks.push({-rightmostLyingPos[s - 1 + i], value});
  133. pushedRightValues.insert(value);
  134. dp[i] = 1 + ((leftmostLyingPos[s - 1 + i] - 1 < 0) ? 0 : dp[leftmostLyingPos[s - 1 + i] - 1]);
  135. if (!pushedRightValues.empty()) {
  136. dp[i] = min(dp[i], *pushedRightValues.begin());
  137. }
  138. }
  139. printf("%d\n", dp[n - 1]);
  140. return 0;
  141. }

{Code with Codeater}

Give Your Reviews

Leave a Reply