Блог пользователя dush1729

Автор dush1729, история, 4 года назад, По-английски

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
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

You can't solve it by making 9 segment tree. In fact,one segment tree with lazy tags can perfectly solve this problem.

»
4 года назад, # |
  Проголосовать: нравится +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<n;i++) { for(j=i-1;j>=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<<x;

why is it working???

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Weak test cases.

    Testcase
»
4 года назад, # |
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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

for E, I'm storing updated digits as lazy values, submission