### ouuan's blog

By ouuan, history, 23 months ago, 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

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. Tutorial of Codeforces Round #564 (Div. 1) Tutorial of Codeforces Round #564 (Div. 2) Comments (80)
•  » » 23 months ago, # ^ | ← Rev. 2 →   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.
•  » » » can you please explain how that p_i -i +1 come up? thank you
•  » » » » 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
•  » » » » » Your approach is totally cool.
•  » » » » » can u please explain with some more detail explaination??
•  » » » » I see it this way.If its position is p[i], then it takes p[i] operations for the card to end up in your hand. After than, while you were waiting for the card i, you could've played the cards before it, that is, you won't have to use cards numbered 0 to fill the deck for the i-1 cards in hand, thus p[i]-(i-1);
•  » » » » » 19 months ago, # ^ | ← Rev. 2 →   Your intuition is incomplete. If while waiting for card i to be dealt to you, you play the cards 1 to i — 1, the cards after card i may not be in your hand yet. So you may have to play even more blank cards. For example, your stack may look something like this (from top-to-bottom):Hand: 4, 0, 0 ... Stack: 6 5 [1 2 3]where 1, 2, 3 were the cards you just played while waiting for 4 (i.e. 4 was just taken out of the stack). When you play 4, you still have to play more blank cards in order to get card 5. So you will get something like this:Hand: 6, 0, 0 ... Stack: 5 [1 2 3], 4, 0Now you have to take out everything from the stack again because the order has been disrupted.
•  » » » » » » Since we know that a solution definitely exists, the problem is now to maximise the value of p[i]-(i-1) so that we get all the cards in a row.The example you gave is valid until we reach Stack when the value of p[i]-(i-1) is 3, the maximum possible value. Here 3 says we need to pick 3 cards before we can start adding them to stack.
•  » » » » » » » Yes. That's the complete explanation.
•  » » » Thank You for such a good explanation but can you please also explain if(p) condition in above code? Thank You very much
•  » » 23 months ago, # ^ | ← Rev. 5 →   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
•  » » » How did p_k + 1 - k become p_k + 2 - k in the last line?
•  » » » » 23 months ago, # ^ | ← Rev. 4 →   I have the same doubt
•  » » » » » I guess it is because of the 0 based vs 1 based indexing.
•  » » » » 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.
•  » » 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
•  » » 23 months ago, # ^ | ← Rev. 2 →   I think I got a very clean solution of this problem. https://codeforces.com/contest/1173/submission/55334637I check if there's an increasing subsequence from the start of the pile (from b[n-1] to b), 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.
 » nice tutorial.
 » Can someone please give a less mathematical explanation of divison 2 problem B?
•  » » 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.
•  » » » Thank you.
•  » » 23 months ago, # ^ | ← Rev. 2 →   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.
•  » » 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
•  » » 23 months ago, # ^ | ← Rev. 2 →   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.
 » How to see on what pretest(input) the code gives wrong answer ?
•  » » thats not visible
 » 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.
•  » » If you understand the dp solution, you can expand the dp formula, and get $n\prod\limits_{i = 1}^ndegree[i]!$.
•  » » » 23 months ago, # ^ | ← Rev. 2 →   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 ?
•  » » » » $|son(root)|=degree(root)$, $|son(u\ne root)|=degree(u)-1$.
•  » » » » » Then how come the answer of test case 1 is 16 and not 8(4 * 2! * 1! * 1!)
•  » » » » » » the degrees on test case 1 are 2, 2, 1, and 1.
•  » » » » » » » But for non root-node we should consider degree-1.Shouldn't we ?
•  » » » » » » » » 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.
•  » » » » » » » » no, it's total degree for each node.
•  » » » » » 10 months ago, # ^ | ← Rev. 2 →   Please can u explain Div1 B more elaborately?Thank you
 » May someone please explain how m≥[n/2]+1 was derived for Div 2 B? Thank you very much.
•  » » 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
 » Can anyone please explain how the if(j > n) condition would ever be fulfilled in the editorial of div2c? Thanks in advance! :)
•  » » 23 months ago, # ^ | ← Rev. 2 →   It means the loop exits not because of p[j] > j - i, but j > n.
•  » » » Oh, got it. Thanks!
 » 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)! ... .
•  » » 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.
•  » » » Oh! I got it. Thank you so much :3
 » Problemset was really clear other than question C (div.2).
 » 23 months ago, # | ← Rev. 2 →   div2 C (-_-)
•  » » real
 » 23 months ago, # | ← Rev. 2 →   plz someone explain div2D(nauuo and circle).
 » Div1C is an extraordinarily nice problem and has a beautiful proof with this lemma. I had a time gradually transforming my solution from [M][M][M][N] to [M][N] complexity. Kudos for the problem.
 » Can someone explain the editorial of 1172B - Nauuo and Circle?I could not get any part of it.
•  » » I have tried to explain my solution here.
 » 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.
•  » » I think greedy way only works when the ans is lower than n.
 » I didn't get the editorial for problem div2-D Nauuo and circle can anyone explain it?
 » ouuanThis 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?
•  » » A top tree is a tree structure of "top clusters". Consider a connected subgraph on tree, if there are only two vertices which have edges with outside, we call the subgraph "top cluster". Top trees have very strong ability but the whole top trees are very hard to implement in the contest. Instead we often use a simplified version called "the subtree maintaining tricks of link/cut tree". You can learn more on https://en.wikipedia.org/wiki/Top_tree.
 »
 » 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. > <
•  » » Oh it seems like my arrays are too small. Now it's OK.
 » Can someone please explain the swapping of a1 and ax, b1 and by in the solution of Nauuo and Portals (Div2.F) ?
 » Can someone prove the correctness of the tutorial of 1172A
 » 23 months ago, # | ← Rev. 3 →   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)
 » I have never heard before that linkcut trees can maintain subtree sizes. Are there resources about cool operations that linkcut trees can perform?
•  » » You can read this.I think you are able to read (Simplified) Chinese.
 » 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.
•  » » 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.
 » 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.
 » 22 months ago, # | ← Rev. 5 →   ouuan In problem Div.1 C, why doesn't this approach work? Consider you have the expected weights $e_i$ of each picture upto $m-1$ visits. With initial conditions, for $m = 0$, we have $e_i$ = $w_i$. We can update Expected values in the next visit by:For picture Nauo likes, $e_i = e_i + \frac{e_i}{\sum_{j=1}^n e_j}$ [previous E.V $+$ 1 * probability of getting this picture]For picture Nauo dislikes, $e_i = e_i - \frac{e_i}{\sum_{j=1}^n e_j}$ [previous E.V $-$ 1 * probability of getting this picture] We'll do this for $m$ times to get final $e_i$
•  » » Because the sum of weights is not fixed when the number of operations is fixed.
•  » » » 22 months ago, # ^ | ← Rev. 2 →   Why can't we use expected weights upto $m-1$ operations as actual weights to compute weights of $m^{th}$ operation? The expected values are just average weights after $m-1$ ops, right?
•  » » » I tried the same thing as S.Jindal, and I wasn't sure why it was incorrect. Each time through the loop I recalculated the sum of the weights using the expected values.
•  » » » » "Because the sum of weights is not fixed when the number of operations is fixed." doesn't mean I thought you didn't recalculate the sum of the weights using the expected values. This sentence is the reason why you can't use the sum of expected values to calculate. You can calculate the example test 3 by hand to see why it is wrong.
 » What if in Div 1 B the question was about a graph, not necessarily a tree
•  » » 10 months ago, # ^ | ← Rev. 2 →   Can anyone explain div1 B ? Thank you
•  » » » I have tried to explain my solution here. Hope it helps.
•  » » » » Thank you very much