wrg0ababd's blog

By wrg0ababd, history, 4 weeks 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
  • +49
  • Vote: I do not like it

»
4 weeks 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

»
4 weeks 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.

  • »
    »
    4 weeks 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.

    • »
      »
      »
      4 weeks 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.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Amazing trick.. Why it's correct?

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

        Because multiplicative inversion is unique?

        • »
          »
          »
          »
          »
          4 weeks 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)

        • »
          »
          »
          »
          »
          4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

kkkkkkkkk.jpg

»
4 weeks 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

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

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

    • »
      »
      »
      4 weeks 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?

»
4 weeks 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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain me problem B please :"(

  • »
    »
    4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

can somebody explain problem E more clearly

»
3 weeks 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.

  • »
    »
    3 weeks 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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain problem B ?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

i didn't understand exactly what problem c wanted.Anyone there to help me 'bout this??

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to prove the point is only as much as $$$O(\log n)$$$ in problem G?