Ant_Man's blog

XXI Open Cup (GP of Xiaomi)
By Ant_Man, history, 4 years ago, In English

How to solve B, D, E, J?

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

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

Were there errors in tests with problem S ? I have seen people passed it only after making +60 , +30 submissions.

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

J: Calculate dp[mask] — the longest possible distance from the center of mass to the rightmost point of all books with indices in mask. You can add books from top to bottom. If you have some books in mask, you can add another book to bottom in two ways:

  • Right side of the new book aligns with the center of mass for the books in mask;

  • Left side of the new book aligns with the center of mass for the books in mask.

By this technique you can calculate dp for the whole mask.

I don't know the right solution for other tasks. We implemented some weird $$$26 n \log^2 n$$$ in D, but it got TL.

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

    In D change each letter to the distance to the previous occurence of this letter

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

      Yeah, we were more or less ready to speed the solution up to $$$O(n \log(n)(\log(n)+26))$$$, but $$$O(n \log^2(n)26)$$$ was enough.

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

        Impressive, I wrote the $$$O(n \log(n)(\log(n)+26))$$$, and it still took 2.3s out of the 5s time limit.

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

          Our $$$O(n \log ^ 2 (n) 26)$$$ took 1.6 s. I think in this case it much more depends on the implementation rather than complexity.

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

      Oh, nice idea, thanks!

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

C xd?

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

    Let's say we generate two independent trees, and then for each vertex $$$v$$$ calculate the expected number of pairs of vertices $$$i,j$$$ s.t. $$$v$$$ is an ancestor of $$$i$$$ in the first tree, and $$$v$$$ is an ancestor of $$$j$$$ in the second tree. A simple DP can do this.

    Next, using these values, for each vertex $$$v$$$, calculate the expected number of pairs of vertices $$$i,j$$$ s.t. $$$v$$$ is the vertex with maximum index with the abovementioned property. Let $$$f(v)$$$ be this value.

    Here's the trick: I said two trees, but the value $$$f(v)$$$ is the same as the expected number of pairs of vertices $$$i,j$$$ s.t. $$$v=lca(i,j)$$$ when we consider only one tree. This is because the paths $$$i \rightarrow v$$$ and $$$j \rightarrow v$$$ are disjoint.

    And the rest is straightforward.

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

      How did you calculate $$$f(v)$$$? We had to use the observation that there are few triples $$$i,j,k$$$ such that $$$i \vert j$$$ and $$$j \vert k$$$, so our runtime is like $$$O(n \log^2(n))$$$. Realizing the graph was small enough to enumerate all reachable pairs was definitely a surprise for me.

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

        The std is also $$$O(n\log^2 n)$$$. Enumerating on the transition graph is the intended solution. (We tried to make it faster for a long time but we failed.

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

        Let $$$g(v)$$$ be the answer to the first DP. Then $$$f(v)=g(v)-\sum_{i|j} f(v) \times (the\ probability\ the\ path\ j\rightarrow i\ exists)^2$$$. When we fix $$$i$$$, we can calculate $$$(the\ probability\ the\ path\ j\rightarrow i\ exists)$$$ for all $$$j$$$ in $$$O((n/i)\log(n/i))$$$ time. So the total time complexity is $$$O(n\log ^2(n))$$$.

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

      Wow, it somehow looked intractable to me during contest, but now it doesn't even look that hard :,( Nice trick

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

How to solve I ?

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

B: Do D&C. For some interval passing trough the middle the optimal subinterval either passes through the middle or is fully contained in one of the halves. For each prefix of the right half calculate the greatest sum of its subinterval and the greatest sum of its subprefix. The same for left half (but for sufixes ofc. Let's create triples $$$(subinterval, subprefix, side)$$$ with side being $$$0$$$ or $$$1$$$. Sort them in nondecreasing order of $$$subinterval$$$. Now go from smallest to biggest and when you pair some triple $$$i$$$ with each passed tripple $$$j$$$ (with different side) the result is either equal to $$$subinterval_i$$$ or $$$subprefix_i + subprefix_j$$$. If you also maintain the triples sorted by $$$subprefix$$$ it's easy to see that the first case will happen for prefix and the second case for sufix, so Fenwick tree does the job.

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

    B is kind of an easier version of 1458F - Range Diameter Sum from Round 691, which was just 24 hours earlier; they have both a similar statement and a similar D&C solution. I definitely got a hint from looking at solutions to 1458F earlier in the day.

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

    B is doable in $$$O(n\log(n))$$$ with stack and segment tree. Consider an easier problem where you need to calculate max segment sum for queires $$$[l, r]$$$. We can go from right to left and maintain for each position the largest sum segment ending in this position. When we are at point $$$l$$$ we need to ask maximum on $$$r$$$-th prefix of segment tree to get answer for query $$$[l, r]$$$.

    Now in our problem we need to count sum of those maximums which seems harder. But we can store those maximums in the segment tree instead of actual values. Since everything is monotone we can remax with a simple assignment on segment.

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

E: I'm omitting the proof here, but $$$|str(c)| \in [|str(\left\lfloor n/2 \right\rfloor)| - 1, |str(\left\lfloor n/2 \right\rfloor)|]$$$ where $$$|str(\left\lfloor n/2 \right\rfloor)|$$$ is achieved if:

  • $$$n$$$ is even, or
  • $$$n$$$ is odd, begins with 1 (but not 10), and $$$n \mod{11} \neq 10$$$.

And the following factorizations $$$n = a + b$$$ are enough:

a=n/2, b=n/2 for n even;

a = xklmnopy
b =  xklmnop, x != 0
this works if n % 11 != 10, e.g. 33099 = 30090 + 3009, c = 3009

a = xklmnopy
b = 1xklmnop, x != 0
e.g. 73479 = 57709 + 15770 (c = 5770)

a = 1klmnopy
b = 10klmnop
e.g. 20239 = 10218 + 10021 (c = 1021)

a =  99klmnopy
b =  99zklmnop
--------------
n = 199a****** (a<9)
now that I experiment a bit, z = 7, 8 seem enough, but necessary:
10045 = 2769 + 7276 (c = 276)
10013 = 1830 + 8183 (c = 183)
also see:
1999909999 = 999936363 + 999973636 (c = 99993636)

Each of the cases can be verified in $$$O(n)$$$ time (some simple greedy algorithm).

Maybe it can be done a bit cleaner than that?

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

    The case where n is odd and n % 11 == 10 can be handled as follows:

    Let p=n/2
p=somethingequalx9...999
q=somethingequaly0...000, where y=x+1

    There could be none of 9s and 0s, but it's not a special case. somethingequalx might be empty though. Then we can do:

    a=somethingequal x  y 9-y y 9-y ..
b=somethingequal y 9-y y 9-y y ...
c=somethingequal y 9-y y 9-y y (1 symbol less)
    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You are very brave for writing that down

    → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

How did you guys solve A? We reduced it to undirected vertex geography and thus finding the max matching of $$$G \setminus \{v\}$$$ for each vertex $$$v$$$, but didn't know if there was a well known way to proceed from there.

We used the randomized Tutte matrix trick for finding a maximum matching (https://www.cc.gatech.edu/~rpeng/18434_S15/matchingTutteMatrix.pdf ): construct the Tutte matrix, substitute in a random value of $$$\mathbb{F}_{998244353}$$$ for each formal variable, and then use Gaussian elimination to get it into RREF. Then, a starting move is winning iff the elementary vector $$$e_i$$$ is a row of the RREF.

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

    Not sure what you mean. Do you ask how do you solve undirected vertex geography through matchings or how to do it fast enough?

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

      Yeah, how to solve it fast enough; in particular, how do you find max matching when removing each point?

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

        We compute max matching once (call it $$$M$$$). Then we look at each vertex v. If it doesn't belong to $$$M$$$ then we are happy. If it does then let $$$u$$$ be the neighbor it was matched to. We remove $$$v$$$ from the graph and search for an augmenting path from $$$u$$$.

        There was no point in my life when I understood blossom algorithm, so I can't say that with confidence, but I think my teammates seemed convinced it indeed works in $$$O(m)$$$ per augmenting path as one would expect, so in total that gives $$$O(nm)$$$. Unfortunately even with $$$O(nm)$$$ we faced some TLE issues and that turned out to be decisive about the win ;_;

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

        A Codechef problem helps...

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

This F... XD I am always enthusiastic about hard geometry problems, but in my life I've had enough of "shortest path on a plane with forbidden polygon" problems and they are always a struggle.

→ Reply