Hello, Codeforces!
CS Academy will host the online mirror of Romania's IOI 2017 Selection Contests. The first contest already took place on Saturday.
The second round will take place tomorrow, Monday, 08/May/2015 06:30:00 (UTC). The round will be rated for all users. You will have to solve 3 problems in 5 hours. The statements will be available in English and Romanian.
The third round will take place on Wednesday. As for the first round, we'll host the online mirror on Friday. Rounds 4, 5 and 6 will take place in a few weeks.
Contest format:
- You will have to solve 3 tasks in 5 hours.
- There will be full feedback throughout the entire contest.
- The tasks will have partial scoring. The maximum score for each problem will be 100 points.
- There will be no tie breaker, so two users having the same total score at the end of the contest will share the same place in the standings.
If you find any bugs please email us at [email protected]
Don't forget to like us on Facebook, VK and follow us on Twitter.
Will virtual participation be possible with these rounds?
Yep. Just like for a regular contest :)
Man, what kind of programmers do Romanians select? This contest is soooo hard.
geniucos, Andrei1998 and AndreiNet were top 3 after the first selection contest. We need hard problems to break the tie between them.
Yep I know, I occasionally chat with geniucos about their contests. I just wanted to say that they must be really good to solve these problems, I can't do anything on them :D
They are, geniucos and Andrei1998 both got max score in the previous round.
or maybe you need hard problems to break them.
Can you describe your solution for the third task?
Solve it in O(N*M*log(N)) using some DP, then reduce the O(log) to O(log*), then reduce one dimension using the trick from IOI 2016 aliens ^_^ It's one of the nicest problems I've seen recently.
Reyna tried that trick, but it didn't work. Did you manage to get your solution accepted?
not yet, but I know the solution from the author of the task, bicsi . He promised me a beer if I can get it AC, so I'll probably code it soon. :))
Hello, I am the problem setter for Popcorn.
The official solution uses the linear binary search optimization trick seen at IOI 2017 Aliens, along with a data structure that will be described below:
Let DP[i][j] = the solution where we choose i points and we consider intervals that have the right end less than or equal to j. The recurrence is: DP[i][j] = maxx{DP[i - 1][x - 1] + C(x, j)}, where C(x, j) is the total weight of the ranges that have l ≤ x ≤ r ≤ j.
We use sweep line to calculate DP[i][ * ]. Let Val[x] = DP[i - 1][x - 1] + C(x, j) in our sweeping. When we go from j - 1 to j, we do 2 things:
The data structure should, at any time, give out the answer for maxx{Val[x]}.
Obviously, this can be done with a segment tree. Not so obvious is the fact that it can be improved with disjoint sets:
Notice that, if at any time we have Val[x] ≤ Val[y] with x < y, x will never be a solution anymore. We can keep a list of (strictly) decreasing values. However, we have to be able to append to the list and increment arbitrary suffixes of it. Appending is easy, and adding suffixes can be managed by keeping differences of consecutive elements (i.e., Incr[x] = Val[x] - Val[x - 1]). Note that for each increment, if at some time Incr[x] ≥ 0, we will "merge" x with the element right before it, adding its increment. If we use DSU for this process, we get an amortized complexity of O(n * log * (n)) for each step in our dynamic. Note that when appending to this increment array, you actually have to subtract the sum of the increments in the data structure to keep the property.
Obviously, the maximum value will be the first element of the list.
This is the solution in complexity O(n * m).
Obviously, this can be adapted to work with the binary search trick, giving a total complexity of O(n * log(109) * log * (n)) for 100 points.
Interestingly enough, the solution for 100 points has about 2kb source size and less than 100 lines of code.
Don't hesitate to give more info about this contest :D
Say Ans(k) is the answer for k bags. Then, because Ans(k) - Ans(k - 1) ≥ Ans(k + 1) - Ans(k), you can solve the answer for M boxes in the following manner (in short):
Consider a reduced problem, where you have an infinite number of bags, but taking a new bag has a cost λ. You can solve this problem in O(n * log * (n)) time, in a similar manner described above.
It is clear that, as λ gets bigger, the solution to the reduced problem will yield fewer bags. Now, because that inequality above is true, there always exists a λM for which the solution to the reduced problem yields M bags (this comes from the fact that no linear function of form Ans(i) - λ * i lies below the upper convex hull of all of them).
You binary search for that λM. After finding that particular λM, you just output the solution to the reduced problem, adding back the cost for the M bags (i.e., output ans + λM * M)
Of course, the algorithm of computing the solution to the reduced problem should also keep track of the number of bags used, which is not that hard.
This "trick" has been made famous by the IOI 2016 problem "aliens", which can be seen here: http://www.ioi-jp.org/ioi/2016/tasks/day2-aliens-ISC.pdf
By the way, on problem popcorn, there were two more 75-point subtasks (the most relevant ones) that were not included on csacademy's simulation of the contest. Here is a link of the problem with all the original subtasks (albeit in Romanian, not English):
http://www.infoarena.ro/problema/popcorn
Any hints on the first problem Meow? I didn't quite get the official editorial.