chokudai's blog

By chokudai, history, 2 months ago, In English

We will hold Monoxer Programming Contest 2022(AtCoder Beginner Contest 249).

We are looking forward to your participation!

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

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

What a contest, I got 10 WAs for this contest: A (2), C (4), F (4)

»
2 months ago, # |
  Vote: I like it -9 Vote: I do not like it

How to solve E? I tried reducing it to something like

$$$ \begin{cases} a_1 \ge 2a_2+3a_3+\ldots+na_n \\ a_1 + 2a_2 + \ldots + na_n = l \end{cases} $$$

where $$$l = |s|$$$

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +7 Vote: I do not like it

    Let the DP state be:

    1. $$$i$$$, the length of the actual string.
    2. $$$l$$$, the length of the run-length encoded string.
    3. $$$c$$$, the last character in the string.

    Think of a transition where you add $$$c'$$$ $$$k$$$ times. In the run-length encoded string, that is equivalent to adding $$$f(k)+1$$$ characters, where $$$f(k)$$$ is the length of $$$k$$$ when written as a number. Since $$$n < 3000$$$, $$$f(k) \leq 4$$$. So, you can transition from $$$dp_{i,l,c}$$$ to $$$dp_{i+k,l+f(k)+1, c'}$$$, for 4 different ranges of $$$k$$$.

    Note that the DP transitions will actually be symmetric w.r.t $$$c$$$, i.e. $$$dp_{i,l,c} = dp_{i,l,c'}$$$ for all $$$i,l$$$. With this knowledge, we can just knock that dimension out, making the transition adding $$$25 \cdot dp_{i,l}$$$ to $$$dp_{i+k, l+f(k)+1}$$$. You don't need any complicated structures to add to the ranges of $$$k$$$, you can do this by adding in a prefix-sum-esque way and adding to $$$l$$$ and subtracting from $$$r+1$$$. Hence, you can do the entire DP in $$$O(n^2)$$$.

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

Though the problems themselves were pretty standard for an ABC, some of them could have been framed a bit better imho.
For example, it took me around 11 mins. to solve A because of the mistake in the problem statement. This could have been prevented if the variable names had been descriptive (speed, duration and rest instead of single alphabets).
And in problem D, clarifications that i, j and k need not be unique and that the division should be exact (not integer division) would have saved 20 mins. for me.

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

    I requested that clarification. It's lucky that as a Chinese I can comprehend at least some Japanese.

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

    At least "meters a second" should be "meters per second".

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

Someone explain D for English? I tried prime factors approach but didnt correct

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

    Just keep the no. of times a number has appeared in the array. Factor (not prime factor) the number and use some simple combinatorics. It should be done in $$$O(n\sqrt n)$$$.

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

      Thank you. I'll review it

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

      Better way (as in better complexity) is to just use the harmonic series which would give a $$$O(nlogn)$$$ solution.

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

      ah nice, i did not think O(N * sqrt(N)) would pass. the harmonic series approach seems stronger

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

    Actually in D, I am not able to see how ans for sample 3 equals 62?

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

    You can do this by enumerating i, and enumerating the multiples of i, and storing them in a vector.This should be done in $$$O(n\ln n)$$$

    Excuse my English is not very good.Because I am a Chinese.

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

How to solve G and Ex?

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

Will the solutions be rejudged with test cases updated for A?

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

Great problems, thanks to the writers. Hope that tutorials could be published as soon as possible.

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

No Editorial :(

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

In problem D, I tried two solutions after contest. Both are exactly same, one sorts the input array and the other doesn't. The former got AC (accepted), while the latter got TLE on 5/20 test cases. I'm curious what might've caused this, all the more since according to me, my solution doesn't take advantage of the sorted order of the array in any way.

Problem Link

Accepted solution with sorting

TLE solution without sorting

I know that rather than map, I could've used the vector or array and gotten AC, but in a similar scenario in some other problem, I might think sorting isn't required and fail to solve the problem.

Any help would be much appreciated.

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

    Just guessing: I think the access-patterns on mp.count(v[i] / j) are more cache-friendly in the sorted case, at least for low values of i. In the unsorted case you have less loop iterations where both v[i] and v[i+1] are low.

»
2 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Hi, Why there's no editorial available yet? chokudai, Kodaman, m_99, PCTprobability, nok0, And also can someone explain the solution of F?

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    The editorial is out now.

    My solution to problem F: Let we add an operation $$$t_0=1,y_0=0$$$. Then, the final value of $$$x$$$ is always consisted of $$$y_i(t_i=1)$$$ and the sum of some(not all) $$$y_j(t_j=2,i<j\le n)$$$. (We will ignore the operations with $$$t_j=1$$$)

    In the operations with $$$t_j=2$$$, we can always ignore the smallest negative $$$y_j$$$ to reach the maximum value of $$$x$$$. Thus, the problem becomes maintaining $$$val=\text{the sum of the smallest negative }k'\text{-th } y_j$$$ ($$$k'=k- \text{the number of operations with } t_j=1(i<j\le n)$$$), and this can be done by balance tree, priority queue, segment tree, etc.

    My implementation: deal with the operations from $$$n$$$ to $$$0$$$. If $$$t_i=2$$$ and $$$y_i<0$$$, insert it to the treap, then do $$$s\leftarrow s+y_i$$$. If $$$t_i=1$$$, do $$$ans\leftarrow\max(ans,y_i+s-val),k'\leftarrow k'-1$$$.($$$val$$$ is mentioned above)

    my code using treap

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In Problem E, I can't understand how the optimization is working. Can anyone help me.

The optimization of DP We can find that the g(k) is in [2,3,4,5], so we can use fenwick tree to optimize it. There are n fenwick trees, the i-th is called C[i].

For each i,j:

  • Add 25×f[i][j] to the (i+1)-th element of C[j+2], and subtract it to the (i+10)-th element of C[j+2].
  • Add 25×f[i][j] to the (i+10)-th element of C[j+3], and subtract it to the (i+100)-th element of C[j+3].
  • Add 25×f[i][j] to the (i+100)-th element of C[j+4], and subtract it to the (i+1000)-th element of C[j+4].
  • Add 25×f[i][j] to the (i+1000)-th element of C[j+5].