chokudai's blog

By chokudai, history, 20 months ago, In English

We will hold AtCoder Beginner Contest 293.

The point values will be 100-200-300-400-500-500-600-600. We are looking forward to your participation!

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

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

What is the counter test case for this problem B's solution? I kept getting WA.

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

    5

    3 4 1 5 4

    For this test case, your code gives wrong answer.

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      1. It seems that this test case itself is invalid
      2. Even if this test case is valid, my code outputs 1 2 5, is it wrong?
      • »
        »
        »
        »
        20 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The number of elements in the answer is actually 3, but your code gives 2.

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

          Perhaps I misunderstood the problem statement, so the elements of the given array are not necessary to be distinct?

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

            Yes.

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

              Ok, I was so upset and left the contest so early not even bothering to read C, D, E.

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

today, re-learn how to sum the Geometric Progression :) good problem

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

Can't seem to get D to AC, failed 6 test cases. My idea is to label $$$2*i$$$ as blue and $$$2*i + 1$$$ as red for $$$i \in [1, n]$$$ and treat it as a graph dfs problem

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

    I treated i as red and i+n as blue. Then I used union-find.

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

    Probably, the problem is multiple edges

    Input

    1 1

    1 R 1 B

    Output

    1 0

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

    Colors don't matter, you can just DFS and check for cycles in each component

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

    I just treated the graph as undirected and used: no of components with cycle = m — n + no_of_connected components

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

My solution for each problem are explained below.

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

    Can you explain about the 2 by 2 matrix formula in the editorial for problem E? https://atcoder.jp/contests/abc293/editorial/5962

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

    $$$E$$$ can be solved simpler. Let $$$f(x) = a^0 + a^1 + \dots + a^{x-1}$$$. Then:

    If $$$x$$$ is even $$$f(x) = f(\frac{x}{2}) + a^{\frac{x}{2}} \cdot f(\frac{x}{2})$$$.

    If $$$x$$$ is odd $$$f(x) = a^0 + a^1 \cdot f(\frac{x}{2}) + a^{\frac{x}{2} + 1} \cdot f(\frac{x}{2})$$$.

    Write simple recursion.

    About problem $$$F$$$. I precalculated answers and carefully looked at it. Then I calculated $$$a_x = \sqrt[\leftroot{-2}\uproot{2}x]{n}$$$ for all integer $$$x$$$, which are meaningfull. Then simply tried all numbers in ranges $$$[a_x - 10, a_x + 10]$$$. I have no idea, why it is correct.

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

      Oh cool, this is much easier to understand. Thanks! I tried so hard to use the sum formula with mod inverse, little did I know that depending on M, it may not even exist :(

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

        Can you help me understand it please please

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

          If x = 4: f(x) = a^0 + a^1 + a^2 + a^3 = (a^0 + a^1) + a^2 * (a^0 + a^1) = f(x / 2) + a^(x / 2) * f(x / 2).

          If x = 5: f(x) = a^0 + a^1 + a^2 + a^3 + a^4 = a^0 + a^1 * (a^0 + a^1) + a^(x / 2 + 1) * (a^0 + a^1) = 1 + a * f(x / 2) + a^(x / 2 + 1) * f(x / 2).

          Hopefully this helps you understand the recursive formula.

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

      .

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

        return 1%m;

        E is tricky that a^0 is not necessarily 1. When m==1, (a^0) % m is 0.

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

          got accepted thanks

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

          i forgot to add that case thanks for clearification

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

    What is reeds sloane template where to find it

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

      It's an algorithm that finds linear recurrences given the sequence's first few values. The template is on here but I can assure you there are very few moments when you actually need it to solve a certain task (again, I used it because I was lazy)

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

Soltuion for d :

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

Solution for problem E using simple recursion Source Submission

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

Solution to F: It is possible to write a function that checks if a number x can be written in base b with 1s and 0s like this:

Code

If the number written in the base b has many digits it means that b is small. If b is large it means that the mask (representation of n in base b) has few digits. By defining the threshold at 6 digits it means that we can check b until $$$\sqrt[6]{maxn}\leq\sqrt[6]{10^{18}}=1000$$$. And then we have large b's left (with few digits in the mask). We can check all the masks up to 6 digits and do a binary search to find if there is a b that matches the mask.

My implementation

Total complexity per test case: $$$\Theta((1000+2^6)\log_b n)$$$

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

    Wow, it seems that we have similar ideas(see my comments below). But, I don't have enough time to finish it during contest, and only solve it after contest.

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

Somehow I used an ugly method to solve problem F (after contest).

For some base-b, at first we check all the combination of patterns (1/0)b^0+(1/0)b^1+...(1/0)b^4, and find all the valid b. Then, note that we have at most 10^(18/5) other candidates to check, and it suffices to implement brute-force for this part (this is beacuse we must start from at least b^5, and valid b must satisfy b<=10^3.6).

But I think the editorial's idea is better to understand.

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

Can anyone explain the winner's (maspy) elegant solution to problem E?

https://atcoder.jp/contests/abc293/submissions/39612056

A, X, M = map(int, input().split())
if A == 1:
    print(X % M)
else:
    mod = M * (A - 1)
    x = pow(A, X, mod) - 1
    x //= (A - 1)
    print(x % M)
  • »
    »
    20 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    I think I might have an explanation to the "else" part.

    The original problem is equivalent to computing (a/b)%c. Suppose that (a/b)%c=r, then we must have a/b=qc+r, and a=qbc+rb, then we compute a%(bc)=0+rb (because r<c, so rb<rc), and thus r=(a%(bc))/b.

    In fact, I decided to use this at first, but I kept getting WA at sample3 so I gave it up.

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

      Great explanation, thanks!

      This is true when $$$a \equiv_{\mathrm{mod}\ b} 0 $$$ (or in other words $$$a$$$ is divisible by $$$b$$$).

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

    It seems to be this obvious formula:

    Spoiler

    The if part avoids division by zero.

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

    If you want to calculate ans = (X/D)%m

    (X/D) = K*(m) + ans

    X = K*(D*m) + D*ans

    => X%(D*m) = D*ans

    ans = (X%(D*m))//D

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

    I actually had the same solution: https://atcoder.jp/contests/abc293/submissions/39630645

    The idea is that we need to divide by $$$X - 1$$$ in order to do the geometric sum formula, but the problem is that $$$X - 1$$$ may not have an inverse mod $$$M$$$ as we aren't given that $$$M$$$ is prime and large enough. So, we use the fact that if $$$Ar \equiv Br \pmod{Cr}$$$, then $$$A \equiv B \pmod{C}$$$. We calculate the numerator of the geometric sum mod $$$M(X-1)$$$ and divide both the residue and modulus by $$$X - 1$$$ in the end.

    You might also notice that $$$M(X-1)$$$ doesn't fit in a 32-bit integer, so even using long longs, multiplication will overflow, thus why both I and the person you referenced used Python.

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

what will be approach for C?

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

Is it possible to calculate a/b mod m for when b and m are not coprimes? I guess no in general right? (for values up to 10^18 for example). This would help in problem E if I knew I had to come up with a different approach. Is this common, realising you have to have a different approach because a/b is impossible?

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

    What do you mean by $$$a / b mod m$$$. For cases when inverse of $$$b$$$ modulo $$$m$$$ exists, then $$$a / b$$$ is defined as $$$a . b^{-1}$$$.

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

      Given 3 integers a, b and m 1<=a,b,m<=10^18 — calculate a/b mod (m). That is a divided by b mod m (or a/b%m in modular arithmetic I guess). Is it possible to solve this? Obviously it is possible when b has a modular inverse, but not possible otherwise?

      For example 10/2 mod 7 == 5 because the modular inverse of 2 mod 7 is 4. 10*4 mod 7 is 5

      And 9/2 mod 7 is 1

      And other example is 16/8 mod 8. Obvioulsy 16/8 is 2 and 2 mod 8 is 2. But there is no modular inverse of 8 mod 8.

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

E is tricky that a^0 is not necessarily 1. When m==1, (a^0) % m is 0.

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

How to solve E?

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

why 2/25 test cases are failing in problem C , can someone help me sumbission

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

    try this testcase:

    3 2
    1 2
    3 4
    5 6
    

    expected output:3

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

      thanks for the test case , base case was wrong:( , now got ac