tourist's blog

AtCoder Grand Contest 019
By tourist, history, 7 years ago, In English

AtCoder Grand Contest 019 will be held on Saturday (time). The writer is tourist.

Contest Link

Contest Announcement

The point values will be 300 — 500 — 900 — 1000 — 1700 (1200) — 2000 (1500). Note that the contest duration is unusual (150 minutes).

Let's discuss problems after the contest.

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

Comments Comments (39)
| Write comment?
»
7 years ago, # |
  Vote: I like it +33 Vote: I do not like it

It is very pleasing as well as fearing to see you as a contest writer tourist.

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

Yesterday I had to cancel my weekend plans and got upset by that. Now I'm not that upset anymore.

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

tourist round? Oh Yeah!

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

Special mention when tourist is the problem setter:

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

I hope to get well in this contest, this wink has to mean something..

→ Reply
»
7 years ago, # |
  Vote: I like it -14 Vote: I do not like it

Looks like the whole world is waiting for this contest -> I hope that servers will handle such a huge number of participants.

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

Did anyone else get WA in last 4 tests in C?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    Case like that:

    0 0 3 1

    2

    1 0

    2 1

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

      I think i considered that, so what's correct output?

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

        402.831853071795862

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

          And how can we achieve this?

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

            Sorry, my mistake 407.123889803846897

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

              I have the same, so i've missed something else

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

        The last 4 cases were similar but with x & y swapped. Try this

        0 0 1 3

        2

        0 1

        1 2

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

Any hints for C?

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

    x1 = x2 and y1 = y2 are not the only special cases.

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

how to solve B ? :)

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

    Consider all contiguous regions. of them. Now a [l... r] is superfluous if a[l] = a[r] as [l + 1... r - 1] is already checked. Subtract these from that.

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

    Good day to you,

    well a good hint is, that as long as "borders" of reversed substring are equal, then the string after reverse will be same as if it was reversed without borders.

    Also note that if this wouldn't happen, then |s|*(|s|+1)/2 (+1) possible solutions could apprear.

    Hope it helped a little bit.

    Good Luck & Have Nice Day ^_^

    → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +20 Vote: I do not like it

Solution for B is so simple but too difficult to come up with. ;(
How did you come up with it?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    It's obvious that if substring is palindrome reversing it won't change anything. And I noticed if s[l] = s[r], then reversing it will be same as reversing [l + 1, r — 1], so you need to substract such pairs.

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

    The hard way:

    • "prove" that any palindrome is bad and any non-palindrome is good (and unique)
    • code a solution using Manacher's algorithm
    • fail last sample (answer: 54)
    • print all strings my solution generates
    • find out why some are the same
    • look for a way to find pairs of same letters in same distance from given pivot (yay for overcomplicating)
    • give up, switch problem
    • return to it, start from scratch but with a correct condition this time
    • finally solve it.
    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +23 Vote: I do not like it

      My first three steps were the same as yours :)

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it +55 Vote: I do not like it

      Then atleast someone suffered like me. My steps:

      1. Look at points : 500 => Easy.

      2. Look at problem : WTF, how to solve?

      3. Think for some time, figure out swapping palindromes is invalid.

      4. Look at "abracadabra" : HTF is answer 44? How can 11 be bad?

      5. Look at standings : People solving trivially in 8 — 10 minutes.

      6. Start discarding Manacher. What is trivial and seems correct?

      7. No idea, write brute force Python code, print all invalids.

      8. Endpoints equal means invalid, scold yourself for being dumb.

      9. Believe in God, and that your observation is the sufficient condition.

      10. Code.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it -25 Vote: I do not like it

        and these are my steps :D :

        1.read problem !

        2.WTF :D

        3.after about 10 min think , I guess that it need some algorithm that I don't know !

        4.close contest page and go to my bed and sleep :))))

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

      My way:

      • guess that any palindrome is bad and any non-palindrome is good (and unique)
      • code a solution using Manacher's algorithm
      • fail last sample (answer: 54)
      • print all strings my solution generates
      • find out why some are the same
      • look for a way to find pairs of same letters in same distance from given pivot (yay for overcomplicating)
      • give up, switch problem
      • return to it, start from scratch but no clue
      • finally time is up
      → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +78 Vote: I do not like it

      Oh, that 54 is familiar :D I was afraid I'm the only one here, facing side effects of droptable coaching me for ICPC :)

      I really loved this problem — it made me feel stupid, then I had to guess solution from standings (there are not so many simple things you can do with string in 2 minutes), and then after figuring out why is it correct (only after the contest) I was amazed how simple&obvious it is.

      It is also funny how it uses some simple but not worn-out idea, but everybody goes into palindromes because they have been hyped a bit over last years :)

      → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I also stuck with this problem , ended up by doing it bruteforce(print out all of the same strings with different left and right) and finally got it xD

    → Reply
»
7 years ago, # |
← Rev. 5   Vote: I like it +105 Vote: I do not like it

I have an easy solution to E in O(n2) with a sufficiently small constant, without using NTT, unlike 998244353 suggested. (p.s. I didn't bothered to check other solutions. It appears that first solvers have the same solution.)

int solve(int x, int y) {
    dp[0] = 1;
    for (int i = 1; i <= x; i++)
        for (int j = 1; j <= y; j++)
            dp[j] = (dp[j] + (long) i * dp[j - 1]) % mod;
    int ans = 0;
    for (int i = 0; i <= y; i++)
        ans = (ans + (long) dp[i] * inv[x + i]) % mod;
    return (long) ans * fac[x] % mod * fac[x] % mod * fac[y] % mod * fac[x + y] % mod;
}

We first observe that any valid swap is either:

  1. Swapping a (0, 1) with a (1, 0) (swapping ai, aj s.t. (ai, bi) = (0, 1), (aj, bj) = (1, 0))
  2. Swapping a (0, 1) with a (1, 1)
  3. Swapping a (1, 1) with a (1, 1)

Let x be the number of (0, 1) and y be the number of (1, 1). Clearly the number of type 1 swaps is x, and the number of type 2 or 3 swaps is y. As type 3 swaps do not interfere with other types, we assume there are y - i of them, multiply the answer by , and forget their existence.

Now we're left with x of (0, 1), i of (1, 1), and only type 1 or 2 swaps. Let g(x, i) be the number of possible swap sequences. Clearly,

Let g(x, i) = (x!)2(i!)f(x, i). Then clearly,

And for the final answer, we must sum over 0 ≤ i ≤ y, i.e.

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

    I think that tourist knew about this solution and made constraints lower for this to pass. If the only intended complexity was then why n is not up to 105?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it +10 Vote: I do not like it

      Better ask tourist directly for the reason.

      Anyway, I'd still post the comment as long as most of the world didn't know about this solution.

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

        Thank you for describing your solution! It's quite different from the editorial, so it's definitely worth explaining.

        Indeed, we had only intended, but shortly before the round discovered that it's nearly impossible to separate it from O(n2). Thus, we decreased the constraints to make it obvious that O(n2) works.

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
          ← Rev. 3   Vote: I like it +11 Vote: I do not like it

          It took a lot of work, but I was able to squeeze in a solution of F in .

          Let's first consider the case where N = M, and compute A[x] — the sum of the results over all possible Yes/No sequences. Clearly, A[0] = 0.

          We model the Yes/No sequence as lattice path from (N, N) to (0, 0). What happens at point (x, x) for x > 0? There will surely be a point where the path crosses the main diagonal again for the first time, that is, we reach state (y, y) for some 0 ≤ y < x.

          How many ways to do this are there, and how good they score? Let's assume that the we guess incorrectly at (x, x) and we move to a state (x - 1, x). Then, our path continues to (y, y + 1) and then continues to (y, y). It is the first time we reach the main diagonal, thus the path never crosses the "+1" diagonal. There are such paths. Since it is optimal to always guess the answer which has the most occurrences left, it is easy to see that this path scores exactly y points, plus whatever we expect to get from the path between (y, y) and (0, 0).

          Similarly, if we guess correctly at (x, x), we have the same amount of paths to (y, y), but we score one more point (the one at (x, x)).

          This combined yields the following recurrence:

          The second summand in the large sum times the right term can be computed first by a simple convolution. The term with A[y] can be then computed using linear convolution (of form ) in time.

          This yields 1500 points and fits quite comfortably into TL. To extend this to a full point solution, we need an extra linear step: for every point (x, x) we calculate how many paths there are for which this is the first point on the main diagonal from the path from (N, M) (again by using the above formula for lattice paths above the diagonal) and for each of them add M - x points to A[x].

          The TL is very tight in this case, so one needs to have solid NTT implementation, and when doing the linear convolution using Divide & Conquer algorithm (described here), one needs to cut-off the recursion at around 26.

          My quite convoluted (pun intended) solution: link

          EDIT: The editorial seems not to be present anymore, so I wasn't able to verify how much my solution matches it :)

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

      Maybe his mind is weak

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

could someone explain the "simple binary coefficient" for me :D

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

As expected, problems were very interesting. Words cannot explain the pleasure of a post-AC orgasm from this contest's problems.

→ Reply