We will hold SuntoryProgrammingContest2024（AtCoder Beginner Contest 357）.
- Contest URL: https://atcoder.jp/contests/abc357
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20240608T2100&p1=248
- Duration: 100 minutes
- Writer: Nyaan, math957963, physics0523, MtSaka
- Tester: toam, Aus21
- Rated range: ~ 1999
- The point values: 100-200-250-350-450-550-650
We are looking forward to your participation!
Excited and Hoping for the best ABC Round!
Auto comment: topic has been updated by atcoder_official (previous revision, new revision, compare).
only 5 contributions away from the top-contributors.
wu~hu~qi~fei~
glhf
Problem E is similar to this!
E was exactly same as this. Probably that explains so many submissions on E.
what is hand_00.txt in D? only failed that test :/
\begin{equation} \sum_{i=0}^{len(s) — 1}(\frac{10^{n * len(n) + i} — 10^{i}}{10^i — 1}) * d[i] \end{equation} 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
n*len(n) can overflow. Maybe you missed that ?
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))topow((mlong)10, num_digits(n))and got AC nowWA AC
How to change my name?
I spent over 40 mins implementing E only to find out here that it was available on Leetcode :/
I used Condensation Graph for E which is a bit overkill but it worked.
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 :)
how to solve F?
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.
Some segment tree magic. I misread statement and solved for $$$\sum_i \sum_j A_iB_j $$$
Segment Tree
Why submission giving WA on test_03.txt :(
you must print # for N = 0 not .
Joined 1 hour late (on accident), but still solved ABD.
WA — https://atcoder.jp/contests/abc357/submissions/54368958 AC — https://atcoder.jp/contests/abc357/submissions/54381026
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()
This may help you.
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
Let $$$M$$$ be the length of the number $$$N$$$.
To calculate this, we have to take
Code
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 reason
https://atcoder.jp/contests/abc357/submissions/54385841
Not sure what is the exact issue
Wait that is literally the exact same thing that happened to me
My first D submission had 15WA and 13AC, so I might have had the same error as you
Later 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/54371464
And here's my AC solution:
https://atcoder.jp/contests/abc357/submissions/54371922
Thanks! That totally skipped my mind at the time
Anyone please explain me the logic or Intution of Problem D.
Prerequisite: Binary Exponentiation and Modular arithmetic
Could You please tell me why this fails — https://atcoder.jp/contests/abc357/submissions/54764020
https://mirror.codeforces.com/blog/entry/130226?#comment-1157408
Only solved first two, sad, suggest some topic.
Can anyone help me with problem F? I used lazy segment tree. code
Anyone help please
@atcoder_official try to add more general editorial instead of any snippet, sometimes its get hard to understand .