### chokudai's blog

By chokudai, history, 3 years ago, We will hold AtCoder Beginner Contest 179.

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation! Comments (101)
| Write comment?
 » "We are looking forward to your participation!"We are looking for quick editorials.P.S. I love ABC's.
•  » » same to you...looking for quick editorials
 » 3 years ago, # | ← Rev. 2 →   What are the ALC contests of Atcoder? Edit: It's is described in this blog
 » •  » » 3 years ago, # ^ | ← Rev. 3 →   No, it is me after solving ABCDEThough it seems F was not particularly difficult this time
 » I tried a DP solution for D. Somehow getting TLE in 6 TCs. I tried to optimize it as much as I could. Am I missing something?Link to Submission
•  » » 3 years ago, # ^ | ← Rev. 2 →   post qns only after contest is over.
•  » » » It is over.
•  » » » » U posted few minutes before it was over.
•  » » » » » I could have posted the comment barely moments before the contest got over. But anyways, you can't open the submission link before the contest gets over anyways. Don't be a cop. If you can help then you are welcome.
•  » » » » » » direct DP is O (n^2). U need to use either prefix array or seg tree to solve in O(n logn)
•  » » » » » » » I tried d with segment tree but in runtime error in some test cases. Can you help me? https://atcoder.jp/contests/abc179/submissions/16889464
•  » » i used fenwick tree to optimize it, note that k <= 10, your solution fails because ranges can be very big, so your solution is n^2
•  » » » But the sum of ranges won't be more than O(n) I suppose. Because the segments are nonintersecting.
•  » » » » Yes, the sum of ranges is $O(n)$, but you also have $O(n)$ states and for each, you iterate through all of them. In total it is $O(n^2)$.
•  » » you can try it in O(n*k). Refer to below link for reference.https://www.geeksforgeeks.org/constant-time-range-add-operation-array/My Submission
•  » » your code runs in O(K*N) where K is the number of possible jumps, theoretically in worst case it would reach O(n^2) time complexity which could defenitely get TLE. In this problem i used dynamic programming with fenwick tree, you can look at my code here
•  » » For d, you have to combine the dp you are talking about, with the range covering problem (it is easier than segment tree I leave you this video in which that guy explains that problem https://youtu.be/Zze-O2oxoEo?t=219 ) and then you just have to be careful about modulo operations (you might be doing them with negatives)I hope this was useful
•  » » » Thanks for this. I checked out the video. Isn't what he is talking about, called the Fenwick tree?
•  » » » » No, Fenwick tree is a little more complex than that, it is about having sum until last significant bit and when doing a query going up from last significant bit to most significant bit (with a complexity of logn) and when updating is almost the same, but instead of getting an answer, updating; that is why it is also called Binary Indexed Tree
•  » » My code is similar with yours and I wonder how to optimize it too. [submission:#17148205]
 » First time in ABC I was able to solve all problems. Here are short explenations. FUse two segment tree with lazy propagation to maintain the first blocking position per row/col. Submission EThe sequence repeats after at most M elements. Find the size of the loop and the sum of the loop, then "jump" to n. Submission DUse segment tree with lazy propagation to maintain the dp-array. This makes it possible to quickly update the intervals. Submission CBrute force count the number of pairs $i*j •  » » For d instead of segment tree + dp you can use prefix array + dp. •  » » » please share your code •  » » » » •  » » » » » plz give a brief explanation also. thnx •  » » » » » » 3 years ago, # ^ | ← Rev. 5 → Basicdp[i] represntes number of ways to reach ith index.suppose you can make jump of value a1,a2,a3.then dp[i] = dp[i - a1] + dp[i - a2] + dp[i - a3] Solutionconsider a segment (L1,R1)so dp[i] = dp[i - L1] + dp[i - (L1 + 1)] + ... + dp[i - R1]So for this, we can use the prefix array.dp[i] = prefix[i - L1] - prefix[i - R1 - 1]We have to repeat this process for all segments.Submission •  » » You don't really need a segment tree for D I just used prefix sums •  » » D and E should have been swapped ,I didn't even attempt E after continuous TLE's in D . •  » » » 3 years ago, # ^ | ← Rev. 2 → D is more difficult in terms of the idea I guessE is heavier in terms of implementation •  » » » even i think so •  » » 3 years ago, # ^ | ← Rev. 2 → You don't need segment tree for F either. Code#include using namespace std; int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, q; cin >> n >> q; set> se; se.insert({n, n}); se.insert({n, n}); long long ans = 1LL * (n - 2) * (n - 2); while (q--) { int ty, i; cin >> ty >> i; ty--; auto it = se[ty].lower_bound({i, -1}); int k = (*it).second; ans -= k - 2; se[ty ^ 1].insert({(k - 1), i}); } cout << ans << '\n'; return 0; }  •  » » » can you explain your approach for F •  » » » » I'm more than a month late, you may have got the answer till now, but here is what I think the approach is:Here two sets are used to maintain position of lines of white stones. There are two kinds of lines length wise :1. Partial lines(going from one end and ending halfway)2. Complete lines (going from one end to other end)There are two kinds of lines possible orientation wise :a) Horizontal Line - Can be stored as$y$co-ordinate it starts on and$x$co-ordinate it ends on.b) Vertical Line - Can be stored as$x$co-ordinate it starts on and$y$co-ordinate it ends on.Now what exactly those two sets do, set stores position for horizontal lines, and set stores position of vertical lines.Formally a pair stored in respective sets looks like: s= (Ending abscissa, originating ordinate) s=(Ending ordinate, originating abscissa) Note that at the start we only have two complete lines, one horizontal and one vertical that's why a pair$(n,n)$is stored in both the sets. Query 1 We search for nearest horizontal line we can find that ends after$x$, and thus add remove black stones in that interval from the answer accordingly and now one vertical line is created in the process that starts at$x$and ends just before the horizontal line we found. Query 2 Search for nearest vertical line, remove black stones in that range from the answer and add a horizontal line in the corresponding set. •  » » F: you can use std::map for the same query (lower_bound to find closest) SubmissionD: you can use only partial sums of your dp and fill dp[i] with sum of previous values Submission •  » » I also thought of using segtree with lazy prop on F, but I had no segment tree template with lazy propagation :P and I had only 35mins left. So I quit. Missed my chance of solving all problems in ABC for the first time. I'm taking your template now XD. •  » » » I also got idea of two lazy segment tree immediately but I haven't implemented even a basic lazy segment tree before so I gave up. Now I am seeing there are other solutions too •  » » » I had to fix a bug in that template in function rangeInc(). Not sure if everything works fine. •  » » » » Oh,thanks for informing. I'll test it properly after customizing it for myself. :) •  » » » » » In AtCoders ACL library there is a segment tree, too. I would like to switch to that one, but need time to get used to it.ACL lib •  » » » Question: I thought that we should need to be able to get the historically minimum of some certain index? Won't that be more than just a plain old segtree? •  » » I got tle in this, could you plz tell me why? int ans = 0; for(int i = 1 ; i •  » » » 3 years ago, # ^ | ← Rev. 5 → You have asymptotic of$O(n \sqrt{n})$which is too big. You can enumerate only the smallest number of$A, B$which would be$\sqrt{n}$and calculate how many multipliers bigger than your number you can have such that$A \times B$is smaller than$N$. •  » » » n is 1e6, so the inner loop runs up to 1e3 times... that are aprox 5e8 iterations. •  » » Me too for the first time solved set in any contest lol •  » » Can you please further explain how did segment tree help with this problem? I know segment tree but I cannot utilize it to solve this problem. •  » » » I assume problem D.If we would do standard knapsack we would need to loop over all the values in the K ranges, which is O(n).With the segment tree we are able to do these updates in O(log n).Note that the solution with the partial sums do these updates in virtually O(1). see here •  » » » » Thanks a lot:) you always provide useful insights •  » » correct me if I am wrong, the time complexity of your D solution is N*k*log(n) and not N*log(n) which the editorial says is the optimum •  » » » Yes, you are right. Because of this my submission needs 800+ms instead of possible 10ms. •  » » In problem E , How can I know that the series will repeat itself ? •  » » » 4 months ago, # ^ | ← Rev. 2 → It is the pidgeonhole principle. Since all values of the series are in range 0..M-1, there is a repitition after at most M values.  » How to solve problem D? •  » » Spoileryou can just use range query datastructure like fenwick tree and update every index •  » » 3 years ago, # ^ | ← Rev. 2 → I solved it without segment treeI used difference array. Time complexity of$O(N*K)$basically let dp[i] be no of ways to each i.Then you increment,$i$+$L_j$to$i$+$R_j$with dp[i], increment using difference array method, and keep summing as you move toward right.The answer would be dp[n]Submission •  » » I solved it maintaining a prefix sum array and using dp. dp[i] = sum of dp[j] for all j, i is reachable. As the range was contiguous it was easy to get the sum of dp[j] using prefix sum. My Sumbission •  » » » could u plz explain more •  » » » » 3 years ago, # ^ | ← Rev. 2 → Here dp[i] is the number of ways to reach i. dp[i] was calculated by the sum of dp[j] for all j from where i is reachable. Assume i = 4 and i is reachable from 2 and 3. If the number of ways to reach 2 is 1 aka dp = 1 and the number of ways to reach 3 is 2, dp = 2 then dp = dp + dp which is dp = 3 (rule or sum)And for any i corresponding js were calculated from the ranges and their sum was calculated from the the prefix sum array. For any position iand a range L, R i is reachable from all valid i-R, i-L. Finally the answer is dp[n]. Complexity O(N*K)  » I got runtime error in sometest cases in prob D with segtree can somebody help me? https://atcoder.jp/contests/abc179/submissions/16889464  » 3 years ago, # | ← Rev. 2 → void test_case() { int n , x; cin >> n >> x; for(int i = 0 ; i < 2*x ; i++){ int p; cin >> p; c.insert(p); } dp = 1; for(int i = 2 ; i <= n ; i++){ for(auto j : c){ if(j <= i){ dp[i] = (dp[i]%M+dp[i-j]%M)%M; } } } cout< •  » » 3 years ago, # ^ | ← Rev. 3 → they want you to union the segments [Li,Ri] i mean {Li,1+Li,2+Li,3+Li,....,Ri} not only values {Li,Ri}  » Its the first time I AK abc! LOL  » 3 years ago, # | ← Rev. 2 → I tried to solve D by repeating knapsack dp approach with time complexity O(N*m).But TLE destroyed my today's contest.Can anyone help me with that? •  » » D can be done in O(n*k).Use range update operation on array, it will take O(n) for each range.My submission •  » » » Can you elaborate this part?if(i+range[j].F<=n) temp[i+range[j].F]=(temp[i+range[j].F]+dp[i])%M; if(i+range[j].S+1<=n) temp[i+range[j].S+1]=(temp[i+range[j].S+1]-dp[i]+M)%M; •  » » » » Suppose you have array 1 2 3 4 5 You want to add 2 from position 2 to 4 [1 based-indexing) You can take a temp array and make temp=2 and temp=-2Now you can iterate over array and take sum+=temp[i]And add sum to a[i] . You can get the required array after update in O(n) this way.  » Eagerly waiting for geothermal's editorial.  » Hello in D no I used the similar pattern of dp like CSES-Coin Combinations I. but get TLE from that.Isn't it the similar pattern problem.My solution is here •  » » Thats' so because the time complexity of your solution is O(n*n). •  » » » I thought it's like Coin Combinations I problem.My bad.How can I solve it using dp ? •  » » » » Well, usually i solve 4-5 problems in ABC contest but today i was able to solve only the first three!  » Could anyone please explain the 1 testcase this is failing on? I have tried to find a cycle and then adding to the sum the sum of that cycle and then adding the rest seperately.Submission •  » » nvm, fixed it, was not solving correctly for when the cycle would end without it ever repeating. fixed code  » how to solve D? someone with good explanation? •  » » 3 years ago, # ^ | ← Rev. 2 → You can use this dp: dp[i] means how many ways do you have to go to the i-th cell. Let's get an array of long long dp[2n]. First we fill it with zeros. Denote the sums[2n] as prefix sums array of dp. dp[n] = 1, sums[n] = 1 for each cell from n+1 to 2*n and each segment (l[j], r[j]) we calculate: dp[i] = (mod + dp[i] + sums[i - l[j]] - sums[i - r[j] - 1]) % mod You can understand that part as: to get how many ways I have to go to the i-th cell, I should sum the ways from all dp[the previous one, from which you can get into this].The value sums[i - l[j]] - sums[i - r[j] - 1] gets us sum: dp[i - r] + dp[i - r + 1] + ... + dp[i - l] •  » » » Why are you taking dp[2*n] and not dp[n] or dp[n+1]? •  » » » » Just because I don't want to care about bounds  » 3 years ago, # | ← Rev. 2 → And the Chinese version. •  » » 4 months ago, # ^ | ← Rev. 2 → In problem E , How can I know the this series will repeat itself  » how do you solve c? I got TLE my solution is only O(n^2) •  » »$O(N^2)$is too large for$N=10^6$. •  » » » How can i know that it's large or not? •  » » » » You just put N into the time complexity expression and evaluate it. Generally speaking,$10^7$is totally acceptable, while$10^8$can be a bit dangerous (on some OJs it cannot pass), and$10^9$is almost impossible to pass the time limits.However, sometimes we also need to consider the constant, which is omitted in the time complexity expression. •  » » can somebody please explain the logic for c. n = int(input()) cnt = 0 for i in range(1, n): cnt += (n - 1) // i print(cnt)  •  » » » 3 years ago, # ^ | ← Rev. 2 → Since N is fixed, we don't need to enumerate all possible triplet of (A, B, C), we only need to enumerate (A, B) and compute C accordingly. Such method can be improved by enumerating only A and find the upperbound and lowerbound of B. All the values between lowerbound and upperbound are valid B. Note that B should be integer.$0 \lt A \cdot B = N - C \lt N \implies 0 < B < N/A$N = int(input()) ans = 0 for A in range(1, N): lb = 1 ub = math.ceil(N / A) - 1 ans += ub - lb + 1 print(ans)   » I believe F can be solved using monotonic set  » 3 years ago, # | ← Rev. 3 → I have written an unofficial English editorial.you can find it here.UPD: Added editorial for problem F. •  » » In the explanation for C : Could you please explain how the number of ways of choosing is N/A ?I have tried to do it on paper but couldnot come up with the intution. •  » » » It should be$\frac{N - 1}{A}$fixed it now, thanks for notifying me.The reason for that is for every$A$there can be$\frac{N}{A}$numbers for be such that$ A \times B \le N$, however we should subtract$1$because$C$can't be equal to zero.  »  » Can E be solved with Matrix exponentiation??  » 3 years ago, # | ← Rev. 3 → I tried to solve E,but for some unkown reason,I got two RE.Can you help me? Code#include #define int long long using namespace std; int n,mod,x,ans; pair a; int a2; signed main() { cin>>n>>x>>mod; x%=mod; int pos=0,len=0,pos2=n,sum=0; for(int i=1;i<=n;i++) { ans+=x; a[x].first=1; a[x].second=i; a2[i]=x; x=(x*x)%mod; if(a[x].first==1) { pos=a[x].second; pos2-=i; len=i-pos+1; for(int k=pos;k<=i;k++) sum+=a2[k]; break; } } ans+=(pos2/len)*sum; pos2%=len; for(int i=1;i<=pos2;i++) { ans+=x; x=(x*x)%mod; } cout<  » Editorial DHow to solve in O(nlogn) when the transitions cannot be written as a sum of small number of segments? •  » » 3 years ago, # ^ | ← Rev. 2 → [ignore this, too much complex] •  » » 3 years ago, # ^ | ← Rev. 2 → let$J$be the set of possible jump lengths, now$ J = \cup[l_i,r_i] $Now we can use generating function$ G $to define that set.$G = \sum_{i=0}^N c_i x^i $where$ c_i = 1$if${i \in J}$else$c_i = 0$. Now, number of ways to reach from$1$to$N$using exactly$k$jumps =$[x^{N-1}] G^k$. As there is no restriction of jumps,so we sum it over all possible$k$. so, finally what we need is$[x^{N-1}]\sum_{k>=0} G^k = [x^{N-1}]\frac{1}{1-G}$now coefficient of$ x^{N-1} $in the polynomial$\frac{1}{1-G}$can be easily calculated by calculating inverse of polynomial$ 1 - G $restricted to max degree$N$. Overall complexity is$O(N\log{}N)$For calculating inverse of polynomial you can refer Operations on polynomials and series  » In problem E , How can I know that the series will repeat itself? •  » » Pigeon hole principle •  » » » I know Pigeon hole principle but i can't understand how can we know that the series will repeat itself? •  » » » » There can only be$M$different values of$A_i$. Therefore, it's inevitable that the sequence will repeat in at most$M\$ iterations.Also this topic is 2 years old
•  » » » » A[i] is only dependent on A[i-1]. Therefore, given the last value, there is only one and only one possible current value. It also means there can only be one and only one possible next value A[i+1]`.
•  » » » » » Thanks ^^