Блог пользователя Ant_Man

Автор Ant_Man, история, 4 года назад, По-английски

How to solve B, D, E, J?

  • Проголосовать: нравится
  • +38
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится -21 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Oh, nice idea, thanks!

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

C xd?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится

    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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

How to solve I ?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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)
    
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You are very brave for writing that down

»
4 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

        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 ;_;

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

        A Codechef problem helps...

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.