wrg0ababd's blog

Codeforces Round #586 Editorial
By wrg0ababd, history, 5 years ago, translation, In English

Update: editorial for G is out

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
  • +39
  • Vote: I do not like it

Comments Comments (53)
| Write comment?
»
5 years ago, # |
  Vote: I like it +32 Vote: I do not like it

Another solution for F: first shift the permutation so that 1 becomes the leftmost element.

now the problem can be modeled like this: don't consider the first element(1). now we want to split the new array into two parts(maybe one of them is empty) so that to minimize the maximum depth of tree of the two parts.

so first build an RMQ on the array(we are not considering element 1). now we have a recursive O(n) algorithm to find depth of a subarray:

int get(int tl, int tr){
	if (tr<=tl) return 0;
	if (tr-tl==1) return 1;
	int mid=RMQ(tl, tr);
	return max(get(tl, mid), get(mid+1, tr))+1;
}

let P[i] be depth of prefix ending in position i. and S[i] be depth of suffix beginning in position i.

we know that: P[1]<=P[2]<=P[3]<=...<=P[n-1] and S[1]>=S[2]>=S[3]>=...>=S[n-1] we can use binary search to find the rightmost index i that P[i]<=S[i+1] and there exist an optimal answer thst we split the array to [1, i][i+1,n-1] or [1,i+1][i+2,n-1] so check both of them and find the answer:)

my solution:60808916

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

I think the complexity can be $$$O(n)$$$ in Problem D because you can find the lowest bit in $$$O(1)$$$ by bit operations. Just use lowbit function (It seems only Chinese call it lowbit?). This is my submission.

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

    I know there is an additional log complexity because of map, but you can use unordered_map instead of it.

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

      You can use something like $$$2^{i}$$$ % $$$67$$$ to avoid any maps here.

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

        Amazing trick.. Why it's correct?

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

        Because multiplicative inversion is unique?

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

          Yes.

          $$$2^x = 2^y \implies 2 ^ {x - y} = 1 \implies x = y$$$

          ($$$2^{-y}$$$ is unique and exists because $$$67$$$ is a prime)

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

          No, but because $$$2$$$ is a primitive root modulo $$$67$$$. As a consequence, all powers of two less than $$$10^{18}$$$ give distinct remainders modulo $$$67$$$, so there are no collisions.

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

kkkkkkkkk.jpg

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

consider k-th bit. An edge connects only vertices with different k-th bit, so partition is clear.

Can u explain me more

wrg0ababd

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

    Me too, didn't get this proof. I hope someone elaborate.

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

      What I get is that, Assuming initially B contained only odd edges, hence vertices would be pair of (odd, even) and hence even if you multiply by 2^k all the elements of B(equivalent to multiplying vertices by 2^k), the kth bit of vertices which was initially 0th bit(since multiplying by 2^k is equivalent to shifting) will be opposite(odd has 0th bit 1 while even has 0th bit 0).

      After this However I do not get the cyclic part. Can anybody help me with that?

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

        If you take some pair of numbers $$$(a, b)$$$ from B you can alwas find a cycle. Let's say you start at $$$0$$$ then you'll have the path $$$0, a, 2a, 3a, ..., lcm(a, b)$$$. From there you can decrease $$$b$$$ until you hit $$$0$$$ again.

        E. g., if $$$a = 3, b = 5$$$, you have: $$$0 \rightarrow 3 \rightarrow 6 \rightarrow 9 \rightarrow 12 \rightarrow 15 \rightarrow 10 \rightarrow 5 \rightarrow 0$$$.

        The length of the cycle length $$$len$$$ is equal to the number of ascending $$$a$$$ steps plus the number of descending $$$b$$$ steps. So $$$len = \frac{lcm(a,b)}{a} + \frac{lcm(a,b)}{b}$$$.

        From $$$a \cdot b = lcm(a,b) \cdot gcd(a,b)$$$, it follows: $$$\frac{lcm(a,b)}{a} = \frac{b}{gcd(a,b)}$$$.

        So $$$len = \frac{lcm(a,b)}{a} + \frac{lcm(a,b)}{b} = \frac{b}{gcd(a,b)} + \frac{a}{gcd(a,b)}$$$.

        If $$$a$$$ and $$$b$$$ are both divisible by the same power of $$$2$$$, then $$$\frac{b}{gcd(a,b)}$$$ and $$$\frac{b}{gcd(a,b)}$$$ are gonna be odd, so $$$len$$$ will be even.

        Otherwise, one of the terms will be even so $$$len$$$ will be odd.

        Finally, you can show that you can't have odd length cycles in a bipartite graph. So solutions won't have numbers with different number of powers of $$$2$$$ in the set.

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

    You can see it this way:

    • If you take any number $$$n$$$ and you add an odd number $$$z$$$, then $$$n + z$$$ is going to have its last bit flipped. That's because any odd number has its last bit set to $$$1$$$. If $$$z \in B$$$, $$$n$$$ will have an edge to $$$n + z$$$ in the generated graph. But since that always flips the last bit you can split all numbers in a set with last bit equal to $$$1$$$ and a set with last bit equal to $$$0$$$.
    • Now if you multiply $$$z$$$ by $$$2^k$$$, you know that this number will have its last $$$k$$$ bits set to zero. So $$$q = 2^k \cdot z$$$ will look like this: $$$\cdot\cdot\cdot10\cdot\cdot\cdot0$$$. So if you take some number $$$n$$$ and you add $$$q$$$ to it, the last $$$k$$$ bits won't change and the $$$k-th$$$ will always change. Given that in this case you started assuming that all number in $$$B$$$ were odd then if you multiply any of them by $$$2^k$$$ the resulting number will have exaclty $$$k$$$ zeros to its right.
    • Finally, if you generate the graph for this new set you can show that any pair of nodes $$$(a,b)$$$ that have an edge between, $$$a$$$ and $$$b$$$ have their $$$k-th$$$ bit flipped with respect to each other. So you can put all numbers with their $$$k-th$$$ bit set to $$$0$$$ in one set, and the rest in the other.
    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Thank you Orlandolsay.

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

      Excellent solution,but what about cycles formed from more than 2 numbers?for example: 1 3 6 1,it is formed due to numbers 2,3,5. In this case,the formula for length of cycle =lcm(a,b)/a+lcm(a,b)/b wont be valid right?

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

        Actually there are 2 arguments to be considered.

        (i) If all numbers in a set have same power of 2 in it's factorization then corresponding graph is bipartite.

        (ii) If any two number in a set have different powers of 2 in it's factorization then corresponding graph is not a bipartite.

        And argument you are making is related to second one. Where it suffice just to consider a pair of number.

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

Hi! Do check my editorial for $$$D$$$. This was actually written as editorial was not published before and lot were(including me) were facing problem in $$$D$$$.

Link

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

Can someone explain me problem B please :"(

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

    Let's denote the first three numbers in the array as a, b, c. Then the multiplication table has the following form: row1: 0 ab ac ... row2: ab 0 bc ... row 3: ac bc 0 ... So we do have the values of ab, ac, and bc given in the input. Then we can simply solve a system of equations with three unknowns and find the value of a. Then if we know a we can find all the other ones by simply going through the first row of the table and dividing all the entries by a. Hope it makes sense.

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

    HERE

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

Can anyone explain E better? What is the dp solution?

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

    See Ashishgup's solution for the problem (60806580)

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

      Can you please explain the working? Like, just an overview of the working of the code and what does the variables 'canTake', 'best', etc represent. It'd be really helpful.

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

        For any node that belongs to the cycle connected with the source, you can add its weight to canTake. Otherwise you can only visit only a path in the subtree of that node. We can only visit one such node. So, we keep the best variable to take the node that maximizes our answer.

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

can somebody explain problem E more clearly

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

In fact, problem F can be solved in linear time.Consider a new sequence b of length 2n:$$$a_1, a_2, a_3, ..., a_n, a_1, a_2, ..., a_n$$$, and build cartesian tree of it.Let T be the cartesian tree of b.

Observation 1: $$$a_{k+1}, a_{k+2}, ..., a_{n}, a_1, ..., a_k$$$ = $$$b_{k+1}, b_{k+2}, ..., b_{k+n}$$$.It can be seemed as a subsegment of length n of b.

Observation 2: The cartesian tree of $$$b_{k+1}, b_{k+2}, ..., b_{k+n}$$$ is a connected component of T.

Let b_i be the root of the connected component, which is the minimum number of $$$b_{k+1}, b_{k+2}, ..., b_{k+n}$$$. In order to the the maximum depth of cartesian tree of each subsegment, all we need to do is to get $$$d_1$$$:the depth of b_i and $$$d_2$$$:the maximum depth of $$$b_{k+1}, b_{k+2}, ..., b_{k+n}$$$ in T for each $$$1 \leq k \leq n$$$. According to Observation 2, the answer is $$$d_2$$$ — $$$d_1$$$.

Applying monotonic queue instead of RMQ, we can calculate these two things in linear time. Just get the minimum depth of them and find the answer.

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

    wait...why the observation 2 is correct? by the way, I think the T you build by the sample is : 1(0,5) 2(0,3) 3(0,4) 4(0,0) 5(2,6) 6(0,7) 7(0,0) but not all cartesian tree of $$$b_{k+1}...b_{k+n}$$$ is a connected compoent of it

    I must mistake your solution can you help me ? thanks a lot. :D

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

Can anyone explain problem B ?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it
    • If I know the value of any one element I can get the values of all the remaining elements.
            Example:
        M = 0 4 8
            4 0 8
            8 8 0
    • If I get the value of the first element, in this case, it is 2
    • I can get remaining elements from the first row: 2, 4 by dividing the first element with all the elements in the first row.

    • We can easily get the value of the first element

    • Let elements be a, b, c
             M = 0 ab ac
             ab 0 bc  
             ac bc 0  

         M[0][1] = ab, M[0][2] = ac, M[1][2] = bc 
         (ab * ac) / (bc) => a^2

    • Hence first element is sqrt(M[0][1] * M[0][2] / M[1][2])

    • My solution LINK

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

      Thanks so much bro , I read your explain after 6 months but it's really helpful , I didn't understand B from the editorial , but I understood it from you ,, I'm really thankful <3

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

Can someone please explain E with an example? The editorial is not clear to me.

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

    The graph may have some subtrees. If you enter a subtree, you cannot leave it.Therefore, the best solution would be to start by choosing two subtrees. One for you to start the tour and one for you to complete. Vertices that are not part of a subtree can be visited without any problem. therefore you will be able to visit all. Now you need to choose two paths. These paths belong to the subtrees. These paths should have the highest possible value. For each subtree, you can calculate the highest cost of each path using dynamic programming.

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

      Can you please walk me through an example for this problem. I've tried really hard to understand different solutions, but failed everytime. It's like i always get stuck somewhere. Thanks!

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

        did you understand the problem? He wants to visit the cities and maximize the cost. But, he can't use the edge twice in a row.

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

          Looking at this picture, do you agree that you can visit all the green vertices smoothly?

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

            Yes, I guess that I've understood the problem statement. And I do agree with you that he can visit all the green vertices, without any problem!

            But if he wants he can even take, ABMNJIH or ABMODFG or ABMKLNODFG etc. Is it not? I mean, it's not necessary that he has to return to the starting point at the end of the journey. Right or not? But he just could not pass again through the city that he has already visited before. Correct me if I'm wrong.

            PS: Sorry for the late reply

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

              You are allowed to visit any city multiple times.

              In this example, the best solution would be to get out of some red vertex, execute all green vertices, and end up in another red vertex. Alright ?

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

                Okay! Then?

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

                But wait! If we are allowed to visit a city multiple times, then is it not obvious that we can visit all the cities in some way? I mean that we can visit some city and then go back and like that we can visit every city.

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

                  Yes, there is a way to visit a (green) city several times. However, this is not possible with a red city. Because we can't use an edge twice in a row.

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

                  Oh!Okay! Got it. Then?

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

                  check your message box.

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

                  then what happened?

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

it is possible to solve F without segment tree. I solved it in O (n). Note that we can move 1 to the last position in the Array. We can then calculate the tree height on the left and right side separately for all positions where number one can occupy. accepted: https://codeforces.me/contest/1220/submission/63617810

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

For problem E, my solution is to cycle compress. So if a node is part of a cycle, mark the node as red. Then, merge all the red nodes together. Keep doing this until we get a tree. Then, solve the tree case. But this gives a wrong answer. Help?

138700167

→ Reply