We will hold AtCoder Beginner Contest 158.
- Contest URL: https://atcoder.jp/contests/abc158
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20200307T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 6
- Writer: satashun, evima, tempura0224
- Rated range: ~ 1999
- The point values will be 100-200-300-400-500-600.
We are looking forward to your participation!
Just got all 6 problems correct. No WA on any of them either!
good contest!
Task-D submission using deque Here. I first did the same logic but instead wrote this line which gave me TLE.
This line appends c to the front of the string S and rewrites the whole string S which is costly. Hope this helps :)
https://atcoder.jp/contests/abc158/submissions/10636233
Why my code is giving TLE? Its taking O(Q) time which is enough for 2x10^5. isn't'it?
String concatenation isn't O(1).
OMG! i don't know that! Thanks
Screencast
How you solved the problem E?
What do I need to learn to solve task-E?
Thinking.
Ok honestly, prefix sums and modular arithmetic if you really don't know them, but actually it is more about experience and figuring out the correct direction to think in.
Thx. Prefix sums did not pop in my head, anyways I will practice more :)
How I understood it: in case p is neither 2 nor 5, it can be solved with the same linear-time solution (after using a vector of size p as hashmap) as the 2sum problem: (https://leetcode.com/problems/two-sum/) (one needs to make an observation about divisibility, basically that if $$$t\cdot 10^i = 0 \mod p$$$, then $$$p\vert t$$$ ).
In case p = 2 or 5, then this observation is no longer true, but the problem can be solved (more) easily on an ad hoc basis (e.g. if p=5, count all substrings which end at a 0 or 5).
for E I can solve it in O(NP) time using dp but it will give TLE for N=2*10^5 & P<=10^4.
So any suggestion please?
With some optimizations, I managed to fit O(NP) solution in TL. I will share some methods I used. I assume that you understand some basic modulo arithmetic.
1) Precompute everything. We precompute
transition, which is 10*10000 size.transition[i][j] = kwill represent the information of "If we had a substring with $$$k \mod p$$$ until this letter, and we have current digit $$$i$$$, it will produce substring with $$$j \mod p$$$.2) Of course, if $$$P = 2, 5$$$, it may be possible that we do not have such $$$j$$$. I used two different logic for $$$p < 10$$$ and $$$p >= 10$$$, but what I actually wanted is to guarantee $$$p \neq 2, 5$$$.
3) Use dp with toggling for memory optimization (we cant' fit 2e9 integers to memory), using the transition we computed at 1).
Here is my code. https://atcoder.jp/contests/abc158/submissions/10628481
Note that the
transitionfor two cases (small P and large P) is different. For small P, we usetransition[i][j] = kthen "If we had a substring with $$$j \mod p$$$, current digit $$$i$$$, it produce $$$k \mod p$$$. This is dirty, but it is because I knew that 1) definition better after getting TLE several times.After TLE, I also noticed that we have to use 10*10000 array for transition instead of 10000*10, which I feel very unintuitive for logic. But this was to enhance performance with better caching. Of course I used O3 and Ofast pragmas, and all those tedious things unrelated to algorithm.
I have read your code. But I still can't make sense of the difference between the two kinds of definition.
My code is the same as yours. (Just the part in P<10)
https://atcoder.jp/contests/abc158/submissions/10633816
This will get TLE.
I just can't understand why the second part in your code(P>10) is faster than the original one (P<10)? Do these two have any difference in Complex?
Thank you~
I do not fully understand the performance difference between two definitions, but I got 3 TLEs from definitions above and got AC after changing definition.
As I understand, in the first case (which I used for $$$P < 10$$$), we cannot guarantee that every single
dp[r][k]is touched by one iteration for $$$n$$$, hence we have to reset thedptable. However in my logic we can't simple reassign this variable (we have to add it just like you usedrem[now][mp[j][s[i]-'0']]+=rem[now^1][j];) In your code I seefor (int j=0;j<p;j++) rem[now][j]=0;which is executed $$$O(np)$$$ times.If we use second definition, it is guaranteed that every entry is updated in single iteration. Hence, we do not have to reset the value before we use, and we can simply assign as
dp[r][j] = dp[1-r][k];. I think the zeroing out time is quite critical, since I usedmemsetwhich should be much faster than manually zeroing out and it didn't passed.I don't think using
registerkeyword is meaningful (modern compilers tend to ignore that) in my code. But using pragmas are. Try with bunch of#pragmastuff I wrote in my code. You might find https://codeforces.net/blog/entry/66279 helpful for understanding these compiler pragma and how it enhances performance.And to answer last question, no. It has absolutely no difference in complexity. My code is still $$$O(np)$$$, but as you might know, there are hidden constant factors in big-O notation. My code is optimizing that constant factor.
Ok, I will try to reduce my constant and think more about this.
Thank you~
Can anyone give a tutorial for task E
We observe that we can transform the string into an array of integers, where A[0] = S[0], A[1] = 10 * S[1], A[2] = 100 * S[2] and so on. We build the array A modulo P.
Now, the substring is transformed into a subarray. We observe that if P is coprime to 10, then if the subarray sum is divisible by P the substring must also be divisible by P in base 10. Thus, if P is coprime to 10, this becomes the classic problem of finding the number of subarrays with sum divisible by P, which can be solved in O(N logN) with a map.
If P is not coprime to 10, P is either 2 or 5. Thus, we just count all of the substrings ending with a digit divisible by P.
Can you elaborate more? Why do we not need to divide the subarray sum by some power of ten to get the substring here?
Thanks
https://codeforces.net/blog/entry/74551 this explanation is good regarding E.
It's probably A[N-1] = S[N-1], A[N-2] = 10 * S[N-2], A[N-3] = 100 * S[N-3] and so on.
Or reverse S in the beginning :)
Yeah, I implicitly did some reversal somewhere in my code (oops).
Actually, it doesn't really matter for the case where P is coprime to 10, because subarray sum is the same forwards and backwards.
Update: Oops, it seems I have made a small misunderstanding about what "reversal" means. My apologies, it does matter.
I don't think subarray sum is the same forwards and backward. Take 15 and 51 for example: 15 % 7 = 1 51 % 7 = 2
Can you please explain,why "if P is coprime to 10, then if the subarray sum is divisibile by P the substring must also be divisible by P"
We observe that the subarray sum is equal to the substring in base 10, multiplied by some power of 10. If P is coprime to 10, then multiplying by a power of 10 will not change divisibility by P.
Example:
S="135"
P=13
A={100, 30, 5} (actually, we store A mod P, which is {9, 4, 5})
We observe that the subarray sum of the first two elements is 130, which is 13 * 10. The 10 does not affect divisibility by 13, thus we see this equivalence between subarray sum and substring.
Thanks a lot!!! I understand!
https://atcoder.jp/contests/abc158/submissions/10648178 I have implemented the same idea suggested by you, but I am still getting a good amount of WAs, can you point out the mistake my code is having?
RaunaqRoxx you should iterate from right to left in line 66
That didn't make a change.
https://atcoder.jp/contests/abc158/submissions/10642326
Thanks a lot!
Problem E, Editorial:Your text to link here..., though I still couldn't solve it.
The size of P is very small in that problem. O(NP) won't work.
Yes, but in the editorial, in the end they probably talks about how to optimise it.
That's just space complexity.
Ok, thanks.
can anyone explain O(1) solution for C?
Let the price before taxes (that's what we're looking for) be p. Then,
floor(0.1p) = B.
We know that floor(n) = x means that x <= n < x + 1. So, "floor(0.1p) = B" means that "B <= 0.1p < B + 1". Multiplying by 10: "10*B <= p < 10*B + 10". So, if there's an answer, it's between 10*B and 10*B + 9.
So, all you have to do is scan each number x between 10*B and 10*B + 9 (those are only 10 numbers, so it's O(1)) and check if "A <= floor(0.08x) < A + 1" (because floor(0.08p) must be A and "floor(n) = A" means that "A <= n < A + 1"). The first number that satisfies that condition is the answer. If no number between 10*B and 10*B + 9 satisfies that condition then there's no answer and you return -1.
Can anyone guide me how to solve or approach problems of type E? I really don't have any clue.
In my opinion E is a fairly nice problem. It requires one good observation followed by knowledge of some (fairly well-known) classic problem.
The observation is that you can transform substring to subarray sum if P is not 2 or 5 (if P is 2 or 5, the problem becomes much easier anyways, so it doesn't matter) by transforming the string to an array using a method I described here: https://codeforces.net/blog/entry/74534?#comment-586664. I'm not sure how to explain how to get to this observation, but I believe that it comes from experience with similar problems.
After that, the problem becomes "count subarrays with sum divisible by P". This is a fairly well-known classic problem that can be solved with prefix sum and map (or some other method of counting occurrences of a value in a range quickly).
In conclusion, if you're stuck on a problem like E, try to make some nice observations to turn the problem into something more classic that you've seen before.
Oh Yes!!! Your transformation to the problem made it look so easy. Thank You.
English Translation of Japanese editorial
E: Divisible Substring First, fix the left end and extend the right side while calculating the remainder after actually dividing by P, so you can find the answer with O (N2). For example, if the left and right sides of a character string are fixed, let's consider formulating whether the remainder after dividing by P can be calculated. Put Ui: = S [i: N] (the i-th character after S) as the evaluated integer. For convenience, UN + 1 = 0. (At this point, we have not yet considered it with modP.) At this time, the integer that evaluates the i-th to j-th characters of S can be expressed as Ui−Uj + 110j + 1−i. (1≤i≤j≤N) where it is important that P and 10 are relatively prime. In the case of P = 2,5, it can be solved by O (N) because it is determined only by whether or not the right end is divisible by P. P̸ = 2,5. At this time, Ui−Uj + 110j + 1−i is divisible by P is equivalent to Ui−Uj + 1 being divisible by P. Therefore, this problem was solved by O (N + P) by calculating UimodP from the right side and managing the number of j that is currently xmodP with an array or map. (This time P is small, but if P is large, use map)
My solution for E uses the same logic as provided in the editorial here : https://codeforces.net/blog/entry/74551 But I am getting WA on TC 33 (and only on 33). Could someone point out why this is the case? Here is the link to my solution: https://atcoder.jp/contests/abc158/submissions/10649436
General question as I wasn't sure where/who to ask on AtCoder. If we register for a contest, but do not participate, does it impact rating, or does rating only get impacted when something is submitted (similar to Codeforces)?
I found there contain a BUG in some of the AC programs base on prefix sum/suffix sum at problem E. Try this input:
The answer should be 1. I used several solutions based on prefix sum for testing, but they all output 6. The reason why this problem occur is that when p=4, 10%p=2. If there are 2 zeros at the end, the answer will be divisible whatever the number really are. for example, 3543-43=3500, even though 35 is not divisible by 4, 3500 is divisible by 4.
However, I notice there are some guys solve this problem by DP. They would not occur the bug like this.
update： I made a STUPID mistake that I didn't notice p should be a prime. Sorry about that :( So the solution based on prefix sum is right, they just can not handle the situation when p is not prime, which is not considered in this problem.
can u share the codes which used dp to solve this.
In the editorial of E, shouldn't it be $$$\frac{U_i-U_{j+1}}{10^{N-j}}$$$ instead of $$$\frac{U_i-U_{j+1}}{10^{j+1-i}}$$$?
Supplementary editorial and sample codes for last 4 problems AtCoder_ABC_158