maroonrk's blog

AtCoder Regular Contest 139 Announcement
By maroonrk, history, 3 years ago, In English

We will hold AtCoder Regular Contest 139.

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

We are looking forward to your participation!

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

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

Let's go in 10 minutes.

700 for C and D (o_O)

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

good luck guys

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

good luck！

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

I think B in this contest is really hard.Who can give me some advice?Thanks.(I'm unrated.)

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

    sorry

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

      Mr. Dragon,I know it is so easy for you to solve this problem .Although I tried my best to solve it by this way,I still have no idea .So can you tell me more advice?

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

        Hey bros, contest is still running now.

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

    e

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

    Hey bros, contest is still running now.

    Although you're unrated, there are some guys which are rated will look into this comment.

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

      e

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

        The Chinese CPers' jargon words in his comment(Rev. 1):

        konjac=蒟蒻(jǔruò), pronounced similarly to 巨弱(jùruò), a informal word to represent the fact that CP is someone's weak point.

        a province or a school is weak means students, teachers or instructional resources in it are not good.

        big guy=大佬=someone good at CP.

        Chinese CPers tend to be modest, so his words may be fake.

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

    greedy . Maybe three points. https://atcoder.jp/contests/arc139/submissions/31243156

    Set a threshold, and then consider that it must be B,C is the best, and then 1 completes N.

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

    I just solved it using square root decomposition, so if either A or B is greater than $$$\sqrt{N}$$$ than there are only $$$O(\sqrt{N})$$$ cases to consider, and if they are both less than that, then there are only $$$O(\sqrt{N})$$$ possible remainders that can arise from dividing with A or B. I think I overcomplicated it lol

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

What a Div.0 round!

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

This round is toooooo hard!!!!!!!!!!

I really miss the old days when ARC's hard problems are not always modulo $$$998244353$$$ problems!

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

    This round is harder than early AGC rounds...

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

      Judging by this ARC and the last one, I really don't know why ARCs are not rated for reds...

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

damn this contest is crazy hard, compared to the other regular contest

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

Deleted.

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

    Why your atcoder account has been banned?

    Did you copy others code frequently?

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

      I used to,and I'm very sorry for that.

      I'm considering to delete this codeforces account.

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

Problem C was a nice problem. I solved it considering the function $$$f : A \mapsto B$$$, where $$$A = x + 3y$$$ and $$$B = 3x + y$$$, have to be an injective function and using the fact that $$$x = \frac{3B - A}{8}$$$ and $$$y = \frac{3A -B}{8}$$$, we can solve the problem pretty straightforwardly.

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

    idk how but straightforward bfs from (1,1) passes.

    just check if current pair (x,y) breaks condition if not include it

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

Does anyone have a strong testcase for B?

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

I think I am very lucky to solve problem B. I didn't come up with the arguments mentioned in the tutorials, but I just guessed that it is sufficient to find out the correct answer if we implement the following two loops.

At first, we use ny to denote the number of operation "increase P by A", Then, Loop 1, we check ny from 0 to 1e6. Loop 2, we start from (n/a) to (n/a-1e6). In each loop, we could compute the number of the other two operations, and thus we could update the answer.

I got the above "guess", since recently when I was trying to solve this problem, https://mirror.codeforces.com/contest/466/problem/B, I realize there may exist a general pattern. In this pattern, at first sight, we have to do bruteforce from 1 to 1e9, but with some observation, it is enough to reduce it to two independent loops, one from 1 to 1e6, and the other from 1e9 to 1e9-1e6. I am sorry that this is not a strict and precise description of this pattern, because I really don't know how to give it a clear statement, but you may find it out by yourself if you take a look at the problem of the above link.

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

anyone pls explain the logic of this submission , task A . https://atcoder.jp/contests/arc139/submissions/31236419

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

    Think the problem in a greedy way. We should make each $$$a_i(1\le i\le n)$$$ as small as it can be.

    Then Absolutely, $$$a_1=2^{t_1}$$$.Let $$$b_i=a_i\div 2^{t_i}$$$.

    Because $$$a_i>a_{i-1}(2\le i\le n)$$$, the smallest $$$b_i=\lfloor\dfrac{a_{i-1}}{2^{t_i}}\rfloor+1$$$.

    As $$$\operatorname{ctz}(a_i)=t_i$$$, $$$b_i$$$ should always be odd.If $$$b_i$$$ is an even number, then do $$$b_i\leftarrow b_i+1$$$.

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

Im not sure if I understand the editorial of B, can anyone explain please?

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

    First of all, consider the price/performance ratio, and sort it according to the price/performance ratio. Definitely, the higher price/performance ratio will be preferred, but there will be a problem, that is, when choosing the higher price/performance ratio, it takes up the space of the second price/performance ratio, making the choice of the second price/performance ratio and the third price/performance ratio not optimal. At this time, you can imagine that this deviation will not be very big, or even a three-point function? Then you can pass this question by setting a threshold.

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

B can be solved in $$$O(log^2)$$$, if we solve the subproblem: Find the minimum $$$x(l\leq Ax\%B\leq r)$$$ in $$$O(log)$$$ time. The subproblem once appeared in arc127f.

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

how to solve E,I cannot understand the Editorial of problem E.

if H is odd,why it can reach the upperbound for L $$$(H \times \frac{W-1}{2})$$$

Hope someone can give an example

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

In editorial of B, how did the we get this conclusion: "Thus, we can solve the problem by trying all possible numbers of uses of the operation “increase P by A” if ⌊N/A⌋<A−1, and those of the operation “increase P by B” otherwise"

I am getting this condition: try all x such that (N-A*x)/B <= A-1; x < N/A. This gives time complexity of : O(N/A)

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

By the way, when will the English editorial of ABC249 be released?

PCTprobability Kodaman

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

Could anyone explain how we would go about implementing B? Reading the editorial i got the fact that number of operations for A would be less than equal to floor(N/A) whereas those of B would be less than A-1. But how would one one implement in O(sqrt(N)) time?

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

Can anyone tell me in problem B, how the person who has submitted this code made an assumption on line 52 that iteration will less than 100000 times

→ Reply