XVII Open Cup Stage 10: Grand Prix of Gomel takes place on Sunday, February 5, 2017, at 11:00 AM Petrozavodsk time.
The link to the contest. You need an Open Cup login to participate.
I'm the writer of all the problems.
This problemset will also be used at Barcelona ACM ICPC Bootcamp on Monday, February 6. Unfortunately, this means I have to ask you to refrain from discussing the problems in public until the end of the contest in Barcelona on Monday, 5:30 PM Barcelona time.
Let's discuss the problems here on Monday evening!
Hi, could you please give me more info about open cup?
I'm interested in participating since I'm free this Sunday.
Unfortunately based on what I read in this discussion, link, there is no simple way to get an Open Cup login :(
will this problemset be available for those who don't have authentication credentials?
Can somebody provide a link to live standings of Barcelona ACM ICPC Bootcamp contest?
http://opentrains.mipt.ru/~ejudge/workshops/
Is there some PDF/text file of the problemset publicly available?
The contest is over. How to solve B,D,E?
B. Suppose that we add x to the first two disks. Then for each pair of adjacent disks the number we should add to the pair can be represented as a linear function of x. Let f(x) = min(x%m, m - x%m). The problem is about minimizing the sum of a function of the form f(x) + f( - x + a) + f(x + b) + f( - x + c) + ..., and this is a standard task. Notice that we should add two cases (depending on the parity of n) separately.
D. Reduce it to a knapsack problem, where the cost and the volume of each item is up to 400. We want the total cost to be exactly x and we want to minimize the volume. When $x >= 400^2", we can choose "the most efficient one" greedily. After that do some DP.
A. The definition of the object we want to count look overwhelming — how to solve it?
F. We can see it as a game on two stacks. The critical case is when it's Appleman's turn, in both stacks the top is apple, and the two fruits at the bottom are different. In this case I assumed that he should always take an apple from the stack whose bottom is apple — how to prove this?
A: Let's look at some solution. Assume at some moment maximum used value is x and now you used value y < x. After this all values in (y + 1;x - 1) become "locked" — you can't use them. So we can just think we took value y, but maximum value becomes y + 1. It means that at any moment last value equals to maxValue or maxValue - 1. So we can consider following dp[position][maxValue][maxCan][difference] — we stay at some position, largest used number is maxValue, maximum number you can use now is maxCan (It's number of ascents plus 1). Difference equal 1 if last number you picked equal maxValue and 0 otherwise. This dp has O(n3) states and it's easy to calc it in O(n4) time. To reduce time to O(n3) you need notice some "add to prefix offline" parts in formulas and do it.
What is the solution for "the standard task" in B? I did not see this problem before. The way I solved may be a bit complicated.
For n odd: I get equation 2x = a (mod m). I solve for x using extended gcd. There are not many solns for x within [0, m) [at most 4]. So I try each of them and select the minimum.
For n even: I convert -x+a -> x+a'. Then I solve circular version of another standard problem: given location of some points in the circle, select a location so that, sum of distance from this point to other points is minimum. This problem can be solved using "kind of circular sweep".
Yes, I did the same thing for even n (f( - x + a) = f(x - a)). For odd n, we don't need extended gcd — such x is either a / 2 or (a + m) / 2.
In D: Do you mean digit-dp like dp? I mean, there are 400 numbers, each with weight 1, 2 ... 400. And there is cost associated with them as well. We need to make sum of weights x such that the cost is minimum. And probably it can be solved using digit dp like dp. Each time you fix lsb of the numbers, then the next one and so on.
Как решать задачу K?
Пусть у нас есть x вхождений некоторой буквы. Тогда расстояние между соседними не превосходит
. Поэтому если мы научимся провверять расстояние за O(xlogx) мы победим. Переберем расстояние. Запоним для каждого остатка все позиции с этим остатком. Переберем самый левый элемент, который мы не переместим. Кого тогда еще можно не двигать? Тех, у кого такой же остаток и кто попадает в определенный отрезок, начиная с этого элемента. Это можно проверить бинпоиском в списке с данным остатком.
How to solve E and I?
I: Let f(x) be the number of integers smaller than x, but lexicographically larger than x. For example when n = 2345, we want to compute f(1) + ... + f(2345).
Divide it into two parts: f(1) + ... + f(999) and f(1000) + ... + f(2345). The latter is harder. For a 4-digit number "abcd", we can prove that f("abcd") = (9 + 99 + 999) - 111a - 11b - c. Using this, we can compute f(1000) + ... + f(2345) by performing O(#digits) biginteger operations, so it will be O(#digits^2).
To make it faster, our goal is to represent the answer of the form a1 + a2 * 11 + a3 * 111 + ... using small integers a1, a2, ... (then we can get the decimal representation of the answer easily). It turns out that we can compute these coefficients using bunch of prefix sums and FFTs.
E:
Sort the people by their rating. Then we perform a sweep. We have the following querries: 1. update the sum on an interval 2. ask for the greatest sum that ever occurred on an interval
This can be done using a segment tree with lazy propagation. We need to store the following values in every node: current maximum in the segment, the best maximum that ever occurred in the segment, the sum that needs to be propagated to the subtree, the greatest sum of the propagation that ever occurred after the last time this node propagated to its children.
Now it is fairly simple to correctly maintain all of these values.
Did you get accepted?
Yes, he got.
How to solve C?
There is a paper about this problem. You may find the solution of the problem there.
Optimal canonization of all substrings of a string
And here is another paper in CPM 2016 about a more difficult version (range minimum cyclic shift) of this problem.
Minimal Suffix and Rotation of a Substring in Optimal Time.