XVIII Open Cup Grand Prix of Gomel takes place on Sunday, February 18, 2018, 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. Let's discuss them here after the contest!

Do you believe in extraterrestrials? what if they appear and ask you to find ramsey 5,5 number? what will you answer?

After some csacademy rounds, I thought that the best are minimalistic statements, but even tourist can write cute problem stories :)

How to solve B?

First note you need to maximize subject to (here

x_{i}is the number of ones inf(a,i)). Now increasing ax_{i}by one 'costs'i·2^{xi}. Binary search over the maximum cost that you use.Is there greedy first binary search for i = 1 find max

x_{1}then maxx_{2}for n — 2^{xi}+ 1 and so on...?No, you binary search over the maximum cost for which you use 'all options'. To check if

mis possible, check if (here counts the number ofifor whichi·2^{x}≤m). After the binary search you can use whatever you have left for options which cost exactly one more.Could you share the feeling when you see no Chinese team solved the problem J?

Lol, you guys should write some problems about Mahjong hands evaluation :)

(Note to readers: this contest first appeared at Chinese Winter Camp two weeks ago. 25 teams, 0 submissions for problem J.)

Well, I anticipated that it could go either way :) Such a scenario was more likely with Chinese teams -- Russian-speaking participants are more familiar with this game, even though this particular modification is made up by myself and obviously not played by anyone.

If you ask about feelings -- I was slightly worried that the problem statement was difficult to understand. In Petrozavodsk & Open Cup the first correct attempt came in during the first hour, and then a dozen of non-Russian-speaking teams solved it as well, so hopefully it was good enough.

We spent 40 minutes to understand rule of "Fool's Game".. Do Russian competitors know it already?

Yes, but it's modified. If second has 2 jokers, he loses, otherwise he wins by taking all cards that first tosses until first only has jokers.

Is there any simple proof? We solved J without any proof :(

As I said, if second has at most 1 joker, his optimal strategy is to never cover and always take cards that first tosses at him. This way first always tosses. In the end the first will take all cards from the deck, so he surely will have at least one joker, which he can't toss, so he will lose. If second has both jokers, then if he always takes cards, then first's hand will get empty in the end, and if he covers at least once, first can use similar strategy and only take cards for the rest of the game.

In Russia it's a well known card game called "Дурак" ("durak").

If I were to choose a card game that every single native speaker of Russian knows the rules of, Durak would be my bet.

How to solve G and K?

K: Factorize

Nfirst. Then, inclusion-exclusion works inO(3^{k}), wherekis the number of distinct prime divisors ofN. It's first enough.The main challenge is the factorization. Check all divisors up to

N^{1 / 3}. Then there are three cases:N=p^{2}(we computesqrt(N) and check)N=p(use BigInteger.isProbablePrime in Java, not sure if this is intended)N=pq(otherwise this holds, we are not interested in the values ofpandq)Could you explain about inclusion-exclusion more detailed?

Suppose that

N=p^{a}q^{b}. We want to choose a subset of divisors ofN. But there are four things we want to avoid:p.p^{a - 1}.q.q^{b - 1}.Now we get an

O(4^{k}) inclusion-exclusion.To make it

O(3^{k}), notice that "choose (1) and not choose (2)" and "choose (2) and not choose (1)" are equivalent (and the same holds for (3) and (4)).Why N is

p^{a}*q^{b}but notp_{1}^{a1}* ... *p_{n}^{an}?I assumed that

k= 2 just for simplicity, it works for generalk.Here is more or less strict detailed formulation. Assume

n=p_{1}^{a1}...p_{m}^{am}.All numbers in considered set must be divisors of

n. Let's calculate number of subsetsg(n) we can take having only equals 1. That means that for each numberp_{i}we should take at least one number havingp_{i}with only power of 0 in its factorization. let's denote set of all sets that contain at least one such number forp_{i}byN_{i}. Then we have to calculate intersection of such sets:Here denotes set of all sets that do not contain any number having

p_{i}with power 0 in factorization. For single numberiholds where is simply number of divisors ofn.Indeed, we shoud choose some divisors of

nsuch that they all are divided byp_{i}, thus we can first dividenbyp_{i}, choose arbitrary subset of divisors and multiply them backwards byp_{i}. After that we subtract 1 to vanish empty set. And for intersection of such sets we have:Thus answer can be reformulated as Dirichlet convolution using Möbius function:

Now if we would like additionally calculate number of subsets

f(n) having equalsnwe can write it with quite similar formula:Since Dirichlet convolution is associative, we can just calculate

Where is Dirichlet convolution of Möbius function with itself. It can be found out that is multiplicative function defined in the following way:

This allows you to solve the problem in .

such hard maths. from where you learn.

Wikipedia

How to solve D and I?

Gaussian binomial coefficient and line graph recognition.

Line graph recognition lol

Now I'm curious how MSU team solved it. Did they derived it from scratch?

It's not so hard to come up with some process building the answer. Something like "take an edge

uv, assignxyandxzto its endpoints, realize which neighbors can havex,y,zandyzlabels..". I can share my code which received OK after about one and a half hour of debugging with stress after the contest in Petrozavodsk. Also I can explain the ideas behind my solution if you are still interested, but maybe guys from Red Panda had simpler approach.Yes, basically I expected the contestants to come up with a similar process. From a fairly large number of submissions, it seems that many teams actually did that.

Unfortunately, the devil is in the details, and most teams failed on test cases 4 and 5, which are line graphs of graphs with a lot of small connected components. The only team besides MSU Red Panda who managed to get past them was team Ural FU 1 -- they ended up with WA 35.

One way to deal with ambiguities, which actually only happen in the beginning of the process, is doing a brute force search until the current connected component is large enough. Definitely it's also possible to analyze these ambiguities on paper.

Let

q= 1 -pandr=p/q. It's easy to see thatf(k) corresponds to the coefficient ofX^{k}of the polynomialP_{N}(X) = (1 +X)(1 +rX)(1 +r^{2}X)...(1 +r^{N - 1}X). So we want to evaluate this polynomial.Use the following (and FFT):

P_{N}(X) =P_{N - 1}(X) * (1 +r^{N - 1}X)P_{N}(X) =P_{N / 2}(X) *P_{N / 2}(r^{N / 2}X) (in caseNis even)In fact, no FFT or polynomials are needed as there is a simple formula for

f(k).If we call

G(N) = (1)(1 +r)(1 +r+r^{2})...(1 +r+ ... +r^{N - 1}), then .Why the formula of f(k) looks like this or the one from rng_58's post?

For my formula: simple calculation shows that the probability that the set of people with indices {

a_{1}, ...,a_{k}} beats everyone else isr^{a1}* ... *r^{ak}*C_{k}, whereC_{k}is a constant that depends only onn,k,p. Thus, we are interested in the value ofIf we get

s_{k}for eachk, we can getf(k) =C_{k}s_{k}.s_{k}is the coefficient ofX^{k}in the polynomial above.UPD: Now, search "There are analogs of the binomial formula" here.

How to solve H and J?

For problem H:

Assume a < b. If n is even while a, b are odd, then there is no way to complete the journey as you can never travel between two even numbers consecutively by walking or jumping.

Otherwise: if a is even, a valid path with three jumps is

Similarly, when n is odd, the following is valid

and when b is even, the following is valid.

We will also need to check if there are shorter paths, and deal with special cases like b = a+1, b = n, a = 1, etc. The number of possibilities to check will still be O(1).

I've already posted solution sketches in a separate comment, but I'd just like to make a special note here (for those who don't get to read it) that a solution without case analysis, at least in the implementation part, is possible.

How to solve G?

Great chance to know about tourist's musical taste

I'm kind of curious about case 64 in problem K. Was it designed to break integer factorization in ? (My squfof breaks on it and I could't break it with various random tests.) Did anyone try pollard-rho?

Test case 64 in problem K is 999949000866995087 = 999983

^{3}. Yes, I've seen a bunch of accepted solutions using Pollard's rho.Can you give me please the 33

^{th}test? I don't know why but I get TLE on it (in Go) while all others pass in less than 30 ms.This is the first test case with a lot of distinct prime divisors: 914836017997511610.

Please find a brief summary of solution ideas here. Feel free to ask if you have any questions.

Could you explain in problem G how to find intersection of semiplanes in O(n) and tricky moment with "all semiplanes intersect any line x=d at some integer y" more detailed?

In general, half-plane intersection is similar to building convex hull. One possible way to go is to separate half-planes into "upper" (covering point (0; + ∞)) and "lower" (covering point (0; - ∞)), sending "vertical" half-planes into either category (there are none in this problem, though). Then, in each category, sort half-planes by polar angle and perform a scan with stack removing unnecessary half-planes -- this is similar to Graham scan. Finally, we have two polylines and by finding their intersection points we obtain the resulting polygon. Of course, in general case this "polygon" might have infinite area, so additional care must be taken (luckily, it never happens in this problem).

This algorithm works in due to sorting, but the scan part works in

O(n). In this problem, since the half-planes are sorted naturally -- their normals look like (i- 1;1) forifrom 1 ton-- there is no need in sorting, so the whole algorithm works inO(n).For the second question, when I said "all half-planes intersect any line

x=dat some integery", I actually meant "half-plane borders" not just "half-planes". Consider any half-plane border, for example,a_{1}+d·(i- 1) =r_{i}. This is equivalent toa_{1}=r_{i}-d·(i- 1). The right part is integer whendis integer, hence the left part is integer too.How does it help in this problem? We have found a polygon representing the intersection of half-planes and we want to find the number of integer points inside it. Let's move with two pointers from left to right and divide it into

O(n) trapezoids with legs formed by two of the given half-planes and bases parallel toOy(well,Oa_{1}). Consider one such trapezoid. Since we are only interested in integer points inside the trapezoid, let's shrink it a bit in such a way that its bases have integerx=d. And now the coordinates of vertices of this trapezoid are all integers -- exactly since both legs intersect linex=dat some integery. Now, for example, you can use Pick's theorem to find the number of integer points inside the trapezoid, but actually this number is just the sum of an arithmetic progression, since at every intermediate integerx=dtrapezoid's legs have integer intersections as well.guys where can i see the problem statements??

The statements will appear here after some time (down on left side in russian is written to choose the stage) but you won't be able to submit problems unless you have an account.