### atcoder_official's blog

By atcoder_official, history, 6 weeks ago,

We will hold SuntoryProgrammingContest2024（AtCoder Beginner Contest 357）.

We are looking forward to your participation!

• +134

 » 6 weeks ago, # |   0 Excited and Hoping for the best ABC Round!
 » 6 weeks ago, # |   0 Auto comment: topic has been updated by atcoder_official (previous revision, new revision, compare).
 » 6 weeks ago, # | ← Rev. 2 →   +10 only 5 contributions away from the top-contributors.
 » 6 weeks ago, # |   -11 wu~hu~qi~fei~
 » 6 weeks ago, # |   0 glhf
 » 6 weeks ago, # |   +1 Problem E is similar to this!
 » 6 weeks ago, # |   0 E was exactly same as this. Probably that explains so many submissions on E.
 » 6 weeks ago, # |   0 what is hand_00.txt in D? only failed that test :/
•  » » 6 weeks ago, # ^ | ← Rev. 4 →   0 $$\sum_{i=0}^{len(s) — 1}(\frac{10^{n * len(n) + i} — 10^{i}}{10^i — 1}) * d[i]$$ where $len(n)$ is no of digits in $n$ and $d[i]$ is the $i$ th digit.need to be careful when calculate the numerator it might overflow: AC
•  » » 6 weeks ago, # ^ |   0 n*len(n) can overflow. Maybe you missed that ?
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 thanks for trying to help guys. I realized I was using the built-in pow to calculate pow(10, len(n)) instead of the pow in my mod template :(I changed pow(10, num_digits(n)) to pow((mlong)10, num_digits(n)) and got AC now
 » 6 weeks ago, # |   0 How to change my name?
 » 6 weeks ago, # |   +9 I spent over 40 mins implementing E only to find out here that it was available on Leetcode :/
•  » » 6 weeks ago, # ^ |   +3 I used Condensation Graph for E which is a bit overkill but it worked.
 » 6 weeks ago, # |   +10 Why there are so many D&C NTT problems in ABC, but almost no problems about suffix array or suffix automaton ??? I think they are educational too :)
 » 6 weeks ago, # |   0 how to solve F?
•  » » 6 weeks ago, # ^ |   0 I personally didn't solve it, but my idea was correct. We maintain 3 arrays: ${a_i}, {b_i}, {v_i}$. The first two should be self-explanatory and $v_i=a_ib_i$. To maintain these arrays, we can use many RURQ data structures (I used Sqrt Decomposition). Maintaining ${a_i}$ and ${b_i}$ should be simple as it is just a classic RURQ problem. To maintain ${v_i}$, we notice that when ${a_l, a_{l+1}, \dots, a_r}$ are each incremented by $x$, then ${v_l+v_{l+1}+\dots+v_r}$ is incremented by $x\times\left(b_l+b_{l+1}+\dots+b_r\right)$. This allows us to maintain array $v$ lazily. You can see the editorials for clearer explanations. Also, if anyone finds the problem in my implementation, I would appreciate it.
•  » » 6 weeks ago, # ^ |   0 Some segment tree magic. I misread statement and solved for $\sum_i \sum_j A_iB_j$
•  » » 6 weeks ago, # ^ |   0 Segment Tree
 » 6 weeks ago, # | ← Rev. 2 →   0 Why submission giving WA on test_03.txt :(
•  » » 6 weeks ago, # ^ |   0 you must print # for N = 0 not .
 » 6 weeks ago, # |   0 Joined 1 hour late (on accident), but still solved ABD.
 » 6 weeks ago, # |   0 Can somebody explain why my first submission was not accepted whereas the other one was accepted and the only difference both have is that in the not accepted one, I have define k = 1+(int)log10(n) whereas, in the accepted one I have define k = to_string(n).size()
•  » » 6 weeks ago, # ^ |   +1 This may help you.
 » 6 weeks ago, # | ← Rev. 3 →   0 Reduced problem D to Geometric Progression, and then utilised the sum of first N terms formula. We can split the original number multiply it later and make a GP serious out of multipliers of powers of 10. a = 10^(N*d — d), r = 1/(10^d). Final ans = N * a(1-r^n)/(1-r)Here d = no. of digits in the original given number. Have taken care of fermat's theorem too by applying (mod-1) for huge numbers in exponents. Why does it fail in 15 and passes 13 test cases. What is wrong in the solution ? https://atcoder.jp/contests/abc357/submissions/54378604
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 Let $M$ be the length of the number $N$. \begin{align} ans &=N\sum_{i=0}^{N-1}10^{iM} \\ &=N\frac{10^{NM}-1}{10^M-1} \end{align}To calculate this, we have to take $N\times(10^{NM}-1)\times(10^M-1)^{mod-2}$Code
•  » » » 6 weeks ago, # ^ |   0 I think there is some issue, with mod being used. I used your approach too with r = 10^d instead of 1/(10^d) which I previously used. Yet it still gives same results(15 fail and 13 pass). for some reasonhttps://atcoder.jp/contests/abc357/submissions/54385841Not sure what is the exact issue
•  » » 6 weeks ago, # ^ | ← Rev. 7 →   0 Wait that is literally the exact same thing that happened to meMy first D submission had 15WA and 13AC, so I might have had the same error as youLater in the contest, I found out that, in my method, I was creating an ll overflow by multiplying the original number n by another number. I fixed this by making the original number n=n%998244353. This might work for you, too.Here's my WA solution: https://atcoder.jp/contests/abc357/submissions/54371464And here's my AC solution:https://atcoder.jp/contests/abc357/submissions/54371922
•  » » » 6 weeks ago, # ^ |   0 Thanks! That totally skipped my mind at the time
 » 6 weeks ago, # |   0 Anyone please explain me the logic or Intution of Problem D.
•  » » 6 weeks ago, # ^ | ← Rev. 3 →   0 Prerequisite: Binary Exponentiation and Modular arithmetic
•  » » » 4 weeks ago, # ^ |   +3 Could You please tell me why this fails — https://atcoder.jp/contests/abc357/submissions/54764020
•  » » 6 weeks ago, # ^ |   0
 » 6 weeks ago, # |   0 Only solved first two, sad, suggest some topic.
 » 6 weeks ago, # |   0 Can anyone help me with problem F? I used lazy segment tree. code
•  » » 6 weeks ago, # ^ |   0 Anyone help please
 » 6 weeks ago, # |   0 @atcoder_official try to add more general editorial instead of any snippet, sometimes its get hard to understand .