maroonrk's blog

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

We will hold AtCoder Regular Contest 109.

The point values will be 300-400-500-600-700-900.

We are looking forward to your participation!

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

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

Could someone explain how to solve C?

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

    Let $$$\mathrm{dp}[k][i]$$$ be the symbol of the winner for a tournament that starts from position $$$i \pmod{n}$$$ and has $$$2^k$$$ players. Hopefully the transitions are obvious.

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

      https://atcoder.jp/contests/arc109/submissions/18471624 can you please help me find where my code fails ?/

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

        Have you tried the following:

        • Write a very naive and simple solution to the problem (maybe exponential complexity) (if you can, you may also just copy someone else's solution)
        • Write a program to generate thousands of small (!) test cases
        • Using those two, find a test case where your program gives the wrong answer
        • Use print statements or a debugger to see where exactly your program does the wrong thing.

        98% of WAs and REs can be resolved this way. I don't have time to delve into every code I'm sent, it's much harder to debug somebody else's code and being able to debug your own code is a valuable skill. It is also a very routine process that can be learned much faster than problem solving and algorithms.

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

          Can you please share your code for generating smaller test cases

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

            Is it really so hard to write a program that generates a random string of R, P and S?

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

        A bit unrelated, in your code you use the std::pow(double x) function to compute integer powers of 2. This is bad and will sooner or later give you WA because of precision errors; it's better to write your own pow function that works on integers.

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

      Thanks!

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

    If $$$k$$$ is small, you can repeat the string $$$s$$$ until its length is at least $$$2^k$$$ and then simulate the competition ($$$s_0$$$ with $$$s_1$$$, $$$s_2$$$ with $$$s_3$$$, and so on).

    To solve for bigger $$$k$$$, observe that at some point the match results in the current round repeat themselves (just like how we repeated $$$s$$$ at the beginning). So if length of $$$s$$$ is $$$2m$$$ (even) then you know that the result of 1st match is the same as the result of $$$(m+1)$$$-th, $$$(2m+1)$$$-th, $$$(3m+1)$$$-th match. In the case of odd-length $$$s$$$, we double it to make it even.

    Now after every iteration, you have a string which is the period of the string of results of the last round meaning you can reapply the algorithm above until $$$k=0$$$.

    To simplify this further, I don't care about the parity of length of $$$s$$$ and always double it on every iteration. After every iteration, the length is divided by two anyway so the length remains constant throughout the algorithm.

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

    Players 1,2 do the first match, players 3,4 the second and so on. Let w(x,y) be the symbol of the winner of a match. Then after 1 round, the symbols of the remaining participants look like

    w(s[1],s[2]),w(s[3],s[4]),w(s[5],s[6]),...

    So we can implement that winner function as given in statement, and create the string of the next round in a loop k times. Then ans is s[0], since this is the last participant. Note that we allways need to create the string of the next round only up to the length of the original string, because then it repeats. Submission

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

      Thank you for the explanation!

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

      Can You Please Explain, why it repeats.

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

        It repeats by definition of which hand is used by player i. If n is even, then it repeats after n/2 matches, because in each match two players are "used". If n is odd it repeats after n matches. So we are on the save side if we allways calculate it up to n.

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

How to solve B and C problem?

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

    B: Simplest strategy would be to buy n items, 1..n. But of course we can do better.

    First we can buy the item n+1 and split it to 1 and n. This saves one buy. Second we can buy the item n and split it to 2 and n-2. Third we can buy the item n-1 and split it to 3 and n-1-3. ...

    So we can save one buy as long as i+sum(1..i)<n. We can calculate that in a loop. Code

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

      Can you prove optimality?

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

        Well, no... We would somehow need to proove that this strategy gives to most possible splits.

        Intuitivly it does because we allways buy the biggest possible item, which has from its size the best potential to be split into other items.

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

        We just have to get a sum that is greater than n*(n+1)/2.

        so let us say that we will take all elements after x in the list of (n+1) elements.

        (n+1)*(n+2)/2-(x)*(x+1)/2 >= n*(n+1)/2

        solving this we will get the answer.

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

        (Just for proof purpose)
        Well, The idea I use is quite straight forward. We want $$$1\,,2...N$$$ from $$$1\,,2...N,\,N+1$$$ so the problem can be formulated as we want $$$X_1+X_2+...+X_k>=N(N+1)/2$$$ such that $$$k$$$ is minimum and all $$$X_i(s)$$$ are different. So it's quite obvious that we pick Top(Max) $$$K$$$ numbers $$$(N+1)+N+(N-1)+...+X$$$ s.t. sum becomes at least $$$N(N+1)/2$$$. Clearly we can see that first few numbers $$$(1,2,...X)$$$ should be splitted from $$$(N+1)$$$ and remaining comes directly. So we can find maximum value of $$$X$$$ such that $$$X(X+1)/2 <=N+1$$$. And we can obtain such $$$X$$$ for ex. using Binary Search.

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

      I saw tourist's code where he used binary search but could not get the approach.

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

        It is based on the same formular, but not loop until n is reached, but instead binary search for the number of loops necessary. Which has obviously better complexity.

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

        Binary search for the max number of elements you can get by breaking (n+1)th log. The max number of elements you can get is obviously by breaking it into smallest of pieces i.e. 1,2,3,4...

        Now the sum of these elements should be less than or equal to (n+1). So binary search for 'x' such that (x*(x+1))/2 <= (n+1) i.e. sum of first x natural numbers less than or equal to (n+1).

        After getting this, you can buy these 'x' elements with 1 coin, and the rest of (n-x) elements with (n-x) coins.

        Total answer is (n-x+1).

        Code

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

          How to prove that this kind of strategy is always optimal.

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

            I don't have a mathematical proof but this is why I thought this would work.

            We can get first 'n' elements using 'n' coins. Which leaves us with (n+1)th log. Obviously now we would want to maximize the number of logs we can get through this because each log has SAME PRICE i.e 1 coin. So it doesn't matter what size you break it into, but the number of logs should be maximized.

            An argument can be why shouldn't we break this into 'k' pieces and then try breaking some other log into some 'm' pieces. Say if n=10, we break 11th log to 5+6 and 10th log to 1+2+3+4. Now it leaves us with to buy 7,8,9,10. First observation that now we can't get 10. Because we broke 10 into smaller pieces. Anyhow even if we didn't, we can notice, the answer will always be greater than if we broke (n+1) optimally. I don't have the proof for this mathematically, but this was my intuition.

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

            Here is a formal proof.

            It's clear that we want to buy the longest set of logs, so we can reformulate the problem as choosing the largest $$$x \geq 0$$$ such that we can form {$$$1, 2, ..., n$$$} from {$$$x + 1, x + 2, ..., n + 1 $$$}.

            Now if $$$x(x + 1) / 2 \leq n + 1$$$, the log of length $$$n + 1$$$ can be partitioned to form {$$$1, 2, ..., x$$$} and the rest can be directory formed from {$$$x + 1, x + 2, ..., n$$$}, so the largest such $$$x$$$ gives us a lower bound.

            To form logs of lengths from 1 to $$$n$$$ we must satisfy $$$sum($$${$$$x + 1, ..., n + 1$$$}$$$) = (n + 1)(n + 2) / 2 - x(x + 1) / 2 \geq sum($$${$$$1, ..., n$$$}$$$) = n(n + 1) / 2$$$. However, $$$x(x + 1) > n + 1$$$ implies $$$(n + 1)(n + 2) / 2 - x(x + 1) / 2 < (n + 1)(n + 2) / 2 - (n + 1) = n(n + 1) / 2$$$, which implies the sum of the lengths of the logs is smaller than $$$n(n + 1) / 2$$$, so we can't form logs of lengths from 1 to $$$n$$$. This proves that largest $$$x$$$ that satisfies $$$x(x + 1) / 2 \leq n + 1$$$ is also an upper bound, which implies that this is also optimal.

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

Clean solution to D:

If we make the transformation to the centroid of the triangle, then each possible triangle corresponds to exactly 1 possible centroid location. These centroid locations form a grid with 4 points inside every 1x1 box (with uneven spacing, but this doesn't matter), on which you can move to any of the 8 adjacent points except diagonal through a corner.

After making this transformation and labeling the points by their row and column $$$(x, y)$$$ in the centroid grid, the answer is $$$\max(|x|, |y|)$$$, unless we're exactly on the diagonal that we can't move freely on, in which case you can add 1, unless you're already in the same 1x1 cell as your target.

auto [x, y] = transform(target);
int ans = max(abs(x), abs(y));
if (x == y && x != 0 && x != 1)
    ans++;

(https://atcoder.jp/contests/arc109/submissions/18474121)

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

    Can someone please explain, why after the transformation the answer is "After making this transformation and labeling the points by their row and column (x,y) in the centroid grid, the answer is max(|x|,|y|), unless we're exactly on the diagonal that we can't move freely on, in which case you can add 1, unless you're already in the same 1x1 cell as your target." ?

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

      Try drawing some paths on the grid above, I think you should be able to figure it out.

      A simpler problem to consider: how many moves does it take a king to move on a chessboard from $$$(0,0)$$$ to $$$(x,y)$$$?

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

    Clean AF. applause

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

I solved E with finding the differences between the numerators (2^n * the answer array) and searching it on OEIS.

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

    Could you please explain how to search it on OEIS specifically? I tried to do like this but I failed. One reason for this is maybe that I am not familiar with OEIS so can you help me?

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

      Take the third sample as an example:

      First multiply the answer array by $$$2^{19}$$$ and we get something like

      $$$4980736,4980736,4980742,4980782,4981006,4982158,...$$$

      Find the differences:

      $$$0,6,40,224,1152,...$$$

      Search $$$6,40,224,1152$$$ on OEIS leads you to A229580 with an O(n) formula. (It's easy to see that $$$ans[i]=ans[n+1-i]$$$ so we only calculate the first half)

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

This is kind of random, but why is ARC 109 missing the "Discuss" link that points to this post? (At https://atcoder.jp/contests/arc109, normally there's a "Discuss" tab that links to CF.)

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

B: #include <bits/stdc++.h> #define ri register int #define ll long long using namespace std; ll n; int main() { scanf("%lld",&n); ll l=1,r=n; while(l<=r) { ll mid=(l+r)>>1; if((2*n+2)/mid>=mid+1)l=mid+1; else r=mid-1; } printf("%lld\n",n+1-r); return 0; } Why is this code correct? I cannot understand the division in the bisection method. "(2*n+2)/mid>=mid+1" has no error?

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

There is a hack in problem F.

Input

42
wwwwwwwwwwwwbbbbwwbbbwwbbbbbbbwwwwwwwwwwww
____o___________oo___oo__________________o

Output
8

One of optimal solution :

44(b) -> 17(w) -> 18(w) -> 22(w) -> 23(w) -> 5(w) -> 43(b) -> 42(w)

Many submissions failed this testcase including tourist's(https://atcoder.jp/contests/arc109/submissions/18464249).

One correct submission by ksun48:(https://atcoder.jp/contests/arc109/submissions/18467968).

You can check the difference between my submissions.

(should be wrong)

https://atcoder.jp/contests/arc109/submissions/32177114

(should be correct)

https://atcoder.jp/contests/arc109/submissions/32177316

Can you update the testcases?maroonrk

→ Reply