maroonrk's blog

By maroonrk, history, 23 months ago, In English

We will hold AtCoder Regular Contest 140.

The point values will be 300-400-500-700-800-900.

We are looking forward to your participation!

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

| Write comment?
»
23 months ago, # |
  Vote: I like it +23 Vote: I do not like it

Wish me luck.

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

randomization can't solve problem E >3

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    sure? this problem with c=3, n<=10 was in russian regional olympiad several years ago and proper solution is randomization

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone else got WA on 1 test case in C?

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Took almost an hour to realize it was |P[i]-P[i+1]| instead of P[i]-P[i+1] in C lmao

»
22 months ago, # |
  Vote: I like it +20 Vote: I do not like it

Bonus: the solution to problem E can be slightly modified to obtain a $$$625\times 625$$$ board. Can we construct a greater square board?

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    I can't do better with a square board, but I think $$$625\times 650$$$ is possible. Identify the labels with elements of the finite field $$$\mathbb{F}_{25}$$$, the rows with ordered pairs $$$(u, v)\in \mathbb{F}_{25}^2$$$, and the columns with tuples $$$(a, b, c)\in \mathbb{F}_{25}^3$$$ where $$$(a, b)$$$ is restricted to the set $$$\{(1, x) \mid x\in \mathbb{F}_{25}\}\cup \{(0, 1)\}$$$. Then the label at the intersection of $$$(u, v)$$$ and $$$(a, b, c)$$$ is $$$au+bv+c$$$.

    Let's choose distinct rows and columns $$$(u_1, v_1), (u_2, v_2), (a_1, b_1, c_1), (a_2, b_2, c_2)$$$ and suppose that the corners all have the same label. If $$$(a_1, b_1) = (a_2, b_2)$$$ then $$$c_1\neq c_2$$$, so $$$a_1u_1+b_1v_1+c_1 \neq a_2u_1+b_2u_1+c_2$$$, i.e. the corners don't have the same label. Otherwise, $$$(a_1, b_1)\neq (a_2, b_2)$$$ so then $$$(u_1, v_1)$$$ is uniquely determined by $$$a_1u_1+b_1v_1+c_1$$$ and $$$a_2u_1+b_2v_1+c_2$$$. However, $$$(u_2, v_2)$$$ is determined by the same constraints so we would get $$$(u_1, v_1) = (u_2, v_2)$$$ contradiction.

    Also, by a counting argument, $$$625\times k$$$ is not possible for $$$k > 650$$$.

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      If you can get $$$625 \times 650$$$, you can also get $$$625 \times 625$$$ by cutting the board (?)

      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The board $$$625\times625$$$ can be achieved just by placing $$$x_1x_2+y_1+y_2$$$ almost like in the editorial, but picking $$$x_{1,2}$$$ and $$$y_{1,2}$$$ from $$$\mathbb{F}_{25}$$$ instead of $$$\mathbb{Z}_{23}$$$. The question is, can you do at least $$$626\times 626$$$?

»
22 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Could anyone share the reasoning behind the particular construction in E (mentioned in editorial)? Thanks in advance!

  • »
    »
    22 months ago, # ^ |
    Rev. 2   Vote: I like it +90 Vote: I do not like it

    Source: I spent almost the whole contest on problem E, and I got AC $$$37$$$ seconds before the end.

    My notes: PDF

    • Page $$$9$$$: maybe it's useful to consider the "classical" bipartite graph.
    • Page $$$10$$$: small cases by hand, in the $$$4 \times 4$$$ case the cells with color $$$1$$$ make a big cycle. Maybe the intended is choosing a color for each diagonal.
    • Page $$$11$$$: there is a rectangle if there are two equal pairwise differences in the set of diagonals of a fixed color. Can we partition $$${0, 1, \dots, 499}$$$ in such a way that there are no such differences?
    • I tried to generate such diagonals on my PC, but I got stuck at $$$n \approx 370$$$.
    • Page $$$13$$$: ok, let's quit the diagonals approach. Let's put the color $$$1$$$ greedily, but in such a way that there are $$$\approx \sqrt{500}$$$ occurrences on each row (unbalanced occurrences = more pairs of cells with the same color in the same row = worse)
    • Page $$$14$$$: let's remove the rows $$$[4, 6]$$$ of page $$$13$$$, they seem inconsistent with the rest of the grid. Ok, we've found a construction with $$$n = m = 16$$$ and $$$4$$$ colors. [Actually it's wrong, there is a rectangle $$$(1, 1), (1, 11), (9, 1), (9, 11)$$$, but I hadn't noticed it.]
    • Page $$$15$$$: oh wait, it works even with $$$n = m = 625$$$ and $$$25$$$ colors!
    • [1:58:05] Submitted, got WA.
    • Oh wait, there actually is a rectangle because $$$25$$$ is not prime.
    • Let's try $$$23$$$.
    • [1:59:23] Submitted, got AC, shouted like a crazy guy.
»
22 months ago, # |
  Vote: I like it +44 Vote: I do not like it

I can't understand the editorial of D. What is "number of cycles that contain vertices in the connected components numbered x1...xk" mean?

  • »
    »
    22 months ago, # ^ |
    Rev. 2   Vote: I like it +54 Vote: I do not like it

    If we consider directed edge (i->xi), then each vertex will have out degree of exactly 1. Because of that, if we consider one graph such that all xi != -1, then each component will have at most one cycle if there are any.

    No. of connected components = No. of vertices — No. of edges + No. of cycles

    Initially we will have n components in which no edge is added. We will start adding edges one by one. Adding each edge will reduce the component by one unless we are already in a same CC in which it won't reduce. All such edges will have one to one mapping with cycles. So we can count cycles instead.

    Now if we consider the graph with X array given in the question. We will get some components. Each component will have at most one xi = -1. We only consider the component with xi =-1 as we are interested only in cycles.

    Let the size of components be A1,A2...AM where M are the number of component which have xi = -1

    Consider the cycle formed from component set {A1,A2,A3...AK}. We can permute them in (k-1)! ways. And then we connect the edges. There are A2 edges we can direct of comp1 to comp2, A3 edges we can direct from comp2 to comp3 ... and A1 edges we can direct from compK to comp1. Then we can choose remaining edges arbitrarily. So we multiply N^(M-k).

    Thus for component set {A1,A2...AK} we have (k-1)! * A1 *A2...*Ak * N^(M-k)ways to form a cycle. So we can use NTT to find Summation of product of (A1*A2*A3..AK) for each k.

»
22 months ago, # |
  Vote: I like it +39 Vote: I do not like it

Coming to ask for some help. Would anyone like to talk about problem D in more details? The editorial of problem D is somehow not so clear, at least for me :(

I think this is about combinatorial mathmatics, but still not able to find out how to deal with it.

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +60 Vote: I do not like it

    Hello there, I'll try my best to give a clear explanation about the solution.

    first of all, let's assume that the given array contains no -1 (in other words, all edges are given). By looking at a single component of the graph, you can see the number of edges in it are equal to the number of nodes, since as given in the input there is a single edge having a starting point at each particular vertex.

    Therefore, for every graph built in the same manner as the problem asks, it is enough to count the number of it's cycles and add these numbers up to form the answer. So from now on, we forget about the main problem and solve the new one, which is counting the number of cycles of all the graphs that can be built.

    Array A may contain values equal to -1, let's see how the graph will look if we forget about these edges. There will be a bunch of components, each one having at most one cycle since there is at most one vertex in each with no edge starting at it.

    Now instead of counting for each graph the number of cycles it contains, we can count for each cycle the number of graphs which contain it and sum these values up. Think of a cycle which there are T other values equal to -1 in A other than those used to make the cycle. Then there are n^T graphs containing the cycle. So if there already exists a cycle in a component of the given graph, just add n^(the number of -1s) and forget about these components.

    What is left, is a group of components, each looking like a tree, with exactly one node in them that you can add an edge from it to any other node to make your cycles. Consider a cycle using components with size B_1, B_2, ..., B_x. Then there are exactly

    (x - 1)!(B_1 * B_2 * ... * B_x)

    cycles that can be formed since you can put these components around a circle and then connect each component to the next one. So now you just have to calculate sum of the given expression for all components, which can be done using dynamic programming.

    Here's also my code for better understanding of the solution

    Code

    I hope this helps :)

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

      Thank you so much for your detailed reply and paticient help, and I have learned a lot from your words.

      I think I have missed at least two important observations that prevent me from solving this problem.

      The first one is, if we ignore all -1, the left nodes will form several connected components, and each of them either contains a cycle or looks like a tree. If it already has a cycle, then we don't need change it, while if it is a tree, then we should add one more edge to it, and this is what we should compute.

      The second one is, as you said, "Now instead of counting for each graph the number of cycles it contains, we can count for each cycle the number of graphs which contain it and sum these values up. ". This is an important "transformation" of the original problem which makes the calculation available, and this is very tricky!

      Thank you so much again for your help, and hope that one day I could handle such problem on my own.

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Since functional graphs (N nodes, N edges) are not necessarily simple cycles, why must the component be a simple cycle?

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

        I'm afraid I don't understand your question. Actually, the point that I am making in my explanation, is that since each functional graph has exactly one cycle, counting the number of cycles will be enough to solve the problem.

        Also when building a new component by merging some of the given components, the new component will not always be a cycle.

        • »
          »
          »
          »
          »
          22 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Oh I see. I thought you meant that each component is only one cycle. Thank you for your explanation and follow-up!

    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for the much better explanation than the original editorial. I understand the subproblems and equations from your explanation but I can't figure out the DP recurrence, nor the DP state.

      What is your DP state, and your DP recurrence?

»
22 months ago, # |
  Vote: I like it +110 Vote: I do not like it

Hi, I wrote problems B, C, E. Thank you all for your participation!!

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    Thank you so much for creating such great problems.

    Problem B is a nice practice for greedy algorithm, and I think there are several corner cases which one should take care of.

    As for Problem C, I missed the simple solution in editorial and used a more complicated one, but anyway, I have learned a lot of exciting ideas from your problems, thanks a lot!

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I'm glad to hear that! Thank you!

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    B and C maybe a bit simple for me. Thanks for Problem E. I took really much time in it in the contest (sadly didn't solve D or E), and was happy when I could explain and proof the solution clearly.

    Really a nice construction round, thank you again. ;)

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

      Thank you for solving my problem E!

      I'm not good at construction problems, but I like them :)

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Could anyone explain how so solve case $$$M=1$$$ in problem F. I don't understand clearly of the last part of the editorial.

Thanks!