maroonrk's blog

AtCoder Regular Contest 113 Announcement
By maroonrk, history, 4 years ago, In English

We will hold AtCoder Regular Contest 113.

The point values will be 300-400-500-600-800-1000.

We are looking forward to your participation!

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

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

Clashes with open cup. Can it be pushed an hour?

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

    I'm sorry, but we can't move the contest time. Maybe you can virtual-participate in the Opencup.

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

    Clashes with innopolis-open finals as well

    Edit:doesn't clash(I thought innopolis is 5 hours instead of 4)

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

This contest will be hold on the old rating system, right?

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +24 Vote: I do not like it 
was C easy than B ?? or its only for me ?
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    C was easy than B but solution of B was on internet so lot of people solved it very quickly .

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

    I found A the hardest in A,B,C

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

New difficulty staircases with a wall

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

    Who solved F are in almost 2000-st place because F costs 110min...

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

      Thats why there a wall. You either choose ABCD(and E?) or F

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

If you're having trouble working out the edge cases, B can be solved with Berlekamp-Massey: https://atcoder.jp/contests/arc113/submissions/20391652

code

Edit: I solved it the traditional way first.

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

    Killing a mosquito with a bazooka.

    Why edge cases though? Couldn't you hardcode the periods of powers of 0-9, and use that?

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

    You can also notice that all the numbers 0-9 will repeat the same ones digit every 4 powers.

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

    For B, here's a simpler solution.

    We know that $$$A, B, C > 1$$$ and the modulus is 10. The period is always a divisor of 4, so it suffices to find $$$B^C$$$ modulo $$$4$$$, say $$$x$$$, and find $$$a^{x + 4}$$$ modulo $$$10$$$.

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

Problem B was already available on Stackoverflow (*_*).

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

how to solve D

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

    Let $$$n>2,m>2$$$. Then observe that the only constraints on $$$A$$$ and $$$B$$$ are that $$$\forall i, B_i > max(A)$$$. So, we can find for a given maximum $$$x \in [1,k]$$$ the number of different sequences $$$A$$$ such that $$$max(A) = x$$$, which is $$$x^{n} - (x-1)^{n}$$$. Then, the number of sequences $$$B$$$ such that $$$B_i \geq x$$$ will be $$$(k-x+1)^m$$$. Multiply these values and add them for all $$$x$$$, and you have your answer.

    Handle $$$n=1$$$ and $$$m=1$$$ separately.

    Complexity is $$$O(k(\log m + \log n))$$$.

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

      can you please tell why number of different sequences $$$A$$$ such that $$$A_i<=x$$$ is $$$x^n - (x-1)^n$$$ . Shouldn't it be just $$$x^n$$$.

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

        I should have made it clear — the maximum of $$$A$$$ is $$$x$$$, so that means there must be at least one $$$i$$$ such that $$$A_i = x$$$. This is why I subtract $$$(x-1)^n$$$, to remove all the sequences where the maximum value is less than that. I'll edit the comment to reflect that.

        By the way, \leq for less than or equal to sign

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

        At least one of them should be x.

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

      In the first line of the comment, I think it should be Bi >= max(A) instead of Bi > max(A) ??

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

    The answer turns out to be the number of monotone $$$k-$$$weightings of a complete bipartite digraph with $$$n$$$ vertices on the left and $$$m$$$ on the right for $$$n, m > 1$$$. For $$$\min(n, m) = 1$$$ the answer is $$$k^{\max(n, m)}$$$.

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

Why problem E is sooooooooo much harder than D (

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

My somewhat readable solutions for anyone interested:

A
B
C
D
→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 6   Vote: I like it +5 Vote: I do not like it

    Edit:Brute force is actually $$$O(n \ log \ n)$$$ (?) but i'm not sure... It is $$$\sum_{i=1}^n \frac{n}{i}$$$

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

      True, now I get how even low rated people solved this in 2 minutes :P

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

    A can also be done with 3 forloops from 1 to n if you just break the loop when i*j>n or i*j*k>n.

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

      Ah... now I feel stupid, after missing such a neat solution XD.

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

    why are u choosing <= i as maximum for m but exact i for choosing minimum in D??

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

      Would you mind elaborating? I didn't get your point?

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

        like lets say question was maximum in row and maximum in column, then we take exact i instead of <= i for both row and column, we do that by $$$ i^n - (i-1)^n $$$ , but here we are not doing like that why??
        link i read from here
        for our version we need minimum for first n elements, so i thought we must need exact i, so it must be $$$({i,i+1,....k})^N/({i+1,....k})^N $$$

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

          I think we can do this here too.
          The only critical observation was this:
          $$$B_j \ge \max_{1 \le i \le n}(A_i)$$$ $$$\forall$$$ $$$1 \le j \le m $$$
          Now What I do is iterate from $$$i=1...k$$$ and for each $$$i$$$ we can find the number of $$$A's$$$ which will have their maximum value to be exactly equal to $$$i$$$ by $$$a_i=i^n-(i-1)^n$$$ now once we've got this. The final task at hand is to find all possible $$$B's$$$. And that'd be equal to $$$b_i=(k-i+1)^m$$$ (as we don't really care what the elements of $$$B$$$ are as long as they're all greater than $$$i$$$ so we can choose any of the values from $$$i \dots k$$$ for each of the $$$m$$$ values of array $$$B$$$). Hence our answer $$$s$$$ would just be given by $$$s=\sum_{i=1}^n(i^n-(i-1)^n)(k-i+1)^m$$$

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

    O(n) solution

    not so difficult to understand （ actually too lazy to explain ）

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

      This is $$$O(n^{3/4})$$$.

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

        oh sorry for that （ by the way % ATS ）

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

I believe I have missed one out of 12321 cases in E.

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

Problem D was similar to this but with weaker constraints.

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

why is this wrong for D

Spoiler


https://math.stackexchange.com/questions/3260717/how-to-count-the-number-of-different-sequences-possible?noredirect=1

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

So I printed (max(n,m)+k-1 choose k-1) instead of k^max(n, m) in D and failed to see this bug for 10 mins. Cost me over 1100 places :thonkms:

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

B can be solved without period observation.
let's define f(a,b,c) = a^b^c = {a^b^(c/2)}^b^(c/2)
then f(a,b,c)=f(f(a,b,c/2),b,c/2) so we can do DP.
https://atcoder.jp/contests/arc113/submissions/20381459

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

So lucky to have E accepted at the last 3 minutes. I was wondering if F is easier than E when I was reading the problems and tried to work F out for tens of minutes, fortunately I did not continue doing that...

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

Sad.Problem E always wrong on test 1,2. AC another 44 tests.

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

So, how to solve E?

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

    There are so many situations to consider: note that we can almost keep all b's except some special cases, and cancel all the a's to 0 or 1 if we want, the problem becomes "how to arrange the rest of a's" and "how many a's we can keep at the end of the final string".

    1. All the a's are at the beginning: we cannot do anything to make b at the beginning, so we should keep 0 or 1 a at the beginning(depending on the parity of number of a's) and keep all the b's.

    2. There are some a's at the end: we should move the continuous a's to the end by an operation, and by one operation with $$$k$$$ continuous a's we can increase the length of suffix with all a's by $$$k - 2$$$, so we only move those larger than 2 to the end.

    3. No a's at the end: if the parity of total number of a's is even, we just cancel all the a's, otherwise, we must keep some a's between b's, or we need to remove (at most 2) b's to make a's at the end. When the suffix of b's is no longer than 2, we can keep the last a and remove any other a's, otherwise, try to keep the longest suffix of a's by removing 2 b's.

    I haven't found a "clean" solution yet...

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

This is the second time I participants in ARC, and it's difficult for me as usual.

I tried my best and solve the first four problems, after this, I'm almost exhaust and didn't have too much time thinking about the rest.

I can't understand why all the people around me are saying:"The first four problems are very simple!", maybe it just because I'm too weak to join ARC:(

All in all, I hope all of you can enjoy the contest, just like I did!

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

Can anyone tell me what is the difference between these 2 codes for B, and why doing +4 is important? I also checked 'b' is never -ve when I submit it.

AC code: void solve(){ ll a, b, c; cin >> a >> b >> c; b = power(b, c, 4)+4; a = power(a, b, 10); cout <<a << endl; return; }

WA Code: void solve(){ ll a, b, c; cin >> a >> b >> c; b = power(b, c, 4); a = power(a, b, 10); cout <<a << endl; return; }

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

So, how to solve F？Could anybody tell me the expanation of dp[i][j][k] -> dp[i + 1][j][k + 1]'s "weight" is 1/(k+1)

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

While the problems are different, D is awfully similar to this Codechef Long problem from 2019, the same idea works to get the formula in both too.

Edit: Just noticed that it was pointed out above too.

→ Reply