maroonrk's blog

By maroonrk, history, 3 weeks 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

»
3 weeks 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)

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

good luck guys

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

good luck!

»
3 weeks 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.)

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -38 Vote: I do not like it

    greedy(((

    • »
      »
      »
      3 weeks 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?

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

        Hey bros, contest is still running now.

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

    e

  • »
    »
    3 weeks 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.

  • »
    »
    3 weeks 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.

  • »
    »
    3 weeks 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

»
3 weeks ago, # |
  Vote: I like it +33 Vote: I do not like it

What a Div.0 round!

»
3 weeks 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!

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

    This round is harder than early AGC rounds...

    • »
      »
      »
      3 weeks 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...

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it -78 Vote: I do not like it

Why do I find D easier than C?

  • »
    »
    3 weeks 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?

    • »
      »
      »
      3 weeks 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.

»
3 weeks 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.

  • »
    »
    3 weeks 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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone have a strong testcase for B?

»
3 weeks 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://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.

»
3 weeks 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

  • »
    »
    3 weeks 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$$$.

»
3 weeks 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?

  • »
    »
    3 weeks 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.

»
3 weeks 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.

»
3 weeks 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

»
3 weeks 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)

»
3 weeks 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

»
3 weeks 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?

»
2 weeks 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