Блог пользователя maroonrk

Автор maroonrk, история, 4 года назад, По-английски

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!

  • Проголосовать: нравится
  • +100
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Could someone explain how to solve C?

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

    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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится -36 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +57 Проголосовать: не нравится

        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.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +29 Проголосовать: не нравится

        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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks!

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    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.

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +15 Проголосовать: не нравится

    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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thank you for the explanation!

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can You Please Explain, why it repeats.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve B and C problem?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Can you prove optimality?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

        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.

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

        (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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

        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

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится +5 Проголосовать: не нравится

            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.

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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.

»
4 года назад, # |
  Проголосовать: нравится +197 Проголосовать: не нравится

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)

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    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." ?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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)$$$?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Clean AF. applause

»
4 года назад, # |
  Проголосовать: нравится +73 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      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)

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.)

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +34 Проголосовать: не нравится

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