ouuan's blog

By ouuan, history, 9 days ago, In English,

1173A - Nauuo and Votes

Idea: ouuan

Tutorial
Solution

1173B - Nauuo and Chess

Idea: Sooke

Tutorial
Solution

1172A - Nauuo and Cards

Idea: QAQAutoMaton

Tutorial
Solution

1172B - Nauuo and Circle

Idea: Sooke

Tutorial
Solution

1172C1 - Nauuo and Pictures (easy version) and 1172C2 - Nauuo and Pictures (hard version)

Idea: ouuan

Tutorial
Solution

1172D - Nauuo and Portals

Idea: Sooke

Tutorial
Solution

1172E - Nauuo and ODT

Idea: ODT

Tutorial
Solution

1172F - Nauuo and Bug

Idea: rushcheyo

Tutorial
Solution

We had prepared a problem similar to 1174F - Ehab and the Big Finale before that round, so we needed to prepare new problems in four days. It was in such a hurry that there are some imperfections in our round. Please accept our sincere apology.

 
 
 
 
  • Vote: I like it
  • +161
  • Vote: I do not like it

»
9 days ago, # |
  Vote: I like it +12 Vote: I do not like it

someone please help with the proof of div2c/div1a

  • »
    »
    9 days ago, # ^ |
    Rev. 2   Vote: I like it +17 Vote: I do not like it

    The approach is that you have to play some blank cards in the beginning and then play the cards 1 to n in a row. So if you see by taking examples. Now suppose you are starting your moves for playing cards 1 to n. So what are the requirement: Card 1 present in hand. Card 2 present in hand or at the top of the pile. Card 3 present in the hand or at the top or the second from top in the pile ... and so on. Suppose some condition is violated, then we have to play blank cards to get the card i before its turn to play comes. That comes out to be pi — i + 1. If we play these many blank cards so the top of pile above this position are already in our hand. So the ans is max(pi — i + 1) + n. We add n for playing the cards 1 to n.

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you please explain how that p_i -i +1 come up? thank you

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        I thought like this. let element position is p[i] then before it's extraction i can have p[i]-1 element in correct position if it is present in our hand. Now that element position in sequence should be i, so to extract it i-p[i]+1 empty cards should be added. Please tell if I am wrong or u have some different observation

        • »
          »
          »
          »
          »
          8 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Your approach is totally cool.

        • »
          »
          »
          »
          »
          44 hours ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          can u please explain with some more detail explaination??

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

      Thank You for such a good explanation but can you please also explain if(p[1]) condition in above code? Thank You very much

  • »
    »
    8 days ago, # ^ |
    Rev. 5   Vote: I like it +9 Vote: I do not like it

    I viewed the Div2C from a different perspective, and ended up with the same solution.

    Let p_k be the 0-based index of card k. If card k is in our hand, then p_k = -1 . After our t-th move, we will receive the card located at index p_t — 1. Ideally, we would like for p_k + 1 < k, for all k; this means that we would acquire all of the cards "just in time" to play the them in order. In this case, the answer would be n.

    However, the p_k + 1 < k condition might not hold for all k. In order to remedy this issue, we can begin by playing a series of 0-cards. Note that playing a 0-card is optimal as a different action would send a non-zero card to the bottom of the deck. In essence, we would be decreasing the value of each p_k by z by playing z 0-cards at the beginning; the 0-cards would essentially be functioning as an offset. This means that we can rewrite our original inequality in the following manner: p_k — z + 1 < k. Via a bit of algebra, we find that p_k + 1 — k < z.

    Since we want to minimize the total number of cards played, it would be wise to minimize z. This can be achieved by finding the maximum value of p_k + 1 — k. Thus, our final solution would be n + max{p_k + 2 — k}, for k = 1,...n.

    Accepted Solution: https://codeforces.com/contest/1173/submission/55285031

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How did p_k + 1 - k become p_k + 2 - k in the last line?

      • »
        »
        »
        »
        8 days ago, # ^ |
        Rev. 4   Vote: I like it +1 Vote: I do not like it

        I have the same doubt

        • »
          »
          »
          »
          »
          6 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I guess it is because of the 0 based vs 1 based indexing.

      • »
        »
        »
        »
        6 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The value of z is constrained to the z > p_k + 1 — k condition. We can relax this condition by adding 1 to the right-hand side: z ≥ p_k + 2 — k.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it needs not that much proof...You can find that the ans will not larger than 2n,since you can just keep all the 1...n in the order from your hand(a[]) in less than n turns...and what you need is just to calc the turns you need when 0<=ans<=n or n<ans<=2n. The samples are good, it covers all the situation. You can find if your push 1 to n into the b[] from T turns,there are some limits to all the numbers.

  • »
    »
    7 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I think I got a very clean solution of this problem. https://codeforces.com/contest/1173/submission/55334637

    I check if there's an increasing subsequence from the start of the pile (from b[n-1] to b[0]), if there is, I go through $$$b[n-1]+1$$$ to n in a loop and I search if its possible to play out the entire deck without putting any zeroes in the pile.

    If there isn't an increasing subsequence, its also possible to play the deck without putting any zeroes, so I search from 1 to n. During this whole process every time I check for the deck, I also put another number from the top of the pile into the deck, if $$$num[i]$$$ is ever wrong, then that means that it is impossible to play out the deck without putting zeroes.

    If you can't play without zeroes, then the answer is simply the maximum amount of moves that you need to get all the numbers from the pile to the deck and into the increasing pile.

    11
    0 0 0 5 0 0 0 4 0 0 11
    9 2 6 0 8 1 7 0 3 0 10
    

    We have to add zeroes to the pile in this test case, so the maximum moves needed to rearrange the pile here is 11 (because you need at least n moves to completely rearrange the pile) and the maximum amount of zeroes that need to be added (a.k.a. how many operations do you need to wait for the right number to come to start piling increasing numbers). In this case that number is 3, as he sits on position i=9, so we need 9 moves to get him into the deck, but we can already start piling up increasing numbers after 7 moves because we already have the number 1 and 2 in the deck. So the answer is n+7, 18.

    If this could have done faster, let me know.

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

nice tutorial.

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

Can someone please give a less mathematical explanation of divison 2 problem B?

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The approach is pretty straight here, the aim is to minimize m given n pieces and if you see the inequality in an easier way, it is as follows: "The next piece should be at least 1 more row or column away from the previous piece, ie r = r + 1 or c = c + 1". So since you need to minimize the number of rows and columns of the chessboard. What you do is increase it alternatively. So if you visualize it is — (n/2) + 1. And the blocks are alternatively increasing the row or column number. Ex. 1-1 then 1-2 then 2-2 then 2-3 then 3-3.... until all pieces are covered. It will always minimize m.

  • »
    »
    9 days ago, # ^ |
    Rev. 2   Vote: I like it -8 Vote: I do not like it

    Well, if this number is divisible by 2, then you will not be able to put the numbers in the square with the n / 2 side, because even if you put 1 and n at opposite corners, the condition will not be fulfilled. If the number is odd, then similar reasoning for a square with a side (n — 1) / 2. How to put numbers in a larger square is clear from the code.

  • »
    »
    9 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Just put them in the pieces in the first row, then the last column. You'll notice that the Manhattan distance of the pieces always remains the same as abs(i-j).
    My Solution

  • »
    »
    8 days ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    Here's my formal proof for a greedy strategy for Div 2B.

    Note: The distance formula used in the problem is the Manhattan distance and I will just refer to it as distance for convenience.

    Let the cell on which we place our first piece (it must be piece number 1) be $$$S$$$. Let the cell which is farthest from $$$S$$$ be $$$T$$$.

    Lemma: Assuming that distance between $$$S$$$ and $$$T$$$ $$$\ge$$$ $$$n$$$, for any choice of such $$$S$$$, we can always find a sequence of cells to place all chess pieces.

    Proof: Formally, the distance between $$$S$$$ and $$$T$$$ is $$$R' + C'$$$ where $$$R'$$$ is the distance in rows only and $$$C'$$$ is the distance in columns only. Let's use the following strategy:

    We will always place the piece, with the next higher numbering, such that it is in either the same row or same column as the previous piece. Furthermore, this piece shall be placed such that it is closer to $$$T$$$ than the previous piece.

    Notice that this strategy will ensure that the distance between $$$T$$$ and the new piece will be $$$R' - i + C'$$$ OR $$$R' + C' - i$$$ where $$$i$$$ is the piece number. Furthermore, this strategy is feasible because the distance between the new piece and the previous piece is exactly $$$1$$$.

    We just keep applying this strategy until we have exhausted all our pieces. We will always be able to use all our pieces because $$$R' + C' \ge n$$$ as per our initial assumption. Q.E.D.

    Now, this is an optimal strategy because for any solution, the distance between $$$S$$$ and $$$T$$$ $$$\ge$$$ $$$n$$$. But we used exactly $$$n$$$ steps.

    To ensure that the assumption in our lemma holds for any feasible board size, we should choose $$$S$$$ to be the upper-left/upper-right/lower-left/lower-right corners of the board. This is because, this maximizes the distance between $$$S$$$ and $$$T$$$.

    From here, all we need to do is to find the minimum size of $$$m$$$ such that our assumption still holds. Notice that for our strategy, we require that that $$$2m - 1 >= n $$$ (Draw a diagram to see why). Solve this inequality to get the optimal value of $$$m$$$.

    In case you didn't understand my strategy, see my submission.

    Cheers. LTDT.

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

How to see on what pretest(input) the code gives wrong answer ?

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

Can someone explain to me how can we just take factorial of degree? I mean how are we assuring that there will be no intersections in any of those permutation? Like if node A has edges to X different nodes. Then if I swap any two nodes in X, how will not intersect? I hope my doubt clear.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    If you understand the dp solution, you can expand the dp formula, and get $$$n\prod\limits_{i = 1}^ndegree[i]!$$$.

    • »
      »
      »
      8 days ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Can you please elaborate the expansion and also the DP equation.

      As we are excluding the root shouldn't the factorial of (degree-1) be taken ?

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        $$$|son(root)|=degree(root)$$$, $$$|son(u\ne root)|=degree(u)-1$$$.

        • »
          »
          »
          »
          »
          8 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Then how come the answer of test case 1 is 16 and not 8(4 * 2! * 1! * 1!)

          • »
            »
            »
            »
            »
            »
            8 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            the degrees on test case 1 are 2, 2, 1, and 1.

            • »
              »
              »
              »
              »
              »
              »
              8 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              But for non root-node we should consider degree-1.

              Shouldn't we ?

              • »
                »
                »
                »
                »
                »
                »
                »
                7 days ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                You will have "degree" number of choices for the position of "non-root node". For instance, you have node A and its parent B. Firstly, you will have an arc containing A and its subtree on the circle and an edge coming from B to A, separating the arc into two parts. Therefore, you will need to divide A's children into two parts and put A between them. Since you have "degree-1" number of children, you will have (degree-1)! number of permutations times (degree) number of choices for A --> a total of (degree)! number of choices at A.

              • »
                »
                »
                »
                »
                »
                »
                »
                7 days ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                no, it's total degree for each node.

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

May someone please explain how m≥[n/2]+1 was derived for Div 2 B? Thank you very much.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    for any m you can place at max 2*(m-1)+1 i.e. all elements can be present in 1st column and last row. If you enter more than that number of elements condition will be violated

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

Can anyone please explain how the if(j > n) condition would ever be fulfilled in the editorial of div2c? Thanks in advance! :)

  • »
    »
    8 days ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    It means the loop exits not because of p[j] > j - i, but j > n.

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

Could someone explain me the problem 1172B — Nauuo and Circle, why if u is root then f[u] = (|son[u]|)! ... and when u is not root then f[u]=(|son[u]|+1)! ... .

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Because for the root, the arcs of its subtrees is in a cycle (the head and tail are connected), it's the same no matter where you put the root.

    For example: you put the root and each subtree in this way: 2, root, 3, 4, then changed root's place: 2, 3, root, 4, but the second one is the same as root, 4, 2, 3, 3, root, 4, 2 and 4, 2, 3, root.

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh! I got it. Thank you so much :3

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

Problemset was really clear other than question C (div.2).

»
8 days ago, # |
  Vote: I like it -18 Vote: I do not like it

Fucking div2 C (-_-)

»
8 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

plz someone explain div2D(nauuo and circle).

»
8 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Div1C is an extraordinarily nice problem and has a beautiful proof with this lemma. I had a time gradually transforming my solution from [2][M][M][M][N] to [2][M][N] complexity. Kudos for the problem.

»
8 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone explain the editorial of 1172B - Nauuo and Circle?

I could not get any part of it.

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

Could someone please tell the solution of div2c/div1a in a greedy way?I write a greedy one but it is wrong when I test it on my computer during the contest ): So I would like to know where are the bugs.Thanks.

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think greedy way only works when the ans is lower than n.

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

I didn't get the editorial for problem div2-D Nauuo and circle can anyone explain it?

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

ouuan

This problem can be solved by many data structures like top tree, link/cut tree or heavy path decomposition.

I am really curious what is it a top tree? Do you mean centroid decomposition?

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

Please, what kind of data may the 9th point of div1E be? I don't think my code has any difference with the solution, and it can also solve big data in time on my computer, but it is TLE with the 9th point, so I think there may be something special that I haven't thought. > <

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh it seems like my arrays are too small. Now it's OK.

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

Can someone please explain the swapping of a1 and ax, b1 and by in the solution of Nauuo and Portals (Div2.F) ?

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

Can someone prove the correctness of the tutorial of 1172A

»
5 days ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

My solution for Div2C/Div1A Nauuo and Cards The idea is that if you want to place a particular card at the bottom of the pile, you need to have it in your hand beforehand. The other major point to notice is that you'll have to place all the cards upto card n in a sequential manner. If you miss any 1 card from the sequence (cause you don't have it), you'll have to place and pick all the cards again (this time some different placing and picking pattern) until you reach at the same position and now you have the required card in your hand.

Another point to notice is that worst case would be to place all the zeroes in the sequence and pick all the n cards. After at most n operations, you have all the card from 1 to n in your hand, and you need more n operations to place it in a sequential manner.

We'll use the idea of binary search here. If the pile can be arranged in x operations, it can definitely be arranged in more than x operations. We need to find out the min value of x such that we are able to build the pile in x operations.

So this is how we check it for x operations :- If the pile can be built in x operations, x will always be greater than n(except for one corner case that I'll discuss later). So the last n operations would be to put all the cards from 1 to n in the pile. We'll talk about the last n operations. In the 1st operation of the last n operation (overall x-nth operation), we must be able to place the card '1' in the pile. This would be possible if the occurence (index) of card '1' in the array 'b[]' is less than (x-n) ,similarly for card 2, the index in array 'b[]' is less than x-n+1 and so on upto card n. We're just checking whether we have the card in hand or not before placing.

If this can be done using x operations, we'll check for operations lesser than x(using binary search)

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

I have never heard before that linkcut trees can maintain subtree sizes. Are there resources about cool operations that linkcut trees can perform?

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

    You can read this.

    I think you are able to read (Simplified) Chinese.

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

I think the result of $$$Div1$$$ $$$C2$$$ can be reached without a need for the inductive proof. Let the sum of initial weights be $$$Wbig_i$$$. Notice that the expected weight $$$Wbig_e$$$ of a picture with initial weight $$$Wbig_i$$$ of type $$$a$$$, is equal to the expected sum of weights of $$$c$$$ pictures (let this set of pictures be $$$s$$$) of type $$$a$$$, whose initial weights sum up to $$$Wbig_i$$$; This is because the calculation of the expected sum of weights ignores the individual values of weights and just considers the sum of weights (and you add/subtract 1 when visiting some picture, regardless of its initial weight).

And as the expected some of weights is equal to the sum of expected weights (basic probability), therefore $$$Wbig_e$$$ is equal to the sum of the expected weights of $$$s$$$. If all the pictures in $$$s$$$ have the same initial weights, then the expected weight of each of them is $$$Wbig_e/c$$$ (Because 2 pictures with the same initial weights obviously have the same expected weights).

Then we finally can get the expected weight $$$Wsmall_e$$$ of a picture of type $$$a$$$ with initial weight $$$Wsmall_i$$$, by finding a positive integer $$$d$$$ which divides both $$$Wbig_i$$$ and $$$Wsmall_i$$$, then $$$Wsmall_e$$$ will be $$$\frac{Wbig_e}{Wbig_i/d}\cdot\frac{Wsmall_i}{d}$$$, and we can always choose d to be 1.

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

    Yes, I know it's no need to prove it inductively. But I think the inductive proof is easier to write, and is also easier to understand for those who are not so good at probabilities.

»
43 hours ago, # |
  Vote: I like it +18 Vote: I do not like it

The alternative proof for the main lemma in 1173E2 - Nauuo and Pictures (hard version). Let's focus on a case where she likes all the pictures.

There are $$$n$$$ trees, the $$$i$$$-th of them has $$$w_i$$$ vertices. $$$m$$$ times you add a new leaf and attach it to a random vertex. A new vertex is either attached to one of the initially-existing vertices (then the p-bility is $$$w_i / \sum w_i$$$) or it is attached to one of already added vertices. This gives us a trivial proof by induction: if p-bility of adding a vertex to the $$$i$$$-th tree in previous steps is $$$w_i / \sum w_i$$$, then it's the same in this step when we attach the new vertex to one of vertices added in previous steps. So p-bility is $$$w_i / \sum w_i$$$ in every step.