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

xto 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 ofx. Letf(x) =min(x%m,m-x%m). The problem is about minimizing the sum of a function of the formf(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 ofn) 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

xand 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

xand now you used valuey<x. After this all values in (y+ 1;x- 1) become "locked" — you can't use them. So we can just think we took valuey, but maximum value becomesy+ 1. It means that at any moment last value equals tomaxValueormaxValue- 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 hasO(n^{3}) states and it's easy to calc it inO(n^{4}) time. To reduce time toO(n^{3}) 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 oddn, we don't need extended gcd — suchxis eithera/ 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.

How to solve E and I?

I: Let

f(x) be the number of integers smaller thanx, but lexicographically larger thanx. For example whenn= 2345, we want to computef(1) + ... +f(2345).Divide it into two parts:

f(1) + ... +f(999) andf(1000) + ... +f(2345). The latter is harder. For a 4-digit number "abcd", we can prove thatf("abcd") = (9 + 99 + 999) - 111a- 11b-c. Using this, we can computef(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

a_{1}+a_{2}* 11 +a_{3}* 111 + ... using small integersa_{1},a_{2}, ... (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.