### chokudai's blog

By chokudai, history, 9 months ago,

We will hold AtCoder Beginner Contest 158.

We are looking forward to your participation!

• +43

 » 9 months ago, # |   0 ./Main.c: In function ‘main’: ./Main.c:7:5: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d", &a, &b); ^ anyone getting this error?
 » 9 months ago, # |   +5 Just got all 6 problems correct. No WA on any of them either!
 » 9 months ago, # |   -8 idk whats wrong with my B solu getting WA on test case 25-end
 » 9 months ago, # |   +3 good contest!
 » 9 months ago, # |   +6 Task-D submission using deque Here. I first did the same logic but instead wrote this line which gave me TLE. s = c + s This line appends c to the front of the string S and rewrites the whole string S which is costly. Hope this helps :)
•  » » 9 months ago, # ^ |   +5 https://atcoder.jp/contests/abc158/submissions/10636233Why my code is giving TLE? Its taking O(Q) time which is enough for 2x10^5. isn't'it?
•  » » » 9 months ago, # ^ |   +8 String concatenation isn't O(1).
•  » » » » 9 months ago, # ^ |   +5 OMG! i don't know that! Thanks
 » 9 months ago, # |   +29
•  » » 9 months ago, # ^ |   0 How you solved the problem E?
 » 9 months ago, # |   +2 What do I need to learn to solve task-E?
•  » » 9 months ago, # ^ | ← Rev. 3 →   +18 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.
•  » » » 9 months ago, # ^ |   +1 Thx. Prefix sums did not pop in my head, anyways I will practice more :)
•  » » 9 months ago, # ^ |   +3 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).
 » 9 months ago, # |   0 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?
•  » » 9 months ago, # ^ | ← Rev. 2 →   +9 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] = k will 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/10628481Note that the transition for two cases (small P and large P) is different. For small P, we use transition[i][j] = k then "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.
•  » » » 9 months ago, # ^ | ← Rev. 3 →   0 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/10633816This 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~
•  » » » » 9 months ago, # ^ | ← Rev. 2 →   0 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 the dp table. However in my logic we can't simple reassign this variable (we have to add it just like you used rem[now][mp[j][s[i]-'0']]+=rem[now^1][j];) In your code I see for (int j=0;j
•  » » » » » 9 months ago, # ^ |   0 Ok, I will try to reduce my constant and think more about this.Thank you~
 » 9 months ago, # |   0 Can anyone give a tutorial for task E
•  » » 9 months ago, # ^ |   +30 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.
•  » » » 9 months ago, # ^ |   0 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. 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
•  » » » » 9 months ago, # ^ |   0 https://codeforces.com/blog/entry/74551 this explanation is good regarding E.
•  » » » 9 months ago, # ^ | ← Rev. 2 →   +2 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 :)
•  » » » » 9 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » 9 months ago, # ^ |   0 I don't think subarray sum is the same forwards and backward. Take 15 and 51 for example: 15 % 7 = 1 51 % 7 = 2
•  » » » 9 months ago, # ^ |   0 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"
•  » » » » 9 months ago, # ^ |   +5 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=13A={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.
•  » » » » » 9 months ago, # ^ |   0 Thanks a lot!!! I understand!
•  » » » » » 9 months ago, # ^ |   0 I have implemented the same idea. I don't know why I'm getting WA for some cases can anyone find out what's wrong https://atcoder.jp/contests/abc158/submissions/10773471
•  » » » 9 months ago, # ^ |   0 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?
•  » » » » 9 months ago, # ^ |   0 RaunaqRoxx you should iterate from right to left in line 66
•  » » » » » 9 months ago, # ^ |   0 That didn't make a change.
•  » » » » » » 9 months ago, # ^ |   +1
•  » » » » » » » 9 months ago, # ^ |   0 Thanks a lot!
 » 9 months ago, # | ← Rev. 2 →   0 Problem E, Editorial:Your text to link here..., though I still couldn't solve it.
•  » » 9 months ago, # ^ |   +6 The size of P is very small in that problem. O(NP) won't work.
•  » » » 9 months ago, # ^ |   +5 Yes, but in the editorial, in the end they probably talks about how to optimise it.
•  » » » » 9 months ago, # ^ |   +5 That's just space complexity.
•  » » » » » 9 months ago, # ^ | ← Rev. 2 →   +5 Ok, thanks.
 » 9 months ago, # |   +5 can anyone explain O(1) solution for C?
•  » » 9 months ago, # ^ | ← Rev. 2 →   +9 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.
 » 9 months ago, # |   +14 Can anyone guide me how to solve or approach problems of type E? I really don't have any clue.
•  » » 9 months ago, # ^ | ← Rev. 2 →   +10 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.com/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.
•  » » » 9 months ago, # ^ |   +5 Oh Yes!!! Your transformation to the problem made it look so easy. Thank You.
 » 9 months ago, # |   +2 English Translation of Japanese editorialE: 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)
 » 9 months ago, # |   +11 My solution for E uses the same logic as provided in the editorial here : https://codeforces.com/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
 » 9 months ago, # |   +10 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)?
 » 9 months ago, # | ← Rev. 4 →   +13 I found there contain a BUG in some of the AC programs base on prefix sum/suffix sum at problem E. Try this input: 4 4 3543 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.
•  » » 9 months ago, # ^ |   +13 can u share the codes which used dp to solve this.
 » 9 months ago, # |   +5 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}}$?
 » 9 months ago, # |   +3 Supplementary editorial and sample codes for last 4 problems AtCoder_ABC_158
»
7 months ago, # |
Rev. 2   0

# include<bits/stdc++.h>

using namespace std; int main() {int n,a,b;cin>>n>>a>>b; if(a==0)cout<<0; else if(n<(a+b))cout<<min(n,a); else{ cout<<((n/(a+b))*a)+min(n%(a+b),a); } return 0; }

Can anyone tell why my code is giving WRONG ANSWER.( THIS IS THE 2ND QUESTION : COUNT BALLS)

# chokudai

•  » » 7 months ago, # ^ |   0 Use long long instead of int` because constraint is 10^18. One more thing, you don't need all those condition (i.e. a == 0 and n<(a+b)), (n/(a+b))*a+min(n%(a+b), a) will cover everything.