Отличный раунд получился. Больше всего понравилась задача Div 2E.

My last hour of yellow name :(

wow thank you for the fast editorial :D

F can be solved in $$$O(n^4)$$$. And I guess it can be solved in $$$O(n^2)$$$ per test case.

If $$$(a,b)$$$, then $$$(a+k-1, b+k)$$$ with $$$k\geq 4$$$ or $$$(a+k-1, b+k*(k+1)/2)$$$ with $$$k\geq 2$$$.

There is a tree structure about the permutation, which is called 析合树 in Chinese, named or invented by CommonAnts. We can derive this result directly from the tree structure. You can see these two 1 2 in Chinese for details.

And there are some similar problems with this combinatorial structure of the permutation, like NEERC 2018 I, and China Final 2018 B.

Fastest Editorial I have seen in a while! Thanks :)

I was able to solve Div2: C with some example that I wrote in the paper. I was trying to understand the derivation of editorial, but I am not able to understand it. Can someone please elaborate it more like why n even always has no answer?

Is the answer to the bonus of Div1.A yes when k is odd

Автокомментарий: текст был обновлен пользователем antontrygubO_o (предыдущая версия, новая версия, сравнить).

can someone please help me with my code. There is something strange.

Somebody pls check and tell what's wrong with my code for Div 2 problem B !! code

Can anyone explain how to solve problem Div2 D?? I am not able to understand the editorial...

For the problem, Shortest Cycle ,in the test case with n=10^5 and large numbers, making an adjacency list is causing Memory Limit Exceeded Error. How to prevent this?

Edit: Just note if too many edges (thus giving memory limit exceeded) then there is a triangle.

div1 a. i noticed a beautiful pattern by connecting numbers on circle sequentially. my solution was 0 3 4 7 8..., i.e., +3 +1 under modulo 2*n,now join 0->1,1->2..2*n-1->1and so on it makes flower like pattern on paper.really amazed after seeing that.

Thank you for your challenging problems and educative tutorials! But I was caught with some trouble at problem D... 59056716 I tested this submission with test 15 both on my local Windows machine and codeforces custom invocation. Both are resulted in 3. But every attempt to submit turned out to be Wrong answer on test 15...

For 1206 D, 1205 B Another way, If the no. of non-zero elements > 120 ( 2*log2(10^18) ) then we must surely have a 3-cycle. Otherwise, for all vertices v, do BFS traversal to find length of shortest cycle through v and take minimum. This will be in O(V*(V+E)) time and O(V+E)(max O(V*V)) memory. Not much efficient though.

Why am I getting WA on test 5 59056925 in problem D ? I think I misunderstood the problem. Can someone show me how the answer for test 5 is 4 ?

In Div-2D, can someone explain why using set as Adjacency list gives AC int the following code 59059506 whereas using Vector as Adjacency list gives WA in this code 59057776

Finally I left div2.. Nice problems, but solving them from smartphone is incredible as usual :(

For div2,D If the number of non_zero numbers is more than or equal to 119 ,we can just output 3.（Pigeonhole Principle,think of each bit as a pigeonhole,and think of each non_zero number as a pigeon） If it is less than 119,we can just use Floyd algorithm,we can solve it in O(n^3).

This might be a little bit easier to understand.

Can someone explain me the proof of div2 C,i basically did some cases and realized that if the number is even there is no solution, but i cant prove it.

Problem B.Div2 is interesting.59065083 :D

Hi could someone tell me why this is failing for "Make Product Equal One" https://codeforces.com/contest/1206/submission/59025115 locally I'm getting correct answer for the same input, is it some IO issue with Golang?

In Problem D, I first checked for the 3 length cycle case as given in editorial and then I'm finding the minimum length cycle for the other case by taking each vertex as root and seeing if it is in the cycle or not, cases with some non-zero inputs and n = 100000 are passing but the case with all zero inputs and n = 100000 is giving TLE. I'm unable to understand why in case of all zeros it is giving TLE.
Submission — 59060203

Can someone explain the first approach of div1C in more depth? Apart from the dp part. Thanks in advance.

Div1 D solution doesn't seem natural I think.

В конце "1205C — Палиндромные пути" написано алгоритм такой: выбрать любой путь между (1,1) и (4,4). Имелось в виду, видимо, между (1,1) и (n,n).

How can solve 1D in $$$O(n)$$$? I think "divide the subtrees of the childs into two groups" need $$$O(n\log n)$$$...

can anyone please explain the bit part I have no idea of binary represntation or bit may be thats why I didnt understand the solution. Can anyone please explain it easily from scratch. Sorry for my poor english. Thanks a lot :)

Many of you can't solve Div2 C. When you need to construct an array to solve a promblem,just construct it boldly. Don't be afraid.

For this problem, let v be some number of the array(a[i]),let v' be the number opposite v(a[i+n]). Then the circle was cut into halves.let s1 = a[i+1] + ... + a[i+n-1],s2 = a[i+n+1] + a[i+n+2] + ... + a[i-1]. if n is an even number,it means that 2 is a divisor of the sum of all numbers,let it be 2k. The sum of any n consecutive numbers must be k.So,v + s1 = k,v' + s1 =k.v = v'!It's impossible.

if n is an odd number,it means that the sum of all numbers can be written as 2k+1. Then |(v + s1) — (v' + s1)| must be 1.It means v — v' = 1 or -1. Just construct it boldly.I said to my self when I was trying solving this. What we want is for any i,s1 = k or k+1.Now we have n groups:(1,2)(3,4)...

Why not let s1 for v = 1 1 + 4 + 5 + 8 + 9 + 12 + 13 + ... ? (We choose the first one in the first group,second one in the second group,first one in the third group...)It can be proved right.

I won't write down the proof.(I didn't prove the algorithm at all when I was participating the contest,but luckily my thought was corret. :D )The proof was already given in the editorial.

(I'm a Chinese student,there might be some grammar mistakes.Please forgive me for this and upvote for me.Thanks.)

Div1 Problem E can be solved in the time complexity of O(n log n) with Möbius inversion formula : let define that

try to enumerate i1,j1 , whose gcd is d , and simplify the formula it with Möbius inversion now we have

using the inversion:

we can derive that

let $\ i\ ,\ j$ take the place of $$$\frac{i_1}{pd}\ ,\ \frac{j_1}{pd}$$$ we have

then we can enumerate$T=i+j$ the latter formula turns into some "calculate the sum of geometric progression" questions

the former two $$$\sum$$$ can be enumerated in $$$O(n \log n)$$$ the latter formula can be calculated in $$$O(1)$$$ with $$$O(n \log n)$$$ pretreatment

Can anyone pls prove this in Div1E?

The case of i1+j1≤n is obvious: in this case, by subtracting and adding i1,j1 we can show that the string has period gcd(i1,j1), in this case comps=gcd(i1,j1). We now consider the case when i1+j1>n.

Can someone help me figure out the complexity of D problem. There could be at max 60 edges and for each edge we perform a BFS to find the shortest distance between its end points. And there are n vertices, so total complexity of performing repeated bfs would be 60^2*(n+60). And in order to construct the graph the work would be n*(log10^18) so overall — n*(log10^18) + 60^2*(n+60). Could someone tell me if my analysis is correct. Thanks in advance.

Can anyone please explain to me how to find the shortest cycle using the Floyd Warshall's algorithm??

How does the checker work fast enough to determine whether there exists a palindromic path if I query distant points in Div.1 problem C?

Could anyone please explain the second solution of Div.1 C more clearly?

"Thus, the algorithm is as follows: choose any path between $$$(1,1)$$$ and $$$(4,4)$$$, find on it four cells with a xor of numbers equal to $$$0$$$, and ask a question about it."

Why does there exist a path from $$$(1,1)$$$ to $$$(4,4)$$$ such that the xor is equal to $$$0$$$?

for B wouldnt the answer always be 2 since if a[i] & a[j] != 0, then in the graph there will be an edge of weight 1 from i to j. since a[j] & a[i] != 0 as well. we will get an edge from j to i, which is a back edge of weight 1. this would mean the shortest cycle is of weight 2 always?

Useful for 1206C/1205A

Cool.

For div1.B, why does this TLE give TLE for input with 1e5 0s, which forms an empty graph, while this gives AC.

Could anyone prove an upper-bound of the answer to Div1D? Is $$$\frac{2}{9}n^2+O(n)$$$ optimal?

I did div2-E in the dp way, but I can't understand how there will always exist a path from (1, 1) to (4, 4) such that xor sum of 4 consecutive elements is 0. For example in the following matrix, there exists no such path from (1, 1) to (4, 4):

1 1 0 1
1 0 1 1
0 1 1 1
1 1 1 0

antontrygubO_o hate to ping you, but could you please clear this doubt.