### aniervs's blog

By aniervs, history, 6 weeks ago,

Hello. Recently, I started participating on AtCoder contests, and in many cases, I don't see announcements on codeforces, or any posts for discussing the problems. I remember that before, it was very frequent to see at least one AtCoder Contest-related post among the recent actions.

Is there a reason behind it?

Also, maybe we can use this post to discuss about the last ABC.

• +47

 » 6 weeks ago, # | ← Rev. 2 →   0 I felt today's contest was a bit more difficult than usual . Also thought problem D was harder than problem E.
 » 6 weeks ago, # |   0 I got a only WA on TC 7 in E . Can someone tell me what's wrong with my solution Or what TC 7 is https://atcoder.jp/contests/abc224/submissions/26775221
•  » » 6 weeks ago, # ^ |   0 Even I got WA in just test case 7 :///
•  » » » 6 weeks ago, # ^ |   +11 If u r going to next smallest greater element in row and column then do remember there can be many vertices to got to.I did that mistake , though till now haven't tried resubmitting.
•  » » 6 weeks ago, # ^ |   0 Same here
 » 6 weeks ago, # |   0 I think E has a similar idea as https://infoarena.ro/problema/zoro. Nice problem!
•  » » 6 weeks ago, # ^ |   0 For me, E was super standard. I've seen similar stuff at old USACO.
 » 6 weeks ago, # |   0 How did you (people) solve F?
•  » » 6 weeks ago, # ^ |   +14 I did the same as the editorial says. Look at the contribution to the answer of each $a_i$.If we consider indexing from $1$, then each $a_i$ (for $i\in[1,n]$) contributes to the answer in $a_i\cdot 2^{i-1}\cdot \left(10^{n-i} + \displaystyle\sum_{j=0}^{n-i-1}2^{n-i-j-1}\cdot 10^j\right) = \frac{a_i}{2}\cdot \left(10^{n-i} + \displaystyle\sum_{j=0}^{n-i-1}2^{n-j-1}\cdot 10^j\right)$. Thus, we can compute prefix sums ($P_j = P_{j-1} + 2^{n-j-1}\cdot 10^j$), and then, our answer is $\displaystyle\sum_{i=1}^n\frac{a_i}{2}\cdot(10^{n-i} + P_{n-i-1})$.
 » 6 weeks ago, # |   +7 For me, i think problem F is much easier than D and E. I stuck on D for 40 minutes , abandoned my code, and solved F in 15 minutes.
 » 6 weeks ago, # |   0 Can anyone tell what observations you made to solve problem D ( 8 Puzzle on Graph ) .I am not able to think clearly and make any useful observations :( .
•  » » 6 weeks ago, # ^ |   0 So, we have only 9 vertexes, which is very small, due to that there are 9! ways to distribute pieces (because there are 9 ways to choose a free vertex and 8! ways to distribute others => 9 * 8! = 9!). We can just run bfs from out initial state, and for each distribution we find free vertex and iterate over all edges from it, if we didn't get to the new state earlier we update distance and add new state to the queue. Finally we print distance if we can achieve final state or -1 if we can't.
•  » » 6 weeks ago, # ^ |   0 The goal state is a vector of {1,2,3,4,5,6,7,8,-1} where -1 represents an empty space. For sample 1, the initial state is a vector of {-1,3,1,4,5,6,7,8,2}. Use BFS to do state transition to see if the goal state can be reached or not.
 » 6 weeks ago, # | ← Rev. 2 →   +5 I tried F in another way than the editorial suggests. It did not work, but I still do not understand why. That was my strategy:Maintain the answer for a prefix of S, also the sum of all possible last terms for the formulars that can be created of S. Also maintain the count of possible prefixes.We start with cnt[0]=1 post[0]=s[0]-'0'; ans=post[0]; Then iterate S for all subsequent positions, and calc the next ans. Let d be some digit s[i]. That is:We can add the next digit as a new term to all previous formulars. Also we can add the next digit as the last digit of the last term of the previous prefix. Soans=ans+cnt[i-1]*d + post[i-1]*10+cnt[i-1]*dThen calculate the next cnt[], since there are the both above cases, cnt[i]=cnt[i-1]*2Finally, calculate the current sum of all last terms, that is (again) adding the next digit as last digit of existing term, or adding it as a new last term:post[i]=post[i-1]*10+cnt[i-1]*d + cnt[i-1]*dSo, after iterating the string ans should contain the correct answer, see submission. But it does not, why?edit: formulars
•  » » 6 weeks ago, # ^ |   0 The strategy works, the formular was wrong, see working submission.It is ans=ans*2+post[i-1]*9+cnt[i]*d