antontrygubO_o's blog

Editorial of Codeforces Round #580
By antontrygubO_o, 5 years ago, translation, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +150
  • Vote: I do not like it

Comments Comments (105)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it +43 Vote: I do not like it

My last hour of yellow name :(

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

wow thank you for the fast editorial :D

→ Reply
»
5 years ago, # |
← Rev. 7   Vote: I like it +222 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +316 Vote: I do not like it

    The Chinese have a Data structure for everything.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it +51 Vote: I do not like it

      Nobody:

      Chinese people: Let's make a Data Structure based on this problem.

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    I think it is PQ-tree?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      no you can do it by segment tree

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it +11 Vote: I do not like it

      No, I think they look similar. PQ-tree tries to find a valid permutation with some given consecutive subsets, but “析合树” is to describe all consecutive subsegments of a permutation. The tree structure has two types of nodes, which are similar to Q-node and "P-node which is not Q-node" respectively. I mean, values of all sons of a first-type node (“合点”) are monotonic, and those of a second-type node (“析点”) form a simple permutation.

      I introduced the tree and an $$$O(n)$$$ algorithm to construct it for a given $$$n$$$-permutation on RAM (with linear RMQ). So that many such problems could be solved in linear time. For example, CF997E.

      In fact, this problem F could be solved in $$$O(n)$$$ time. We can make a valid permutation with at most $$$n$$$ items at first with greedy. After that, replace a leaf with remain items as a simple permutation. It's $$$O(n)$$$ by adjusting those conflicts of constant size (including corner cases of greedy, the extra one consecutive subsegment for the simple permutation and inexistence of a simple permutation of length $$$3$$$).

      Another similar structure I've ever seen is "separation tree for permutations". It only cares about the second-type nodes, and are for problems about simple permutations.

      A simple permutation is a permutation without consecutive subsegments.

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      If a PQ-tree successfully constructs a permutation, it can be regarded as a virtual tree for a subset of nodes in the permutation's “析合树”, each Q-node is a first-type node “合点”, and each P-node can be either type, “析点” or “合点”, depending on which permutation you choose in construction.

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    Problem setter & tester be like

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    I also solved it with $$$O(n^4)$$$ preprocessing with $$$O(n^2)$$$ per test case — I know how to improve this to $$$O(n)$$$ but I didn't bother. This is my idea, I have no idea why but it seems to work:

    If there is a solution for some $$$n,k$$$ then there is also a solution such that you start from some "disorderly" permutation of length $$$m \leq n$$$, and then in $$$n-m$$$ steps you either append a new maximum element to the permutation or append the new minimum to the permutation. A permutation of length $$$m$$$ is "disorderly" if its beauty is exactly $$$m+1$$$. I used dynamic programming to track the longest "increasing subsegment" suffix of the permutation, this tells me how many new good subsegments are added when the new maximum is appended. Code: 59129441

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    So my mans created his own data structure now

    → Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Consider taking some array from the circle. Then take next value and remove last value, on the same circle. The sum cannot stay the same, because that means what we removed and what we added is equal, and we cannot do that. So it either goes up or down by 1.

    Imagine sum increases by 1. We can write +1 near that number. After that, with same logic, next move has to decrease sum by 1, because increasing number twice gives us three numbers on blackboard: sum, sum + 1, sum + 2. So we can write -1 near that number.

    Now consider a circle with +1 and -1 instead of numbers. If it is odd, it starts and ends with same value — easy to see. And if it is even, is ends with different value and we are back at the sum. No two consecutive numbers (+1 or -1) must stay the same, as it is easy to see.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I didn't quite get the last paragraph of your answer, about the circle of -1 and +1. Can you elaborate a bit please? thanks in advance.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Let's create second circle of the same size, but with +1 or -1 inside, instead of numbers we put in. If it has length of n, we can label its nodes from 1 to n inclusive. Even ones have same sign, and all odd — labeled ones have different sign. The only place when it could go wrong is connection of n'th node to the first one. If they are both odd, they will have the same value, and we don't want that, as we showed. So 1 is odd and n has to be even

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          but the question asked to check in 1 to 2n. it doesn't matter if n is even or odd the last node and first will have a different sign. please explain why the n even is not possible??

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            Yes, the borders work well since the circle is of even length. But there is another problem with even n.

            Consider doing one step around the circle I mentioned. Let's denote sum of all numbers on the circle S, and previous sum in our chosen interval A. The sum of elements we have not chosen will be B = S — A. If we get +1 as result, new sum is A + 1. What happens to B then? Since S stays constant, new B = B — 1. If we choose the second interval as initial one, we would have to write -1 on the next node.

            So if we have +1 on one side, then we need to have -1 on opposite side (and vice versa). If n is even, we get two sequences (+1 -1 +1 -1 ...) (+1 -1 +1 -1 ...) of length n each. Their first elements will have the same sign, which is contradictory

            → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Iv got a simple proof for that.If input is n we have 2n numbers to arrange .the sum of these 2n nos is s=2n*(2n+1)/2 =n*(2n+1).since 2n+1 is always odd,s depends on n.now if n is even ,s can be divided in two equal parts(eg 18+18 for n=4) which we dont want as sum of no two consecutive n nos can not be equal.so n is odd.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it -40 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -20 Vote: I do not like it

    Why downvote? I post it because I am not able to understand why it is not printing all the $$$n$$$ strings. I had run the last for loop n times. But in the output it is printing only 3 rows. If someone can help then Please help!

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      probably your code print something other than 0/1 (-1 or something)

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    input :
    3
    -1 0 1
    output: 1
    yours: 3

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Currently, you are ALWAYS making 0 go to 1. However, 0 can also go to -1 for the same cost (1).

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I did it this way- The maximum number in the input is 10^18 which can be represented in 64 bits. The minimum possible cycle can be of length 3. If we have the xth bit set in any 3 numbers, then we are done! (all 3 will be mutually connected because of non zero "and") There are at max 64 bits. => If we have more than 128 non zero numbers (By PHP) in the array, then we will get a cycle of length 3.

    Now for <= 128 non zero numbers. We can check by actually making a graph. It will take O(m^2), which will be well within the bounds.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How do you come up with the "128 non-zero numbers" logic?

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        10^18 fits well inside 64 bits. We need a minimum of 3 set bits at any common position. By Pigeon Hole Principle if we have more than 64*2 = 128 numbers (non zero because zero has none of the bits set) then at least one of the position will have 3 set bits. (The bound of 128 can be made stricter if you calculate the exact number of bits needed to represent 10^18)

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks

          → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          how does having >128 numbers guarantee that there will be at least 3 numbers having set bit at the same position? (I'm not saying the answer is wrong, i wanted to know how php is used here)

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            in this problem Max(Ai) = 10^18 which has 60 bits, and as they said > 128 numbers guarantee that there will be at least 3 numbers having set bit at the same position.

            what if i change Max(Ai) = 7 then it only has 3 bits and > 7 numbers guarantee that there will be at least 3 numbers having set bit at the same position. how can it happen?

            here is the example N = 7

            4 4 2 2 1 1 4

            and then i convert all of them to Binary Form

            100

            100

            010

            010

            001

            001

            100

            sum of column: 3 2 2

            as you can see, at the last input, no matter what number you add (as long it <= 7), the sum of column will be >= 3

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              i had already figured it out but thanks!

              → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

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.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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...

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    OH I thought I have made some mistakes...

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Maybe I pasted some other test data by mistake... Finally I found out my fault, then I formed a bfs tree, to judge the size of rings by LCA！[submission:59058541]

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My solution 59056716 is very close to that, but I strangely recieved a WA on test 15, while I surely got the correct answer in codeforces custom invocation...

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Custom Invocation gives 5!=3.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Awwww I see... I'm going to keep debugging...

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thank you! Finally I formed a bfs tree and judge the size of rings by LCA！[submission:59058541]

        → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Given that you are getting WA on TC 14, it is probably because two values can share more than one bit, so the vector representation would have multiple edges going between the same two nodes, which would allow a cycle of length two.

    → Reply
»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +25 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I tried to implement Floyd in the contest but failed coz I discover a problem: say there's an edge u -> v, Floyd will find a cycle path of "u -> v -> u" coz this is an undirected graph. And I don't know how to counter this problem. Do you know if there's any tweak I can do to make Floyd work?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      http://codeforces.net/problemset/submission/1206/59043624 This is my solution.I hope it can help you.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks for the reply, is it ok for you explain these two lines of code?

            for(int i = 0;i < k;i++)
    for(int j = 0;j < i;j++)
        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          It's not quite easy to explain. It's just a way to avoid the situation you said above.

          → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Kindly explain the above lines if you have understood them!

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            This loop is essentially enumerating all the pairs that satisfies 0 <= i,j < k. The shortest path between any pair can only include Vertex 1 ... Vertex k — 1 according to the property of Floyd algo. So here we can enumerate all the cycles that contains Vertex 1 ... Vertex k. When k iterate from Vertex 0 to Vertex n, we basically covers all the possible cycles in the graph.

            → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please explain how to use Floyd's algorithm for finding the shortest path? (I read somewhere it couldn't be used for undirected graphs). It would be of great help. Thank You.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    "Now, if n is even, we get a contradiction, since ai+n−ai=−(a(i+n)+n−ai+n)ai+n−ai=−(a(i+n)+n−ai+n), but due to the alternating they must be equal."

    → Reply
»
5 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Problem B.Div2 is interesting.59065083 :D

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Instead of declaring vis and par vectors of size n every time in the loop, declare map of vis and par and for each iteration of loop, clear both the maps. Hope this helps.!

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah it helped, thanks. But yet I'm unable to understand why previous thing didn't worked.

      → Reply
»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Div1 D solution doesn't seem natural I think.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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 :)

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.)

→ Reply
»
5 years ago, # |
← Rev. 4   Vote: I like it +28 Vote: I do not like it

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

$$$ [ P ]= \begin{cases} 1, & \text {if P is true} \\ 0, & \text{if P is false} \end{cases} $$$

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

$$$Answer=\sum_{i_1,j_1\in [1,n-1],d=gcd(i_1,j_1)}([i_1+j_1-n\lt d]*k^{d-n}+[i_1+j_1-n\geq d]*k^{i_1+j_1-2n})$$$
$$$Answer=\sum_{d=1}^{n-1}\sum_{i_1,j_1\in [1,n-1]}[d=gcd(i_1,j_1)]([i_1+j_1-n\lt d]*k^{d-n}+[i_1+j_1-n\geq d]*k^{i_1+j_1-2n})$$$

using the inversion:

$$$[n=1]=\sum_{p|n}\mu(p)\ \ ,\mu(x)is\ Möbius\ function $$$
$$$gcd(a,b)=d\ <=>\ gcd(\frac ad,\frac bd)=1$$$

we can derive that

$$$Answer=\sum_{d=1}^{n-1}\sum_{i_1,j_1\in [1,n-1]}([i_1+j_1-n\lt d]*k^{d-n}+[i_1+j_1-n\geq d]*k^{i_1+j_1-2n})\sum_{p|gcd(i_1/d,j_1/d)}\mu(p)$$$
$$$\because p|gcd(i_1/d,j_1/d)<=>pd|i_1\ and\ pd|j_1$$$
$$$\therefore Answer=\sum_{d=1}^{n-1}\sum_{pd<n}\mu(p)\sum_{pd|i_1,pd|j_1}([i_1+j_1-n\lt d]*k^{d-n}+[i_1+j_1-n\geq d]*k^{i_1+j_1-2n})$$$

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

$$$Answer=\sum_{d=1}^{n-1}\sum_{pd<n}\mu(p)\sum_{i,j\in[1,\frac{n-1}{pd}]}([i+j\leq \frac{n-1+d}{pd}]*k^{d-n}+[i+j\gt \frac{n-1+d}{pd}]*k^{(i+j)pd-2n})$$$

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

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No!! There are at most 60 edges in a graph and removing each edge and doing bfs would cost me at most 60 operations . so overall our complexity would be (60)^2. You could have also used bellman ford for this but there time complexity would have been (60)^3 in worst case.

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    60 edges can connect at most 120 vertices. So rest of the vertices have zero degree, you don't have to do BFS on them. For example, you can do BFS on the connected component of source only. So my guess is, depending on the implementation the complexity may vary.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 9   Vote: I like it 0 Vote: I do not like it

    Define $$$dp[i][j][k]$$$ as the shortest path from $$$i$$$ to $$$j$$$ using upto prefix $$$k$$$ of vertices, then shortest cycle length is $$$dp[i][i][n]$$$.

    So basically you find the shortest path from vertex $$$i$$$ to $$$i$$$ itself. Make sure during initialization you set, $$$dp[i][i][k] = \infty, \forall k \in [0, n]$$$ and during transitions, avoid going from $$$i$$$ to $$$i$$$ through $$$i$$$(Well, actually this happens automatically if you set $$$dp[i][i][0] = \infty$$$).(Prerequisite: Basic version of Floyd Warshall)

    Setting $$$dp[i][i][0] = \infty$$$ is mathematical way of saying that there is no path from vertex $$$i$$$ to $$$i$$$ without going through any vertex.

    EDIT: This only works for Directed graphs, in undirected graphs, this won't work(Since each edge of Undirected Graph == 2-length cycle of Directed Graph), see explanation here, https://qr.ae/TWreWj

    → Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    I come up with an idea look at this :

    if dp[i][j][k][l]=1 means there is a Palindromic Paths from (i,j) to (k,l),0 otherwise.

    update: dp[i][j][i][j]=1,dp[i][j][i+1][j]=(a[i][j]==a[i+1][j]),dp[i][j][i][j+1]=(a[i][j]==a[i][j+1])

    if(a[i][j]=a[k][l])

    dp[i][j][k][l]=dp[i+1][j][k-1][l]|dp[i+1][j][k][l-1]|dp[i][j+1][k-1][l]|dp[i][j+1][k][l-1];

    else

    dp[i][j][k][l]=0;

    Do you think it's right?

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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$$$?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In the announcement they mentioned this :

    Note that the graph does not contain parallel edges. Therefore, one edge can not be a cycle. A cycle should contain at least three distinct vertices.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Useful for 1206C/1205A

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Cool.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    $$$n$$$ is odd.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Oh I see, you have made a small typo in the last line of the editorial, you have written (4, 4) instead of (n, n). I was trying to prove that there doesn't necessarily exist such path from (1, 1) to (4, 4) xd.

      → Reply