### chokudai's blog

By chokudai, history, 2 months ago,

We will hold Monoxer Programming Contest 2022（AtCoder Beginner Contest 249）.

We are looking forward to your participation!

• +46

 » 2 months ago, # |   +2 What a contest, I got 10 WAs for this contest: A (2), C (4), F (4)
 » 2 months ago, # |   -9 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 →   +7 Let the DP state be: $i$, the length of the actual string. $l$, the length of the run-length encoded string. $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, # |   +8 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, # ^ |   +1 I requested that clarification. It's lucky that as a Chinese I can comprehend at least some Japanese.
•  » » 2 months ago, # ^ |   0 At least "meters a second" should be "meters per second".
 » 2 months ago, # |   0 Someone explain D for English? I tried prime factors approach but didnt correct
•  » » 2 months ago, # ^ |   -14 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)$. Codefor (auto x : d) { ll res = 0; for (int j = 1; j * j <= x; j++) { if (x % j == 0) { if (j != x / j) res += cnt[j] * cnt[x / j] * 2; else res += cnt[j] * (cnt[j] - 1) + cnt[j]; // cerr << j << ": " << res << ", "; } } res *= cnt[x]; // cerr << res << endl; ans += res; } 
•  » » » 2 months ago, # ^ |   0 Thank you. I'll review it
•  » » » 2 months ago, # ^ |   +6 Better way (as in better complexity) is to just use the harmonic series which would give a $O(nlogn)$ solution.
•  » » » 2 months ago, # ^ |   0 ah nice, i did not think O(N * sqrt(N)) would pass. the harmonic series approach seems stronger
•  » » 2 months ago, # ^ |   +4 Actually in D, I am not able to see how ans for sample 3 equals 62?
•  » » » 2 months ago, # ^ |   +15 The indices can be the same. I had the same problem lol
•  » » » 2 months ago, # ^ |   +1 i, j, k need not be unique.
•  » » » 2 months ago, # ^ |   +7 I had to brute force O(n^3) to get 62 and understand the problem
•  » » 2 months ago, # ^ |   0 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, # |   +57 How to solve G and Ex?
 » 2 months ago, # |   0 Will the solutions be rejudged with test cases updated for A?
 » 2 months ago, # |   +1 Great problems, thanks to the writers. Hope that tutorials could be published as soon as possible.
 » 2 months ago, # |   +2 No Editorial :(
 » 2 months ago, # |   0 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.Accepted solution with sortingTLE solution without sortingI 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, # ^ |   0 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, # ^ |   0 Thanks, even without sorting, it works if I reduce the two if loop operations into just one.
 » 2 months ago, # | ← Rev. 3 →   0 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 →   +3 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
 » 7 weeks ago, # | ← Rev. 2 →   0 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].