I've participated in JOI 2017 and I'm trying to find the solutions in English. Why don't we create a tutorial with brief explainings of the solutions? I'll contribute by posting the two problems I have solved during the contest, but I'll update when people comment solutions.
If someone speaks Japanese, the official JOI website has posted solutions, but they're only available in Japanese, so you could translate a brief explanation to us :)
Links for problem statements (English) are available below. Could you help rng_58?
Keep an array of differences between consecutive heights, so that delta[i]=A[i]-A[i-1]. Keep the sum of the values of positive differences in a variable pos, and the sum of the absolute values of negative differences in a variable neg. Each time you update a range (l,r), adding X to it, you just need to update differences l and r+1. To update difference i, you reduce its absolute value from pos or neg, depending on its signal, add X to it and adds its absolute value to pos or neg. After each query, the answer will be neg*T-pos*S. Don't forget to use long long.
You have to create K-M stops for the semiexpress line (besides the M fixed ones). For each range between two consecutive express stops, analyze the advantage of creating a semiexpress stop on each station of the range. You can easily calculate what are the stations in that range that one can achieve within time T using only the express and local trains. Call the last station of this range i. Check how many new stations one could achieve if the semiexpress train stopped at station i+1. Call it Q. Then, keep this value on a heap. After it, check the new number of stations you could achieve if, after it, you created a new stop at station i+1+Q and add to the heap again. Update the values of i and Q and repeat it at most K-M times (because it's the number of stops you can create), or until the value of i exceed the limits of the range you're analyzing.
After this, your answer will be all the stations one can reach with express and local trains plus the K-M greatest values of the heap.
Problem 3 — solution posted by kokosha
Observation 1 — Let's take a look at the point with the minimal value(X) and maximal value(Y). If these two values are inside the territory of JOI or IOI, we are done. So these two values are in different territories.
Now we have two territories, one with minimal value and the other with maximal value.
We can start the territory of minimal value in one of the four corners of the rectangle, or we can simply rotate the rectangle by 90 degrees. Let make the start point the left-top corner
Fact 1 — Suppose the value of answer is K, then the numbers in minimal value territory are less than X+K, and the numbers in the maximal value territory are bigger than Y-K.
Using this we can use binary search on the answer, using the following greedy algorithm.
Fix a column position, the rightest one, this will help us to generate the maximal value territory.
Now we will generate the minimal value territory.
For each row from top to bottom, find the leftiest position that satisfy less than X+K.
If the leftiest position is before to the column position, set the column position to the leftiest position and verify the maximal value territory from new column position to old column position and the rows below.
If the leftiest position is after or equal to the column position, set the leftiest position to the column position.
Credits to tozangezan — http://www.ioi-jp.org/joi/2016/2017-ho/2017-ho-t3-review.pdf
Waiting for comments
Waiting for comments
