When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

rng_58's blog

By rng_58, history, 4 years ago, In English

We will hold NIKKEI Programming Contest 2019-2.

The point values will be announced later.

We are looking forward to your participation!

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

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

Is it for only Japanese or all participants?

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

    For all participants. All rated contests in AtCoder will have English statements.

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

Nice and interesting contest, thanks.

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

How to solve C?

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +27 Vote: I do not like it

    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$$$.

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

      How comes this cycle thing with l-1 swaps?

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

        For each swap you can decrease the length of the cycle by at most one.

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

          More generally you can break a cycle of length $$$L$$$ into two cycles of lengths $$$L'$$$ and $$$L - L'$$$ with one swap.

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

      Pardon me, but i am a bit confused about the 'cycle' thing, can you share your code?

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

      $$$i > j$$$ instead of $$$i \ge j$$$ rihgt ?

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

    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]$$$.

    my submission

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

      What is the proof of this method?

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

      i think for A =1,3,7 and B=4,8,5 it should be yes but yrs is giving no...

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

        can you still hack it after sorting both A,B according to B in non-descending order

        so that A = 1, 3, 7 and B = 4, 5, 8 and it will produce a Yes

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

          For A=5,8,6 and B=7,7,10. It should be Yes

          Edit: Distinct numbers: A=1,5,2 and B=3,4,6

          By searching for this example I even found small bug in my submission which also passed systests XD

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

            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?

            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
              Rev. 3   Vote: I like it 0 Vote: I do not like it

              But his algo starts at first element of A, which is 1, and swaps it with 2 because 2 <= 3 and 2 != 1

              Edit: If you have some other solution in mind you can post the code and I'll try to find counterexample for it

              And for (A=1,7,3 B=4,5,8) his solution gives No, and you said it gives yes

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

                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!

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

                  A=5,2,1 B=2,3,5

                  Your algo tries to make 2 swaps while (5-1) swap is enough

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

                  I see, so the only way to make this fail is to target the numbers of swaps! Thanks!

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

    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.

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

    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.

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

Will the editorial be translated to English?

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

How to solve E?

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

    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.

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

      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.

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

        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

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

    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.

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

Can anyone explain B?

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

    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.

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

Can anyone tell me how to solve F?

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +18 Vote: I do not like it

    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.

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

      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.

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

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 <Api + 1 (i = 1, ..., N−1), there is only (p1, ..., pN) cyclic permutations that satisfy the first condition. The answer is no. On the other hand, if there is i such that Bi ≧ Api + 1, the cyclic permutation of (p1, ..., pi−1, pi + 1, pi, pi + 2, ..., pN) The answer is yes. All of this is done, so you can ask for an answer. The time complexity is O (NlogN) because it sorts.

D: Shortest Path on a Line You can see that d1 ≦ d2 ≦ .... ≦ dN, where di is the length of the shortest path from vertex 1 to vertex i. Therefore, even if a zero-length edge is added from vertex i + 1 to vertex i for each i, the length of the shortest path from vertex 1 to each vertex does not change. In the following, it is assumed that all these edges are included in the graph. Considering the edge added at the i-th time, if you add an edge of length Ci from vertex Li to vertex Ri, the other edges do not affect the shortest path. This is for a vertex s, t with Li ≦ s <t ≦ Ri, there is a zero-length path from s to Li, there is a side of length Ci from Li to Ri, and length 0 from Ri to t Since there is a path, we can see that there is a path of length Ci from s to t. From the above, it can be seen that the shortest path from vertex 1 to each vertex can be found by considering only N + M−1 edges. Therefore, the Dijkstra method can be used to solve with a time complexity of O ((N + M) logN).

»
4 years ago, # |
  Vote: I like it +7 Vote: I do not like it
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)
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    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.

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

    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?

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

      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$$$.

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

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.

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

Will test cases be posted?

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

Similar problems:

D and BZOJ 3073(pay to access)

both segment tree optimizing vertexes connecting