### div24ever's blog

By div24ever, history, 5 weeks ago,

Can't find any announcement for ACL Beginner Contest, so creating this to discuss problems.

C
D

How to solve E?

I tried to make 9 segment tree for each 1 — 9 digits but couldn't find how to do update query where setting everything between l to r to zero when removing digit and to one when adding it.

• +13

 » 5 weeks ago, # |   +17 You can't solve it by making 9 segment tree. In fact,one segment tree with lazy tags can perfectly solve this problem.
 » 5 weeks ago, # |   +7 For D, I saw submissions and some people have just used the traditional longest subsequence approach. The only difference being they are only checking the last 100 indexes.x=1; for(i=1;i=0 && i-j<=100 ; j--) { if(abs(a[i]-a[j])<=k) dp[i]=max(dp[i],dp[j]+1); } x=max(x,dp[i]); } cout<
•  » » 5 weeks ago, # ^ |   0 Weak test cases. Testcase200 1 1000 (Arithmetic progression of size 198 where a = 1, d = 2) 1001 
 » 5 weeks ago, # | ← Rev. 2 →   +8 For E, you can make a single segment tree, where each node holds the value of the integer % MOD. In each update, a range of leaves is changed and the rest is recomputed (the value for each node is $10^{r-(l+r)/2} \times val_{left} + val_{right}$ ) . In order to make this in time, we need lazy propagation. We can only update the top-most node for which the whole range needs to be updated. The value can be calculated as a geometric sequence eg $digit \times (100 + 1000 + 10000 + \dots )$. The value of this sum is equal to $\frac{digit \times (10^x -1 )}{9}$. The result for each query is the top node.Also remember your mods and modular inverse for division by 9. My (messy) code (doesn't use ACL): here
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   +8 Solution using ALC: https://atcoder.jp/contests/abl/submissions/17053342. It uses the same idea that cfalas described.
 » 5 weeks ago, # |   0 for E, I'm storing updated digits as lazy values, submission