atcoder_official's blog

AtCoder Regular Contest 185 Announcement
By atcoder_official, history, 2 months ago, In English

We will hold AtCoder Regular Contest 185.

The point values will be 600-600-600-800-800.

We are looking forward to your participation!

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

»
2 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Three 600 difficulty problems? This round should be earlier than most previous ARC rounds.

$$$\Huge{\text{Good Luck & Have Fun}}$$$
→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

600+600+600+800+800

it's so unusual

→ Reply
»
2 months ago, # |
  Vote: I like it -8 Vote: I do not like it

It seems like a speedrun. Anyway, gl&hf!

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

    Speedrun Yes. BCDE are all easier than ARC184_B.

    → Reply
»
2 months ago, # |
← Rev. 2   Vote: I like it -27 Vote: I do not like it

what's wrong with ARC, the last one was just like AGC and this one is ABC+ speedrun.

→ Reply
»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

This is definitely not an intended solution for E.

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

    Well, I actually managed to squeeze mine to 1.1s... (reduce $$$128^2$$$ to around $$$1200$$$ iterations per index)

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

    Instead of doing it everytime, I cached in memory a simulation of doing this operation for all numbers from 1 to 100'000, and then reducing to $$$128 * 500000 + \sum_{n=1}^{100000} divs(n)^2$$$ from 1694ms to 338ms Link

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

    I got a TLE on this :(

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

      But I optimized my algorithm (not my constant) and got AC. Your code is easy to optimize.

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

A is way too easy for 600.

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

How did the question maker come up with this CDE question ?

→ Reply
»
2 months ago, # |
  Vote: I like it -10 Vote: I do not like it

WhyTF B==C

→ Reply
»
2 months ago, # |
  Vote: I like it +37 Vote: I do not like it

E is too easy for 800pts.

→ Reply
»
2 months ago, # |
  Vote: I like it +82 Vote: I do not like it

The problems seem to be pretty different from a "normal" ARC. I feel like C could just as well have been a late problem in an ABC, basically only needing to know a certain standard technique, and then doing some casework. D and E also had some kind of knowledge check inbuilt, but you didn't need to do much observations. I liked other ARC's more.

→ Reply
»
2 months ago, # |
← Rev. 6   Vote: I like it +26 Vote: I do not like it

There's a solution of C slightly simpler than official: Let multisets S={Ai: Ai<=X/3}, T={Ai: Ai>X/3}, then Ai, Aj and Ak cannot all come from T, and if they all come from S then Ai=Aj=Ak=X/3 so we can check if number of occurences of x/3 is at least 3. So in other cases, there could be 1 number from S and 2 from T, or vice versa. For now on we only need to keep 2 occurences for each different numbers. For the first case (second case is similar), Let f(x)=((sum(j)(x^j))^2-sum(j)(x^(2*j)))/2, where j iterates among all elements of T, then f(x)[x^p] will be the number of ways to choose different Ai,Aj from T such that Ai+Aj=p, we can use FFT to calculate them, and find some p<=X/3 such that f(x)[x^(X-p)]>0. Because we only keep at most 2 occurences, each coefficient of f(x) is at most 1000000*2^2=4000000, so we can do FFT by modulo 998244353 safely.

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

    Actually we can limit to one occurrence for each value. If a value is indeed used twice, i.e. $$$2a+b = x$$$, we can just enumerate all possible $$$a$$$ in $$$O(n)$$$

    → Reply
»
2 months ago, # |
  Vote: I like it -14 Vote: I do not like it

I think the E-questions in this game are easier than the previous ones in ARC. And how to solve C?

→ Reply