rogerioagjr's blog

By rogerioagjr, history, 11 days ago, In English,

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?

Problem 1

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.

Code for Problem 1


Problem 2

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.

Code for problem 2


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


Problem 4

Waiting for comments


Problem 5

Waiting for comments

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

»
11 days ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

Problem 3

Observation 1 — Let's take a look at the point with the minimal value(X) and maximal value(Y). If this two values are inside the territory of JOI or IOI, we are done. So this two values are on different territory.

Now we have two territory, 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, than the numbers in minimal value territory is less than X+K, and the numbers in the maximal value territory is bigger than Y-K.

Using this we can use binary search on 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 leftiest position are 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 belows.

If leftiest position are 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

»
10 days ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

Alternately, you can use segment tree to solve P1 in .

Store answer for a range, leftmost value and right most value in a node. Combine can be done by adding individual answers and comparing rightmost element of left range and leftmost element of right range. Use lazy propagation for updates.

»
10 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem 4:

5 points is very easy.

35 points is O(N^2) dijkstra.
You can do that people is vertices, and edge is pair of people and cost can be calculated for N=2 case.

I'm sorry that I can't explain 100-point-solution because it is very hard to solve (I can't solve it).

»
7 days ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve the problem E?