chokudai's blog

AtCoder Beginner Contest 198 Announcement
By chokudai, history, 4 years ago, In English

We will hold AtCoder Beginner Contest 198.

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

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

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

How to solve C? I tried binary search to avoid precision issue, and even python to avoid overflow issues. Still fails on 3 testcases.

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

    it ruined the contest for me

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

    See this problem: https://mirror.codeforces.com/problemset/problem/1307/B

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

    c is just the ceil value of distance and r.
    corner case: if distance < r answer = 2

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

      Thanks. Very funny edgecase :/

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

      Yes that was the corner case. Thanks!

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

      if distance < r answer = 2 — could you please explain, why?

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

        Obviously you cannot reach the point with one step, since with one step you can reach only points of distance exactly r.

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

          if distance <r can we say 2*distance>r. can you please explain.

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

            with two steps we can go every distance between 0 and 2*r

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

    the answer is always less than or equal to $$$10^{5}\sqrt{2}$$$ so no need for binary search.. you can use linear search

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

    Binary Search will be able to help you with some part of this problem. But, for checking if the number is a perfect square or not you have to calculate its the number of divisors can be odd or not. Link to my submission

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

    By the way, the same edge case showed up on 1307B - Cow and Friend (very similar problem overall).

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

How do you solve F?

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

    Apparently it was A054473, but how to solve this formula? >_<

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

      How to search this on oeis? :')

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

      I even tried google the same definition and couldn't find that formula lol

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

      Here is the painful process I went through to derive it.

      • Burnside lemma

      • Scroll down to "Group of permutations of the cube in cyclic representation" on this page + manually count every cycle type

      • For every cycle type, find the count of its fixed points. Trivial enough to do for all cycles being of equal length (it is exactly the same as Task A in the contest!)

      • This left me with cycle types (1, 1, 4) and (1, 1, 2, 2). Do a little math to reduce their expressions. By a little, I mean a lot by the standards of competitive programming. The former is easier wherein you have to solve $$$4a + b + c = s$$$. Write it as $$$b + c = s - 4a$$$ and create an arithmetic series accordingly. The latter is more involved, but involves thinking along similar lines.

      The AC submission came a few minutes after the contest end.

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

      Thanks for the link, from here we can solve the problem in $$$O(15^3*log(S))$$$. Notice that using denominator of the generating function given in the link, we can write the recursion for the answer. The recursion is as follows:

      $$$ f_n = f_{n-1} + 2f_{n-2} - 2f_{n-4} - 4f_{n-5} + f_{n-6} + 3f_{n-7} + 3f_{n-8} + f_{n-9} - 4f_{n-10} - 2f_{n-11} + 2f_{n-13} + f_{n-14} - f_{n-15} $$$

      Next, you can simply use matrix exponentiation. But, can someone provide a proof of this recursion?

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

        Notice that using the denominator of the generating function given in the link, we get the recursion, can you elaborate on how did you arrive at it?

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

          When we simplify the polynomial in the denominator, we get

          x^{15}-x^{14}-2x^{13}+2x^{11}+4x^{10}-x^9-3x^8-3x^7-x^6+4x^5+2x^4-2x^2-x+1

          When we equate it to zero and consider x^15 as fn then I get the recursive formula you mentioned, but why does this work?

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

        Update: This works because of the formula from General Linear Recurrences

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

      AC solution

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

    I wonder if it can be solved with matrix exponentiation.. or probably it has something to do with generating functions as atcoder is helplessly in love with convolutions these days.

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

How to solve D?

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

    There can be at most 10 distinct characters. So you have only 10! possible assignments, just try them all.

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

      Why? Isn't each string is of max length 10. So, no of distinct characters min(26,len(s1)+len(s2)+len(s3))?

      Is there any proof?

      EDit: Got it. Because only 10 numbers are present.

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

        If there are more than 10 distinct characters it is impossible

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

        Say there were 11 characters. All of them must have distinct assignments. But there are only 10 digits. So, 2 characters must have the same assignment — not allowed.

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

    brute force all 10! permutations

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

    Try to assign the available letters different integer values and see if the equality $$$N_1 + N_2 = N_3$$$ holds the complexity is something like 10! like this https://atcoder.jp/contests/abc198/submissions/21669254

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

which TC am I missing? https://atcoder.jp/contests/abc198/submissions/21665135

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

From the editorial on F (https://atcoder.jp/contests/abc198/editorial/1080):

This time, the carry is at most $$$t$$$, so we only have to consider the range $$$0\le j\le 5$$$.

What does this mean? Does anyone know what $$$t$$$ refers to?

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

For F, consider the solution : Link I built all the general transformations from original cube and then applied burnside lemma. For each unique transformation, I got connected components and their sizes and from then I solved using matrix exponentiation for each of them. Time Complexity should be (16*16*16*6*log(6) {for building all the states} + 24*(2^6)*(6*6*6)*log(S) {for calculating answer corresponding to all unique states})

→ Reply