Sub-segment dynamics: basic things and “one is good and two is better”
Good evening.
In this post I will analyze Problem B “Oaks” from the practical tour of the city computer science Olympiad in St. Petersburg.
This problem for dynamic programming by sub-segments and the idea of a solution is interesting in that it is more convenient to count two speakers instead of one. If you are interested (ignorance of the dynamics does not release, but it will be more difficult) - welcome.
To start, you can see the condition of the problem. It lies here with the tests (only conditions can be downloaded from min.us).
After folding the legend, the following task remains:
If you want, you can think about it (the name of the post can tell you).
As you might guess from the tags - the solution is a certain dynamic. If you forgot or did not know what dynamic programming is, I will remind you. The idea of dynamics is that for very small examples (for example, one tree) the answer is obvious (do not saw anything), but for large ones you can get a solution if you know the solutions for some smaller independent subtasks. At this point, the dynamics are very reminiscent of induction. How to reduce the problem, for example, for ten trees to smaller ones? Suppose we already know the answer (we will not use it, but it is useful to imagine this). There are two extreme trees and some middle in it. Let's iterate over any tree from this middle (in general, any tree that lies in height between the borders - otherwise you cannot leave it):
You can notice that all operations will be performed either on the left side or on the right. So, they do not depend on each other in any way. So they split into two independent subtasks. You can relax (choose the best) answer on our large segment.
And what to do when there are no trees in the interval between our borders (for example, trees 4 and 9)? Here we understand that in this case we need to cut down all the trees on the interval. The question is, in what order? There is a temptation to make a greedy algorithm: cut down the first tree that comes across and so on until they run out. However, it is incorrect:
I think it’s obvious that you shouldn’t come up with various optimizations in the style of "start the search in the last two steps", etc. - this all breaks off with a large random test.
Need something smarter. We look at the title of the post one more time and come up with a very similar dynamics by sub-segments: for two trees and less, nothing needs to be deleted at all. And for more, you need to sort out the tree, which we will delete last and notice that again we have received two subtasks: left and right. The only distinguishing point is that you need to check that this tree can be deleted at the end (when the boundaries of the interval become its neighbors)
For example, you can delete tree 4 as the last, but 3 not.
The answer is restored by the classical method - we remember the optimal transition from each state (where the best answer was reached) to the array, and then we go from the end. It is convenient to write recovery in dynamics by sub-segments recursively:
In total, we have O (n 2 ) states of each dynamics (one for each sub-segment). In each dynamics, the transition is made in O (n) - iterate over the tree inside the interval. When restoring the answer, we visit each state no more than once. It turns out to be a square, but since it is asymptotically (infinitely less on infinitely large n ) less than a cube, it can be neglected.
The total operating time is O (n 3 ) , which at n = 200 is O (8 * 10 6 ) , which works out instantly. It suits us too.
First you need to read the data into an array / vector. You know how to do it.
Next, you need to calculate the dynamics to remove all trees. We will store it in the array int del [a] [b] - -1 if it is impossible to delete all the trees on the interval (a, b) , and the number of the last tree is different.
To enumerate sub-segments, it is tempting to write two cycles: However, this is fundamentally wrong, since the dynamics transition will be correct only when we know the answer for the “smaller” subtasks. In our case, for sub-segments of shorter length. Therefore, you must first sort through the length of the segment, and then start (or end): In this cycle, you need to sort through the last tree and check the possibility of deletion. Also, do not forget to initialize the dynamics for empty intervals:
We will store the second dynamics in two arrays - int dyn [a] [b] and int fr [a] [b] . The first is, in fact, the answer for the subsegment (how many minimum trees need to be removed), or infinity (I use 10 9 ) if you cannot leave a non-decreasing subsequence. And in the second array we will store either -1 if infinity is written in the first, or the last remote tree.
So, we are writing. Here you can initialize everything along the way (a separate loop is only needed to fill with infinities):
It has already been completely written above - that code works completely. It remains only to verify that there is an answer, call the function, and output the result:
The entire program can be viewed on pastebin . Since she wrote at the Olympics, there are some abbreviations for speed dialing and no comments. However, I cited all the significant code in the article.
On the topic of testing algorithmic problems, you can write many large articles. But we want to quickly, right? Therefore, we recall where we downloaded the tests at the beginning of the article, unpack them somewhere (the task is called oaks ) and either run all 50 tests with pens, or compile the check.dpr file ( compiled ) and write the script on CMD: Run. If you saw the inscription ALL IS OK! and “Press Any key” - your decision is right. If not, then there is a test on which it does not work correctly. Do not rush to watch this test - it will be much more useful to find and fix the bug yourself.
That's all I wanted to tell. I hope you understand everything and I have not wasted your time in vain.
Thank you for your attention, easy to accept you.
I will be glad to constructive criticism.
In this post I will analyze Problem B “Oaks” from the practical tour of the city computer science Olympiad in St. Petersburg.
This problem for dynamic programming by sub-segments and the idea of a solution is interesting in that it is more convenient to count two speakers instead of one. If you are interested (ignorance of the dynamics does not release, but it will be more difficult) - welcome.
Condition
To start, you can see the condition of the problem. It lies here with the tests (only conditions can be downloaded from min.us).
After folding the legend, the following task remains:
- There are n (2 <= n <= 200) oaks, each has a height - an integer from 1 to 1000 (incl.).
- We can: remove the oak from the sequence if:
- Or it is strictly smaller than both neighbors
- Or strictly more of them
For example, in the following figure, “oaks” are highlighted in green, which can be removed:
- It is necessary to turn the sequence into a non - strictly increasing sequence for a minimal number of operations . The deletion sequence must also be deduced. For example, like this:
If you want, you can think about it (the name of the post can tell you).
main idea
As you might guess from the tags - the solution is a certain dynamic. If you forgot or did not know what dynamic programming is, I will remind you. The idea of dynamics is that for very small examples (for example, one tree) the answer is obvious (do not saw anything), but for large ones you can get a solution if you know the solutions for some smaller independent subtasks. At this point, the dynamics are very reminiscent of induction. How to reduce the problem, for example, for ten trees to smaller ones? Suppose we already know the answer (we will not use it, but it is useful to imagine this). There are two extreme trees and some middle in it. Let's iterate over any tree from this middle (in general, any tree that lies in height between the borders - otherwise you cannot leave it):
You can notice that all operations will be performed either on the left side or on the right. So, they do not depend on each other in any way. So they split into two independent subtasks. You can relax (choose the best) answer on our large segment.
And what to do when there are no trees in the interval between our borders (for example, trees 4 and 9)? Here we understand that in this case we need to cut down all the trees on the interval. The question is, in what order? There is a temptation to make a greedy algorithm: cut down the first tree that comes across and so on until they run out. However, it is incorrect:
I think it’s obvious that you shouldn’t come up with various optimizations in the style of "start the search in the last two steps", etc. - this all breaks off with a large random test.
Need something smarter. We look at the title of the post one more time and come up with a very similar dynamics by sub-segments: for two trees and less, nothing needs to be deleted at all. And for more, you need to sort out the tree, which we will delete last and notice that again we have received two subtasks: left and right. The only distinguishing point is that you need to check that this tree can be deleted at the end (when the boundaries of the interval become its neighbors)
For example, you can delete tree 4 as the last, but 3 not.
Answer recovery
The answer is restored by the classical method - we remember the optimal transition from each state (where the best answer was reached) to the array, and then we go from the end. It is convenient to write recovery in dynamics by sub-segments recursively:
Answer recovery
vector<int> ans; // Последовательность удалений
// a и b - границы интервала, на котором хотим срубить все деревья
void deleteAll(int a, int b) {
assert(del[a][b] >= 0);
if (del[a][b] == a) return;
deleteAll(a, del[a][b]);
deleteAll(del[a][b], b);
ans.push_back(del[a][b]);
}
// аналогично
void restoreAns(int a, int b) {
assert(fr[a][b] >= 0);
if (fr[a][b] == a) {
deleteAll(a, b);
return;
}
restoreAns(a, fr[a][b]);
restoreAns(fr[a][b], b);
}Working hours
In total, we have O (n 2 ) states of each dynamics (one for each sub-segment). In each dynamics, the transition is made in O (n) - iterate over the tree inside the interval. When restoring the answer, we visit each state no more than once. It turns out to be a square, but since it is asymptotically (infinitely less on infinitely large n ) less than a cube, it can be neglected.
The total operating time is O (n 3 ) , which at n = 200 is O (8 * 10 6 ) , which works out instantly. It suits us too.
How to write
First you need to read the data into an array / vector. You know how to do it.
First speaker
Next, you need to calculate the dynamics to remove all trees. We will store it in the array int del [a] [b] - -1 if it is impossible to delete all the trees on the interval (a, b) , and the number of the last tree is different.
To enumerate sub-segments, it is tempting to write two cycles: However, this is fundamentally wrong, since the dynamics transition will be correct only when we know the answer for the “smaller” subtasks. In our case, for sub-segments of shorter length. Therefore, you must first sort through the length of the segment, and then start (or end): In this cycle, you need to sort through the last tree and check the possibility of deletion. Also, do not forget to initialize the dynamics for empty intervals:
for (int left = 0; left < n; left++)
for (int right = left; right < n; right++) {
// ...
}for (int l = 2; l < n; l++)
for (int a = 0; a + l < n; a++) {
int b = a + l;
// ...
}// Можем ли мы удалить дерево высоты h2, если его соседи имеют высоты h1 и h3
bool can(int h1, int h2, int h3) {
if (h1 < h2 && h3 < h2) return true;
if (h1 > h2 && h3 > h2) return true;
return false;
}
// ...
for (int a = 0; a + 1 < n; a++)
del[a][a + 1] = a;
for (int l = 2; l < n; l++)
for (int a = 0; a + l < n; a++) {
int b = a + l;
for (int i = a + 1; i < b; i++)
if (del[a][i] >= 0 && del[i][b] >= 0 && can(h[a], h[i], h[b])) {
del[a][b] = i;
break;
}
}Second speaker
We will store the second dynamics in two arrays - int dyn [a] [b] and int fr [a] [b] . The first is, in fact, the answer for the subsegment (how many minimum trees need to be removed), or infinity (I use 10 9 ) if you cannot leave a non-decreasing subsequence. And in the second array we will store either -1 if infinity is written in the first, or the last remote tree.
So, we are writing. Here you can initialize everything along the way (a separate loop is only needed to fill with infinities):
// Точно также перебираем отрезки
for (int l = 1; l < n; l++)
for (int a = 0; a + l < n; a++) {
int b = a + l;
if (h[a] > h[b]) continue; // Если левая граница выше правой, тут мы бессильны
if (del[a][b] >= 0) { // Если можно удалить вообще все поддеревья, давайте попробуем
dyn[a][b] = b - a - 1;
fr[a][b] = a;
}
for (int i = a + 1; i < b; i++) {
// Если наше дерево ниже левой границы, или выше правой,
// оно нам не точно подходит - оставить мы его не можем
if (h[a] > h[i] || h[i] > h[b]) continue;
// Если хоть в одном месте будет бесконечность, то в сумме
// также будет число, большее бесконечности
int cans = dyn[a][i] + dyn[i][b];
if (dyn[a][b] > cans) {
dyn[a][b] = cans;
fr[a][b] = i;
}
}
}Answer recovery
It has already been completely written above - that code works completely. It remains only to verify that there is an answer, call the function, and output the result:
int a = 0, b = n - 1;
if (fr[0][n - 1] < 0) printf("-1\n");
else {
ans = vector<int>();
restoreAns(a, b);
printf("%d\n", ans.size());
for (int i = 0; i < ans.size(); i++)
printf("%d\n", ans[i] + 1);
}Together
The entire program can be viewed on pastebin . Since she wrote at the Olympics, there are some abbreviations for speed dialing and no comments. However, I cited all the significant code in the article.
Testing
On the topic of testing algorithmic problems, you can write many large articles. But we want to quickly, right? Therefore, we recall where we downloaded the tests at the beginning of the article, unpack them somewhere (the task is called oaks ) and either run all 50 tests with pens, or compile the check.dpr file ( compiled ) and write the script on CMD: Run. If you saw the inscription ALL IS OK! and “Press Any key” - your decision is right. If not, then there is a test on which it does not work correctly. Do not rush to watch this test - it will be much more useful to find and fix the bug yourself.
@echo off
for %%i IN (tests\??) DO (
del oaks.in oaks.out >nul 2>&1
copy %%i oaks.in >nul 2>&1
main >nul 2>&1
if errorlevel 1 exit
check oaks.in oaks.out %%i.a
if errorlevel 1 exit
)
echo ALL IS OK!
pauseConclusion
That's all I wanted to tell. I hope you understand everything and I have not wasted your time in vain.
Thank you for your attention, easy to accept you.
I will be glad to constructive criticism.