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.

More like

now imagine not winning a shirt.

You can ship it on flights, given they satisfy the maximum mAh criteria. And I guess 10000 mAh is pretty much fine.

Tell that to bootleg Chinese sellers on EBay.

If a[i] % m = a[j] % m for some i < j, then answer is 0. Otherwise there are <= m numbers, so you can calculate answer in O(N^2).

Wow the solution to today's problem had been written 2 years ago

Thanks, I was wondering why that felt so familiar.

The real lesson would've been to not have this covered by pretests.

I guess there is no rule as such.
Usually the problem setters are kind enough to let us know before-hand so that anyone who is new to such problems, will take a look at it. :)

oh wow so i will get WA since i just deleted all the possible brackets...... (()) would fail for me :/

I did the same mistake. My answer should fail on cases like () but got an AC instead

You should be grateful that the pretests covered it.

I FSTed. :(

It is more simple. Query two leaves, if response if one of those leaves, thats ans. Else remove those two leaves. Repeat.

this approach will fail if all the nodes are connected to the same node

If the output of interactor, say w, is not one of the 2 ends(say n1 and n2) then you remove the edges connecting w to n1 and n2. You find the longest diameter again and repeat the process.

I did something related to diameter of the tree.

You may notice you want to remove a lot of nodes, which are not candidates to be the root in each query, until you are left with one, which is done (fitting exactly in queries) by the approach in the editorial, too.

I, instead, went on querying the ends of the diameter, and removing all nodes (and of course all other nodes in "subtrees" of the diameter nodes, except the LCA returned in the query, because all of them except the "w" returned in the query, are no longer candidates to be the root as all of them have atleast one vertex "above" them), and continued to do so until I have one node remaining.

Pretty sure making strong tests for F is a difficult problem in and of itself. My shitty solution passed pretests, we'll see about tests.

I checked that for all N < M the answer is 0 but how to formally prove it ?

After staring at C for a good 20 mins, I had an epiphany. Pigeonhole principle! I smirked like the ninja in https://www.youtube.com/watch?v=pKO9UjSeLew

And then wrote m>=n in my pigeonhole condition instead of m>n

FML