Is it rated?

Wise decision to be honest. ;)

It's soooo real!lol(#ﾟДﾟ)

Hah,that's a serious problem. However,no matter whether you will get the T-shirts finally,wish you enjoy the competition!

How to make round with prizes not combined?

With <1% probability? You are the big optimist.

Wish you good luck!Hah( ´▽` )ﾉ

.

Good question. If only the name of the contest gives us that answer.

No, it is the first one.

It is going to be announced closer to the beginning of the round.

1) register for the contest in contests page
2) when contest starts, solve problems and submit them
3) after the contest your rating will be updated according to your performance

Yes you can.

No

:thinking:

Same here!

What is more! We can not ask the questions in the contest interface because of request status code 500 error!

Did you use late registration? I did, probably this is the source of bug

Same here! I cannot submit any task, but I want to participate in the lottery!

There is another contest tomorrow , you should be able to make it back.

turns out, i disappointed the cf rating formula enough with my initial 4 rounds that I'm still getting rating even with poor performance:(

Probably. I don't see any other way especially because it can be costly to even factor everything on the input.

Yes, choose any two element x, y, get all prime factor of gcd(x-1,y-1),gcd(x-1,y),..., gcd(x+1,y+1). Then try each factor. Each turn, you might get the correct answer with probability 1/4.

Upd: choose any element x, get all prime factor of x-1,x,x+1. Then try each factor. Each turn, you might get the correct answer with probability 1/2.

I don't know, but at least I solved with randomized solution.

My Randomized Solution

1. When $$$gcd = 2$$$, the number of operation must be less than or equal to $$$N$$$.
2. Let $$$t_i$$$ be the number of operation that made for $$$i$$$-th element of array. It means: $$$t_i = |a_i - b_i|$$$ when $$$a_i$$$ is initial array and $$$b_i$$$ is final good array. You can prove easily, that in at least $$$\frac{N}{2}$$$ element, $$$t_i \leq 1$$$.

3. Repeat 30 times as follows:

• Choose random index $$$i$$$ from $$$1 \leq i \leq N$$$.
• Let $$$t_{-1}$$$ be the set of prime factor of $$$a_i - 1$$$.
• Let $$$t_{0}$$$ be the set of prime factor of $$$a_i$$$.
• Let $$$t_{1}$$$ be the set of prime factor of $$$a_i + 1$$$.
• Let $$$T$$$ be the union of $$$t_{-1}, t_{0}, t_{1}$$$. For all value $$$v \in T$$$, check the minimum cost when $$$gcd = v$$$ with complexity $$$O(N)$$$.

Total Complexity is $$$30 \times O(\sqrt{a_i} + N)$$$. It fails with at most $$$2^{-30} \approx 0.0000000931322$$$% probability.

I am just curious how fo you generate these drawings they are really nice :)

Hint: Consider any $$$2$$$ leaves of the tree $$$u$$$ and $$$v$$$. Say $$$lca(u, v) = w$$$. Observe that $$$w \in $$${$$$u, v$$$} if and only if $$$w$$$ is the root.

We can always make gcd=2 by using <= n operations, so let's use only < n operations. Let's say we applied operation on i c[i] times in optimal answer, then at least for n / 2 indices c[i] <= 1(otherwise (n/2) * 2 >= n). So just pick some index i and try to prime divisors of a[i] — 1, a[i] and a[i] + 1. Not sure if it's good enough to fit into TLE though.

I think you can construct the answer. Maximum possible number of triples is achieved in sequences like x, 2x, 3x, 4x, ..., kx, and you can calculate how many triples you can get for each k. If m > this number for n, the answer is -1. Otherwise you take the biggest number k less or equal to n, such that m is bigger than the maximum number of triples possible for this k. The first part of the answer would be 1, 2, 3, ..., k. Then you can add just one number: something like 2*k — 2*(how many more triples you need to get m in total), and you satisfy condition for m. If there are spare numbers left (n — k — 1), you can add a sequence of type (big number) * x — 1, which does not produce any more triples.

For every query, pick 2 from the current graph having degree 1. If the LCA is equal to any one of the 2 nodes you queried for, it is the root! Else remove these 2 nodes from the graph and repeat the same process.