Qingyu's blog

By Qingyu, history, 20 months ago, In English

How to solve task C and G?

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

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

My solution for G was the following:

Denote $$$s_i$$$ as the set of $$$2\times 2$$$ squares that contains exactly $$$i$$$ '?' question marks and it is possible to fill those question marks in such way, that the resulting $$$2\times 2$$$ square is a check pattern. If at some point $$$s_0$$$ is not empty, then the answer is "NO". Otherwise, try to use minimal $$$i$$$, take a single element from the corresponding $$$s_i$$$ and consider two cases:

  1. if $$$i = 1$$$, then fill the question mark in such way, that the $$$2\times 2$$$ square is valid

  2. otherwise, fill one of question marks in any way (e.g. set it to 'B')

After each update of characters, update sets $$$s_i$$$ as well and continue the process.

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

Scoreboard differs so much from on-site's.

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

How to solve Problems: (L) Fenwick Tree, (J) Elden Ring, (B) Beautiful string? Also, it is interesting for me, is there any alternative solution for problem (S) Two Sequences (I solved it with the help of KMP, it is classical and can be observed quickly, but maybe there is something alternative)?

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

    B: let's fix $$$i$$$ as the beginning of $$$s2$$$ and $$$j$$$ as the ending (exclusive) of $$$s3$$$. We need to count in how many ways we can set $$$s1=s2$$$ and in how many ways we can set $$$s5+s6=s2+s3$$$ and then add the product of these numbers to the answer.

    Compute the z-function for each prefix (O(n^2) in total) and let $$$z[i][j]$$$ = the maximum number of characters such that $$$s[i..] = s[j..]$$$.

    If $$$k$$$ is the beginning of $$$s1$$$ then we should have $$$z[k][i]>=i-k$$$ in order to $$$s1=s2$$$ where $$$2i-j+1\leq k<i$$$. If $$$x$$$ is the beginning of $$$s5$$$, then we should have $$$z[i][x]\ge j-i$$$ in order to $$$s2+s3=s5+s6$$$ where $$$x$$$ starts from $$$j+1$$$.

    If we fix $$$i$$$ and we increment $$$j$$$, these two values can be updated in constant time using some precomputations.

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

      Thank you for the solution to problem B! cristian1997

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

      No z-algorithm is required here. An easier way to compute $$$z[i][j]$$$ is just a simple dp. If $$$s[i]=s[j]$$$, $$$z[i][j]=z[i+1][j+1]+1$$$, otherwise it's $$$0$$$.

      The intended solution is to consider $$$A|ABC|AB$$$. Let $$$i, j$$$ be these two separators. Let $$$w = min(j-i, z[i][j])$$$, which is the longest length $$$AB$$$ can extend. The answer is the number of square substrings that is centered at $$$i$$$ and with length $$$\leq w-1$$$, and it can be precomputed $$$O(n^2)$$$.

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

    L: Consider the indices as a tree, such that when you update some index, you add the value to all nodes on the path to the source.

    If a vertex has no nonzero children and must be nonzero, we need to make an update on it. If a vertex has exactly one nonzero child and must be zero, we need to make an update on it. Otherwise, you can scale children so they cancel/do not cancel each other out.

    J: Increment all monster strengths by $$$B$$$, then let $$$D = A - B$$$. Now, we can ignore $$$A$$$ and $$$B$$$ and just gain $$$D$$$ strength after defeating a monster.

    If $$$D < 0$$$, simple Djikstra works. Otherwise, we first compute the maximum strength we can reach. This is simple in $$$\mathcal{O}(n \log n)$$$ with a priority queue. Then, we can again do Djikstra. Let $$$H$$$ be the maximum strength we can reach, and $$$dp[i]$$$ be the minimum number of days we need to beat the monster at node $$$i$$$. Then, for a vertex $$$j$$$ adjacent to vertex $$$i$$$, if

    • $$$h[j] \geq H$$$, we can never beat that monster.
    • $$$h[j] < h[0] + D \cdot dp[i]$$$, we can immediately beat the monster after beating monster $$$i$$$: $$$dp[j] \leq dp[i] + 1$$$.
    • $$$h[0] + D \cdot dp[i] \leq h[j] < H$$$: we can beat the monster as soon as we have the strength for it: $$$dp[j] \leq 1 + \left\lceil \frac{(h[j] + 1) - h[0]}{D} \right\rceil$$$.

    It's easy to see that this is tight. We can never have $$$dp[j] < \min_{i} dp[i] + 1$$$ where $$$i$$$ goes over the neighbours of $$$j$$$ (unless $$$j$$$ is $$$1$$$), and we can never beat a monster until we have the strength to do it (and every day we gain exactly $$$D$$$ strength until we reach $$$H$$$ strength).

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

Can someone please explain how to solve J, H and D?

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

    H: let's invert every second square, now we need to maximize the number of totally white or totally black 2x2 squares.

    Let's build a network: edges with capacity 1 from source to white 2x2 squares which are still possible, edges with capacity 1 from black 2x2 squares which are still possible to sink, and edges with infinite capacity from a white 2x2 square to each intersecting black 2x2 square. Then we find the minimum cut, and edges of capacity 1 which are not in minimum cut give us our answer.

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

      Another way to understand this network: We just add edges between the conflicted 2x2 squares and find the maximum independent set of this graph.

      It's a bipartite graph. so we can solve it by flow or Hopcroft-Karp (10x faster than flow and I don't know why).

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

        Thanks, it makes perfect sense — now I'm not sure why I had to go with the flow :)

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

        If I understand unit network correctly, the network Petr proposes is not a unit network. Maybe this is the reason why flow is slower?

        However, this network is pretty similar to the one in 311E - Biologist but Dinic is fast on that one. Thus I am not sure if I really have the correct explanation.

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

      I understand now. And in fact it is unit network.

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

    D: the answer is always 0, 1 or 2. It's easy to check for 0, we just need to distinguish 1 and 2.

    In order for 1 to be possible, we need to check if the set of points reachable from A directly and the set of points reachable from B directly intersect.

    Set of points reachable from A directly when we don't intersect a given segment is a union of 2 or 3 half-planes without boundary. Therefore we need to check if 4 such unions intersect. We can iterate over 3**4 options for which halfplane to pick in each union, and now we need to check if 4 halfplanes without boundary have a non-empty intersection.

    It turns out that in this task we don't even need to solve that problem exactly, and it suffices to check if they intersect "in the infinity" — in other words, if all normal vectors to the half-planes can be covered by one angle that is less than 180 degrees.

»
20 months ago, # |
Rev. 3   Vote: I like it +30 Vote: I do not like it

C: (the solution by YaoBIG and mango_lassi, ours was K times slower asymptotically but we managed to squeeze it) After processing the greedy part of the problem, we are left with the following subproblem: we have some slots to fill, for each slot we have a set of valid characters, and for each character we either have a lower boundary on the number of occurreneces, or an exact number of occurrences.

We can now fill the slots from left to right, the state of our DP will how many slots we filled and the set of remaining lower boundaries. We have at most 2^K sets of remaining lower boundaries (since their sum is K, and they only decrease), so we have at most O(K*2^K) states, and each state is processed in O(alphabet size).

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

    The intended solution is $$$O(2^k * (k+|\Sigma|)$$$. For a set of remaining lower boundaries, it can only appears from position (the number of the letters in it) to position (k — the number of remaining letters to fill). So the total number of states is $$$O(2^k)$$$.

    I set the constraint that let $$$O(2^k * k)$$$ and optimized $$$O(2^k * k^2)$$$ solution pass.

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

      Yeah we had a small bug when pre-processed the greedy part so we did not manage to pass it during the contest. We first spent ~20 minutes to make our $$$O(2^kk|\Sigma|)$$$ solution fit in the TL and then had no time to find which invalid case we were missing... T T.

      Did all on-site teams which solved this problem had the solution of time complexity $$$O(2^k(k + |\Sigma|))$$$? I just feel that the master solution is really hard to come up with & implement.

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

Is there editorial?

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

How to participate in Open Cup contests? I have mailed snarknews on mail but got no answer

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

    Try to DM him on telegram... You need some good luck to get his reply.

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

Can anyone share the solution for A?

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

    If you observe you can see that the minimum answer for each node, is the level of dfs tree. For example, the root is level 1, its neighbourhoods have level 2 (level of parent + 1) and etc...

    The maximum answer for each node( let's say the node v), is if you visited all nodes in other subtrees and in the last way coming to the node v. We can calculate it by following the formula: Let's say that the subtree with root v has dp[v] children. So the maximum answer will be dp[1] — dp[v] + 1. It means that you have already visited all nodes except the children of the node v. dp[v] can be calculated by just easy dfs. It is classical.

    The code of dfs for all needed calculations.
»
20 months ago, # |
  Vote: I like it +11 Vote: I do not like it

What was the expected solution for M?

I got TL41 during the contest with $$$O(n \log n \log m)$$$ 5 minutes before the end. It was sad to realize after the contest that there are 41 tests in total, and my solution gets AC if I replace "sort" with "sort_unstable"...

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

    How do you solve it?

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

      Our solution has a lot of unproven assumptions, I'd love to see a proof. First, binary search on the total time taken. Then, we'll make the following claim: ants should leave from each hole during the first half of the time, and ants should enter each hole during the second half of the time. (If the total time is odd, for the midpoint time, we alternate leaving and entering in sorted order by $$$a_i$$$.)

      Once you've fixed whether each hole is used for leaving and entering at each time, we have a set of times that ants can arrive at the fridge, and times that the ants must leave from the fridge. Then, we should match these as much as we can, which is just finding the maximum balanced parenthesis subsequence, which we can do with greedy. To do it efficiently, we need to run length encode the ant arrival/departure rates; we can do this in $$$O(n \log n)$$$ by sorting or $$$O(n)$$$ with merge sort if we sort the holes up front. Thus, the total runtime is $$$O(n \log n \log m)$$$ or $$$O(n \log m)$$$. We passed using $$$O(n \log n \log m)$$$ in 6 seconds.

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

        Mine is pretty similar (also with many facts I don't know how to prove).

        For the second part instead of run length encoding, for each hole, I find the number of times it should be used (such that we have $$$m$$$ elements in total, and the maximum element is the smallest possible). And then match them greedily with similarly constructed elements for returning ants. In terms of implementation, it is just sorting and checking the balance is never negative.

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

        A proof can be like this:

        1. Binary search on the total time $$$t$$$.

        2. At the $$$x$$$-th second, through hole $$$i$$$ (whose distance is $$$a_i$$$), there can either be an ant coming in or an ant coming out. For the first case, it must steal the food by the end of the $$$(x-a_i-1)$$$-th second. For the second case, it can steal the food by the end of the $$$(x+a_i)$$$-th second. We can put a ')' at the $$$(x-a_i-1)$$$-th position for the former case and put a '(' at the $$$(x+a_i)$$$-th position for the later case. We want to choose one between the '(' case and the ')' case for each second for each hole and form a bracket sequence. Then the maximum number of ants (that successfully steal some food) is equal to the maximum length valid bracket subsequence. Note that we can have multiple '(' and/or multiple ')' at the same position. These '(' and ')' can match each other.

        3. Since the bracket sequence can be asymmetric, we apply the following trick. Let X be an optimal solution (a bracket sequence). We construct X' such that if in X, the $$$x$$$-th second of the $$$i$$$-th hole chooses '(', then in X', the $$$(t-x+1)$$$-th second of the $$$i$$$-th hole chooses ')'. In other words, X' is the reversed version of X. Let Y be the sum of X' and X, i.e., if X has $$$a$$$ '('s at position $$$i$$$ and X' has $$$b$$$ '('s at position $$$i$$$, then Y has $$$a+b$$$ '('s at position $$$i$$$.

        4. This Y is symmetric. We know that the maximum length valid bracket subsequence of Y ($$$len_Y$$$) is at least twice as long as that of X ($$$len_X$$$). If we can also show $$$len_Y$$$ is at most $$$2len_X+1$$$, then we can just solve for the 'doubled version' and divide the answer by $$$2$$$. (Because Y is a solution of the 'doubled version' in which each hole can allow one ant coming in and one ant coming out, or two ants in the same direction.)

        5. Let's consider how the brackets in Y match each other in the maximum length valid bracket subsequence of Y. By an inductive argument (from endpoints to the middle), we can assume this matching is symmetric, i.e., there is a 1-1 onto mapping between the matched pairs of '(' and ')' such that a pair at positions $$$x$$$ and $$$y$$$ is mapped to a pair at positions $$$t-y+1$$$ and $$$t-x+1$$$.

        6. Another important property of the optimal solution of the original problem (not the doubled version) is that for the first half, the first to the $$$\lfloor t/2\rfloor$$$-th seconds, ants only go out from the holes and for the second half, ants only go back into the holes. (If $$$t$$$ is odd, we know nothing for the $$$((t+1)/2)$$$-th second.) Because otherwise, WLOG suppose at the $$$x$$$-th ($$$x\le t/2$$$) second, an ant go back into hole $$$i$$$. It contributes a ')' at position $$$x-a_i-1$$$ and a '(' at position $$$t-x+1+a_i$$$ to Y. But we can choose the other way, which contributes a '(' at position $$$x+a_i$$$ and ')' at position $$$t-x+1-a_i-1$$$, to match more (or equal number of) pairs. The other way is not worse because it makes the position of the contributed '(' move to the left and the position of ')' move to the right (note that $$$x\le t/2$$$). Assuming this property, we can see that for any $$$1\le x \le t/2$$$ and any hole $$$i$$$, the $$$x$$$-th second and the $$$(t-x+1)$$$-th second contributes two '('s to position $$$x+a_i$$$ and two ')'s to position $$$t-x+1-a_i-1$$$. For simplicity of argument, we assume the two '('s are created by the $$$x$$$-th second and the two ')'s are created by the $$$(t-x+1)$$$-th second. In the original version, each second can only keep one bracket from the pair. When $$$t$$$ is odd and $$$x$$$ is $$$(t+1)/2$$$, the $$$x$$$-th second contributes a ')' to position $$$x-a_i-1$$$ and a '(' to position $$$x+a_i$$$.

        7. We first consider the easy case -- $$$t$$$ is even. Each pair of '('s are matched to two ')'s. The two ')'s may or may not be in the same pair. If we consider the pairs as vertices and the matches as edges, we have a bipartite graph consists of cycles. For each cycle, we erase the even-numbered edges (or odd-numbered edges). Exactly half of the edges remain. The remaining edges matches exactly one bracket from each pair. In other words, the remaining edges and the brackets matched by them form an answer of the original problem. $$$len_X\ge len_Y/2$$$.

        8. If $$$t$$$ is odd, the graph consists of paths and cycles. We still want to erase some edges and their corresponding brackets such that each second of each hole keeps only $$$1$$$ bracket. For each cycle, we can do the same thing. For each path, it must connects a bracket ('(' or ')') created by some hole $$$i$$$ at the $$$((t+1)/2)$$$-th second and a bracket ('(' or ')') created by some hole $$$j$$$ at the $$$((t+1)/2)$$$-th second. If $$$i\neq j$$$, because the matching is symmetric, we can find the mirror image of this path. We keep odd-numbered edges in the original path and even-numbered edges in the mirror path. Then exactly one bracket created by the $$$i$$$-th hole at the $$$((t+1)/2)$$$-th second is kept. The same holds for $$$j$$$. (Thus, it is possible to create the remaining brackets from the original problem.) The number of edges in these two paths are cut by exactly half. (This case actually contains two cases -- when both paths has an endpoint of ')' an endpoint of '(', and when one path has two endpoints of ')' and the other has two endpoints of '('. But the same argument applies to both cases.) If $$$i=j$$$, the mirror of the path is itself and this path has an odd length. We can't keep more than half of the edges in this path because we can keep only one the two endpoints of this path (because they are both created by the $$$i$$$-th hole at the $$$((t+1)/2)$$$-th second). We collect this kind of paths and pair these paths up. We modify each pair of such paths so that they become two different paths that are the mirror image of each other, i.e., the previous case. (This is always possible because at the middle of each such path, we have a pair of '(' and ')' whose positions are symmetric. The two pairs from two such paths can be exchanged.) Then at most $$$1$$$ such path has no partner. If its length is $$$l$$$, we can only keep $$$(l-1)/2$$$ edges. This is the only case where we can't keep exactly half of the edges. We have $$$len_X\ge (len_Y-1)/2$$$.

        9. In either case (7 or 8), $$$len_X\in [(len_Y-1)/2, len_Y/2]$$$. $$$len_X=\lfloor len_Y/2\rfloor$$$.

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

    $$$O(n \log m)$$$ or optimized $$$O(n \log n\log m)$$$.

    I guess you don't need to optimize it too much. But the constant factor might differ very much between different implementations. Some testers and my implementation of $$$O(n \log n \log m)$$$ only take about 4 sec.

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

The contest has been added to the gym. Link

We will add ghost participators later.

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

    Thanks! Do you need a help to add ghosts?

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

      Thanks for your reply. The difficulty now is that we didn't export the result after frozen now. We are asking the judges for the result.

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

    Can you submit model solutions to gym, please? I wonder what is the time complexity for F, I doubt that sqrt decomposition will pass TL.

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

      You can actually solve it in $$$O((n+m) \log n)$$$ with a bunch of segment trees 167449106.

      The idea is to split the whole array into segments of size $$$c$$$. For each pair of neighboring segments, we can create a segment tree of size $$$c$$$, which calculates the best segment, which starts in the first segment and ends in the second.

      When we process a query $$$l..r$$$, we look at all segment trees, for which both segments lie inside $$$l..r$$$, and find the maximum of answers in them. For $$$O(1)$$$ segment trees which are only partially covered by $$$l..r$$$ we need to query some subsegments of them.

      Also, we need another segment tree, which just finds the best subsegment (without restriction on $$$c$$$). So if we receive a query $$$l..r$$$, where $$$r - l < c$$$, we can just query this segment tree.

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

        Thanks! Can you elaborate how to solve the case when there are only two neighbouring arrays of size $$$c$$$? For some reason I thought this was not possible.

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

          First, if $$$r - l \le c$$$ you need to look at the answer in another segment tree, which just calculcates the best subsegment of any length.

          Also you can query the same segment tree with segments $$$l..l+c$$$ and $$$r - c..r$$$, and update the answer.

          After that you only need to consider the cases, when optimal segment intersects position $$$c$$$. In that position you store this additional segment tree of size $$$c$$$, which in the leaf $$$i$$$ stores $$$\sum_{j=i}^{c} a_j$$$ and $$$\sum_{j=c}^{i+c} a_j$$$. And more general, in some node of the sement tree, which corresponds to some segment $$$x..y$$$, we store:

          • maximum segment, which starts somewhere in $$$x..y$$$, and ends in $$$c$$$

          • maximum segment, which starts in $$$c$$$ and ends somewhere in $$$x+c..y+c$$$.

          • maximum segment, which starts somewhere in $$$x..y$$$, ends in $$$x+c..y+c$$$, and have length no more than $$$c$$$.

          So you need to query this segment tree with segment $$$l..r - c$$$. It should cover all cases not covered by our first queries.

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

            When updating, how can we avoid needing to change c leafs on the additional segment tree?

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

How to solve F & K?

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

nice contest

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

Dont know

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

Who can share the code of problem B with me?