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

Автор atcoder_official, история, 5 недель назад, По-английски

We will hold AtCoder Regular Contest 185.

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

We are looking forward to your participation!

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

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

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

$$$\Huge{\text{Good Luck & Have Fun}}$$$
»
5 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

600+600+600+800+800

it's so unusual

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

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

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

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

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

This is definitely not an intended solution for E.

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

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

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

    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

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

    I got a TLE on this :(

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

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

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

A is way too easy for 600.

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

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

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

WhyTF B==C

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

E is too easy for 800pts.

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

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.

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

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.

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

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

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

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