maroonrk's blog

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

Please note the unusual start time.

We will hold AtCoder Regular Contest 118.

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

We are looking forward to your participation!

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

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

Problem B. Republics don't have kings!

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

    "The king has decided" should be replaced with "a bill has been introduced".

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

Now that the contest is over.. what the hell was A????

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

    The tax included prices are strictly increasing, so if the tax included price of integer $$$A$$$ is $$$X$$$, there are $$$X - A$$$ skipped integers before $$$X$$$. Now you can use this to find some closed formula, or just binary search.

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

    just break that division into A+(t*A)/100

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

Me in the contest

  • Work on A for 50 minutes, WA
  • Work on B for 50 minutes, WA
  • Finish C in 10 minutes
  • Reverse the order of numbers to process on B, got AC
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In problem C how to go beyond 2333 elements!

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

      Use 14 and its multiples to generate the remaining numbers.

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

        Sorry my solution was to split into 3 groups.. multiples of 6, 15 and 10. The first group will not have 5 as factor, second group will not have factor as 2 and third group will not have a factor as 3. This only gave 2333 elements

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

      I used multiples of $$$[6, 10, 15]$$$:

      $$$ 6, 10, 12, 15, 18, 20, 24, 30, \dots $$$

      The only thing to notice is that when $$$n=3$$$, we should output $$$[6, 10, 15]$$$ instead of $$$[6, 10, 12]$$$.

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

For A, the answer is simply $$$n + \left\lfloor\dfrac{100 * n - 1}{t}\right\rfloor$$$.

The original formula is $$$n + \left\lceil\dfrac{100 * n}{t}\right\rceil - 1$$$.

$$$n + \left\lceil\dfrac{100 * n}{t}\right\rceil$$$ is the $$$n$$$-th number which has a gap between it and the previous number. So $$$n + \left\lceil\dfrac{100 * n}{t}\right\rceil - 1$$$ is the $$$n$$$-th missing number.

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

    Can you please share — how does the formula come?

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

Hamiltonian cycle is hard to come up with in D, rest of the proof can be done using a primitive root of the given prime.

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

    How to make it seem natural? I mean I can see what editorial wants to say but I doubt if I can come up with something like that in 2 hours.

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

How to pass the "numerical_error" tests in B ?

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

    Take 1/MN common and Now try to minimize the max of |Bi*N — Ai*M|

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

    You can have a look on my solution , it has no scope for numerical error . The basic idea is that either the value of Bi will be ceil of((Ai*m)/n) or floor of((Ai*m)/n Link to the solution https://atcoder.jp/contests/arc118/submissions/22475125

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

      How to prove Bi will be ceil of((Ai*m)/n) or floor of((Ai*m)/n,I just know it is greater or equal to ceil of((Ai*m)/n).

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

        Because if you take exactly (Ai*m)/n in decimal for all numbers, the sum would be m and all differences would be 0. Since you can't take decimal it would be optimal to either take the floor or ceil

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

        We can consider Ai as Ai blocks of size 1 which in total are N , same we can consider Bi as Bi blocks of size 1 which in total are M , So if Ai is x , The value of Bi should be corresponding to x to minimise (Ai*m)/n .So either it will be floor or ceil as we have to make other Ai's and Bi's in the same ratio close to each other as well. This is how I thought it , If you are looking for formal proof then I just dont have it .

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

      i did the same Submission
      got WA on 50/60 cases :(

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

        According to my understanding of your code , you are only trying to reduce the difference for first x no. and leaving the last few no.s on their own . You should consider that I had made a vector of pair to minimise it.

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

Thanks for the nice contest. Problem C involved much minor detail. I solved by making 4 sets. Let p1 = 2, p2 = 3, p3 = 5. Then,3 sets that include 2 of them but not third and lastly a fourth set which has all 3 of them. I saw that 167 numbers were left after I included first 3 sets, then I included the 4th one which gave extra 10000/30 numbers, exactly what I wanted.

For Problem B, I saw that the question is effectively to reduce abs(Bi*n — Ai*m). Given that sum of Bis = M. So, I first took Bi*n as Ai*m — (Ai*m)%n = Ci — Di, so, I have to distribute sum of Di to Ci — Di such that each value I give is a multiple of n(and that should be just n otherwise we would increase the maximum of abs(Bi*n — Ai*m)). Also, sum of Di is a multiple of n. So, just found out t = sum of Di / n and then go on giving n to first n maximum Di. Finally, obtain the Bi by dividing each found term by n.

For problem A, I observed that the number is the first number m, where t*m >= 100*n, then ans is m + n -1.
A
B
C

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

Just a suggestion or request , please make A a little bit easier from next time in ARC's because if A is like todays A it decreases Number of Participants Significantly. :)

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

Am I the only one who feel C < B < A ?

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

    No . :)

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

    Agreed, though I would say its maybe C = B < A

    C was a fairly easy constructive problem once you realize how to do better than the naive answer of using all combinations of 12 primes.

    B is pretty clearly binary search from the statement, and the checker function is fairly simple as well.

    A for me was basically, print sequence for various t, print differences between terms, guess that the differences have period t and sum them up like that. I still have zero clue why it works.

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

      C was much based on constraints and too so close. :(

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

        I mean the limit on a_i is what makes the problem interesting in the first place. If it was $$$a_i \leq 10^{18}$$$, the the naive idea using all combinations of the 12 smallest primes for $$$n - 1$$$ places would work.

        Also looking at your code I think you overcomplicated the implementation a bit, the main logic of my solution was less than 10 lines.

        My idea was to make $$$a_1 = 3 \times 5 \times 7$$$, then take all numbers which divide at least one of $$$6$$$, $$$10$$$, or $$$14$$$ in increasing order. Clearly $$$gcd(a_1, a_i)$$$ is now greater than 1 as it can be divided by at least one of $$$3$$$, $$$5$$$, or $$$7$$$, and $$$gcd(a_i, a_j)$$$ for $$$i, j \gt 1$$$ has $$$2$$$ in common. Note that we go in increasing order, so our first $$$3$$$ numbers will be $$$3 \times 5 \times 7$$$, $$$2 \times 3$$$ and $$$2 \times 5$$$, so the total gcd is already guaranteed to be $$$1$$$. This generates a sequence of length around $$$2600$$$ for which any prefix satisfies the condition.

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

          yes, I overcomplicated it as I was trying some solution and then adding some more to fulfill the constraints. But your thinking was much simpler and easier to implement. Thanks.

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

      You can find my solution to A above, which is much simpler than the official solutions.

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

For C, what would be the max possible N that still satisfy the conditions of the problem? I know it can definitely go above 2500.

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

    N<=2666

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

      Well, the editorial proposes multiples of $$$6$$$, $$$10$$$, $$$14$$$, $$$22$$$ and $$$1155$$$ ($$$2\cdot 3$$$, $$$2\cdot 5$$$, $$$2\cdot 7$$$, $$$2\cdot 11$$$ and $$$3\cdot 5\cdot 7 \cdot 11$$$) and does achieve $$$2926$$$ possible numbers this way. So this disproves $$$2666$$$ as upper limit. But can we go still further?

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

      So, with my acute lack of mathematical proof I decided to write a program, which tries seeds with the given tasks conditions ($$$gcd(all)=1$$$, $$$gcd(pair)\neq 1$$$) and then counts how many possible numbers this seed can create (according to the same procedure as in the editorial):

      Program

      The results are as following:

      Result

      So it seems, that $$$2926$$$ is the maximum achievable number!

      This obviously still misses the formal proof, that such an approach yields the optimal answer. But I personally feel confident about this, after analysing the problem. Also the resulting seeds have a really specific symmetry (all but one are made by multiplying $$$2$$$ with the smallest prime numbers, and the last one is made by multiplying all the used primenumbers except the $$$2$$$), which makes it very plausibel.

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

Nobody even mentioning E-F, I see.

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

    What is there to say about them? They both look like exercises for those in the know: the idea behind GCJ 2008 Round 3 — Endless Knight is used as a trivial observation in E; and the editorial for F has a link to an ARC 033 problem back from when the rounds were in Japanese only. The point values are irrelevant as usual, the motivation behind spending such problems on regular rounds (esp. two problems on one round) is over my head as usual.

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

      What is there to say about them?

      The rest of your comment serves to answer that question.

      I found nice the idea in E that if we sum up inclusion-exclusion formulas over all ways to replace $$$-1$$$, it helps ensure that we're summing up over permutations since inclusion-exclusion over RD paths ignores non-monotonous subsets of forbidden cells. Not super revolutionary though.

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

    Problem E can also be solved without PIE, but by a simple DP in which the state is the current position of the path and how many blocks we have fixed left/above of this position (seperate values for blocks above, left and above+left) See my solution for details.

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

      Thanks! Your idea is great and very helpful for me. It's easy to understand your DP. :)

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

I have always found the questions of atcoder to be good, but sadly you cannot solve atcoder questions by selecting topic tags or by selecting the difficulty level. Does anyone know of any atcoder problem recommending site? Thanks in advance .

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

How about D? I can understand the correctness of the official edtutorial. But what's the idea to make us jump the gap from G(a,b) to G(a,b)=m*n=P-1? Is there a prior knowledge for that? Any idea will be appreciated.

→ Reply