### rng_58's blog

By rng_58, history, 17 months ago,

We will hold NIKKEI Programming Contest 2019-2.

The point values will be announced later.

We are looking forward to your participation!

• +52

 » 17 months ago, # |   0 Is it for only Japanese or all participants?
•  » » 17 months ago, # ^ |   0 For all participants. All rated contests in AtCoder will have English statements.
 » 17 months ago, # |   +1 Nice and interesting contest, thanks.
 » 17 months ago, # |   +16 How to solve C?
•  » » 17 months ago, # ^ | ← Rev. 2 →   +27 My solution is as follows:First check, after sorting $a$ and $b$, is $a_{i}\leq b_{i}$ for every $i$. If not, the answer is impossible.Note that, after sorting $a$ and $b$, if there exists some $i> j$, such that $a_{i}\leq b_{j}$, then the answer is Yes by simply putting the $N-1$ indices except $i$ and $j$ in place. So after checking the above cases, we need to arrange $a$ in a certain permutation, and to sort a permutation, for each cycle of length $l$ in the permutation, we need at least $l-1$ swaps. So it suffices to check if the permutation consists a single cycle of length $N$.
•  » » » 17 months ago, # ^ |   0 How comes this cycle thing with l-1 swaps?
•  » » » » 17 months ago, # ^ |   +5 For each swap you can decrease the length of the cycle by at most one.
•  » » » » » 17 months ago, # ^ |   +5 More generally you can break a cycle of length $L$ into two cycles of lengths $L'$ and $L - L'$ with one swap.
•  » » » 17 months ago, # ^ |   +5 Pardon me, but i am a bit confused about the 'cycle' thing, can you share your code?
•  » » » » 17 months ago, # ^ |   +3 For cycles, search 'permutation' on Wikipedia.My code: Code
•  » » » » » 17 months ago, # ^ |   0 Thank you!
•  » » » 17 months ago, # ^ |   +3 $i > j$ instead of $i \ge j$ rihgt ?
•  » » » » 17 months ago, # ^ |   +3 Ah, yes, fixed.
•  » » 17 months ago, # ^ | ← Rev. 2 →   -9 Do this operation at most $n-2$ times :for every $A[i]$, try to swap it with the maximum number $<=$ $B[i]$ in the range from $i$ to $n$ and lets denote it as $x$, so if $x$ equals $A[i]$ then don't swap the two numbers, else then swap them.Now, check for every index $i$ that $A[i]$ <= $B[i]$.
•  » » » 17 months ago, # ^ |   0 What is the proof of this method?
•  » » » 17 months ago, # ^ |   +15 i think for A =1,3,7 and B=4,8,5 it should be yes but yrs is giving no...
•  » » » » 17 months ago, # ^ | ← Rev. 2 →   0 can you still hack it after sorting both A,B according to B in non-descending orderso that A = 1, 3, 7 and B = 4, 5, 8 and it will produce a Yes
•  » » » » » 17 months ago, # ^ | ← Rev. 2 →   0 For A=5,8,6 and B=7,7,10. It should be YesEdit: Distinct numbers: A=1,5,2 and B=3,4,6By searching for this example I even found small bug in my submission which also passed systests XD
•  » » » » » » 17 months ago, # ^ |   0 actually I don't see how this would fail, we only need to swap at the 2nd pair, and the only number on its right to swap with is 2 which make a valid sequence of A = 1, 2, 5 and B = 3, 4, 6 so?
•  » » » » » » » 17 months ago, # ^ | ← Rev. 3 →   0 But his algo starts at first element of A, which is 1, and swaps it with 2 because 2 <= 3 and 2 != 1Edit: If you have some other solution in mind you can post the code and I'll try to find counterexample for itAnd for (A=1,7,3 B=4,5,8) his solution gives No, and you said it gives yes
•  » » » » » » » » 17 months ago, # ^ |   0 Yeah! Sorry that was a typo! [Fixed]The solution I'm trying to hack sorts pairs of A, B according to B in ascending order and only considers such indices where A[i] > B[i] and tries to find the maximal value of A[j] where A[j] <= B[i] and swaps! In case there are many such js choose the furthest maybe?I'm trying to hack it with no luck! So any help is appreciated!
•  » » » » » » » » » 17 months ago, # ^ |   0 A=5,2,1 B=2,3,5Your algo tries to make 2 swaps while (5-1) swap is enough
•  » » » » » » » » » 17 months ago, # ^ |   0 I see, so the only way to make this fail is to target the numbers of swaps! Thanks!
•  » » 17 months ago, # ^ | ← Rev. 2 →   +8 Sort $A$ and $B$. If $A_i > B_i$ for some $i$, the answer is No. Otherwise, if you can swap some two adjacent elements of $A$ such that the above inequality still holds for all $i$, the answer is yes [1]. Otherwise, look at the permutation needed to bring $A$ from its original order to the order where $A_i \leq B_i$, assuming we didn't change the order of elements in $B$. The answer is Yes if this permutation has more than one cycle and No otherwise.Note — the smallest number of swaps needed to sort a permutation is $n - c$, where $c$ is the number of cycles in the permutation. In [1], you can choose between some two permutations which differ by exactly one swap, and so they cannot both consist of only one cycle.
•  » » 17 months ago, # ^ |   +11 Suppose that $B_i \leq B_{i+1}$ and that we can achieve the required $n-1$ operations.If there is $x$ and $y$ such that $x \neq y$, $A_x \leq B_1$ and $A_y \leq B_1$ then any pairing between $A_x$, $A_y$, $B_1$ and $B_2$ is good. Therefore, we can ignore these and pair all the rest of numbers in at most $n-2$ operations.If there isn't any $x$ such that $A_x \leq B_1$ then obviously answer doesn't exist.Otherwise there is exactly one such $x$. If $x=1$ then we saved one operation and can can pair the rest of numbers in $n-1$ operations. Otherwise swap $A_1$ with $A_x$ and try to solve the smaller problem with $n-1$ pairs and $n-2$ operations.
 » 17 months ago, # |   +43 Will the editorial be translated to English?
 » 17 months ago, # |   0 How to solve E?
•  » » 17 months ago, # ^ |   +16 The construction is impossible if $K+(K+1)+\cdots+(K+2N-1) > (K + 2N) + \cdots+(K+3N-1)$. The above inequality is equivalent to $2K-2>N-1$.Otherwise, the construction is always possible. For example, if $K=4$ and $N=7$, $(4, 14), (5, 15), (6, 16), (7, 17), (8, 11), (9, 12), (10, 13)$ can be made into construction. That is, divide the numbers between $K$ and $K+2N-1$ into "middle half" and "non-middle half" and pair the numbers in ascending order.
•  » » » 17 months ago, # ^ |   0 Can you elaborate the splitting, it looks to me like you are pairing middle and first element increasingly then the rest of them and please do tell what is the main idea behind such splitting. "middle half" and "non middle" didn't quite get to me.
•  » » » » 17 months ago, # ^ |   0 The idea is trial and error, and in my AC solution, I first chose $\lceil\frac{n}{2}\rceil$ smallest and largest numbers and paired them, then paired remaining numbers similarly. I thought I would get AC by trying the method for various small value of $K$ and $N$.My AC code
•  » » 17 months ago, # ^ |   +5 I have another solution.First if k+k>n+1 ,there isn't a construction.Then just make the construction like this:(k,2n,k+2n),(k+2,2n-1,k+2n+1),(k+4,2n-2,k+2n+2)....the rest, just choose the first number in the construction from the left ,the second number in the construction from k+2n-1 to the left (of course they aren't used).Sort and match them with the rest numbers(bigger than k+2n and aren't used) from small to large.
 » 17 months ago, # |   +1 Can anyone explain B?
•  » » 17 months ago, # ^ |   0 Think of the tree being constructed from root to the nodes on deeper levels.You can place any node in the numer of places parent nodes on that level exist.So, the first node is the root node. All nodes on level 1 must be childs of the root node (on level 0), so there is only one possibiliy to place them.Every nodes on level 2 can be placed as a child of every node of level 1. So the posibilities are numNodes(level1) * numNodes(level2)The same is true for all other levels, too, so we need to multiply them.
 » 17 months ago, # |   0 Can anyone tell me how to solve F?
•  » » 17 months ago, # ^ | ← Rev. 3 →   +18 Really nice problem! I'll give the outline.of the solution. Firstly, note that by flipping each interior square, we alter the points that lie on two diagonally oriented rectangles (possibly degenerate, i.e. diagonals). There are $n+1$ such rectangles, and each interior point can be encoded with a pair $(a, b)$ denoting the rectangles they "flip" (we number the rectangles by their distance of the top vertex from the top left corner of the grid). Notice that $a, b$ have the same parity and are distinct. By flipping a point with code $(a,b)$, we flip the lights where at least one coordinate of their code is $a$ or $b$. Consider a graph on the numbers from $0$ to $n$ of the same parity. Our operation of flipping a light can be described as choosing two vertices $u,v$ and flip the edges with at least one endpoint $u,v$. A configuration of lights is nice iff the lights with the same code are consistent and there exist a sequence if operations to reduce our graph to the empty graph, where we start by drawing an edge between the numbers in the code of on lights. We claim that if our graph has $N$ vertices, then the task is always possible if $N$ is even, and the task is possible for $N$ is odd iff the degree of each vertex is even. The necessity can be proven simply by considering the parity of the degree of each vertex after each operation. To prove the sufficiency, firstly note that by performing operations on $(a,b),(b,c),(c,a)$ where $a,b,c$ are distinct, then we can flip only these 3 edges. For $N$ even, flip $(u,v)$ and then flip $(u,v),(v,w),(w,u)$ for all other $w$. This flips exactly one edge $(u,v)$. For $N$ odd, we claim that we can always flip an Eulerian cycle. Indeed, we can simply extend the cycle repeatedly by flipping a triangle. Finally, it remains to count such graphs. The $N$ even case is obvious. To count the $N$ odd case consider the graph of unfixed edges. For each connected component, we can choose the existence of all edges except a spanning tree (we need to be careful about the case where the sum of "degree" of all vertices in the component is odd if we consider only fixed edges, in which case the answer is $0$ since our unfixed edges can only alter the sum of degree by an even number). This gives an $O(n^2)$ solution.
•  » » » 14 months ago, # ^ |   0 Thank you.I think very long time about "the sum of "degree" of all vertices in the component is odd if we consider only fixed edges, in which case the answer is 0".See your explanation I finally understand.Thank for you much.
 » 17 months ago, # |   +6 Question B D1 = 0 is required for a tree to satisfy the condition, otherwise the answer is 0. In the following, D1 = 0. Consider one tree where the distance between vertex 1 and vertex i is Di, and for each vertex i other than vertex 1, let pi be the closest vertex to vertex 1 among the adjacent vertices. You can see that it is 1. On the other hand, if (p2, ..., pN) is defined such that Dpi = Di−1 (i ≥ 2), the tree consisting of the edges connecting vertex i and vertex pi is uniquely determined. Therefore, the number to be obtained is the number of (p2, ..., pN) where Dpi = Di-1 (i ≥ 2). When the number of i where Di = k is ck, the number is obtained by multiplying each integer i of 2 or more by cDi−1, so it can be obtained in linear time.Question C B1 ≦ B2 ≦ .... ≦ BN may be set by first arranging the elements appropriately. Suppose you want to rearrange (A1, ..., AN) with (Ap1, ..., ApN). In other words, the condition that Ai ≦ Bi in the end and the condition that the number of swaps is up to N−2 times, respectively, the condition that should be (p1, ..., pN) is as follows. Api ≦ Bi • When cyclic permutation (p1, ..., pN) is decomposed into cycles, it is decomposed into two or more cycles. First, take (p1, ..., pN) so that Ap1≤Ap2≤ ... ≤ApN. If Api ≤ Bi (i = 1, ..., N) does not hold at this time, there is no (p1, ..., pN) that satisfies the first condition, so the answer is No. Consider the case where Api ≤ Bi (i = 1, ..., N). If (p1, ..., pN) satisfies the second condition, the answer is Yes is. Therefore, it is sufficient to consider the case where (p1, ..., pN) consists of one cycle when it is decomposed into cycles. Here, if Bi
»
17 months ago, # |
+7
##### Solution to D using segment tree:

Observation: If you can move to point $i$ using cost $c$, you can also move to any point $j < i$ using cost $\le c$.

Therefore, we can sort the intervals by left-coordinate and apply each interval one at a time. Here, "applying" an interval $(L,R,C)$ means compute/store the optimum cost $c(L)$ to reach $L$, then set $c(R) = \min(c(R), c(L) + C)$. We know that by the time we reach $L$, we've already found its optimum cost, because we've already processed all intervals that could be used to reach $L$ (because we sorted them). Because of the observation above, we can compute $c(L)$ once we reach $L$ by taking $min(c(L), c(L+1), \ldots, c(n))$, and it's sufficient to store $c(L) + C$ to $c(R)$ specifically, instead of all indices between $L$ and $R$.

Runtime: $\mathcal{O}(N + M \log N)$

Code (L and R are 0-indexed here)
•  » » 17 months ago, # ^ |   +13 D is a well known problem,and one can search for countless solutions posted online.Many,sorry to say but it included myself,just copied the solution,modified the edge weight,and got AC.Perhaps problem setters should check for similar,or the same problems more carefully.
•  » » 17 months ago, # ^ |   0 Excuse me, but I am having problems with proof of the observation "If you can move to point $i$ using cost $c$, you can also move to any point $j < i$ using cost $\le c$."Can anyone give some mathematical proof?
•  » » » 17 months ago, # ^ |   +8 Consider the path that goes to $i$, then it "passes through" all points $\le i$, and our definition of the graph allows us to stop at any time during our trip to $i$.
•  » » » » 17 months ago, # ^ |   0 Get it. Thanks!
 » 17 months ago, # |   0 Can someone please help me to find why my solution does not work for problem C? I'm sorting by B and building a segment tree on A, and then for every Ai > Bi i search for some Bk >= Ai and Ak <= Bi and swap them, if there is no such Bk i try to find the Bj with the smallest Aj such that j > i and Bj >= Ai and Aj <= Bi.
 » 17 months ago, # |   0 Will test cases be posted?
 » 17 months ago, # |   0 Similar problems:D and BZOJ 3073(pay to access)both segment tree optimizing vertexes connecting