atcoder_official's blog

AtCoder Beginner Contest 448 Announcement
By atcoder_official, history, 2 months ago, In English

We will hold AtCoder Beginner Contest 448.

We are looking forward to your participation!

  • Vote: I like it
  • +33
  • Vote: I do not like it

»
2 months ago, hide # |
 
Vote: I like it -19 Vote: I do not like it

哇，G有675分诶~

→ Reply
»
2 months ago, hide # |
 
Vote: I like it -26 Vote: I do not like it

深刻悼念寒假同志

→ Reply
»
2 months ago, hide # |
 
Vote: I like it -23 Vote: I do not like it

Wow! Chinese is very unusual on Codeforces.

→ Reply
»
2 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

The Hardest ABC.:( How E&F

→ Reply
  • »
    »
    2 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    I can't solve E(

    For F,you can use the Mo's algorithm with (奇偶化排序 in Chinese,but I don't know how to say it in English).And change your block len to about 80000 or 130000.

    → Reply
  • »
    »
    2 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    For F: https://mirror.codeforces.com/blog/entry/61203

    → Reply
  • »
    »
    2 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    For E, do the following steps:

    1. Find $$$mod = N \% M$$$.

    2. Set $$$N = N - mod$$$.

    3. Now the floor disappears from the problem. It asks you to find $$$N/M \% 10007$$$. This can now be done easily since you can use the regular modular inverse on $$$M$$$.

    Finding N % x

    Note that $$$N$$$ can be expressed as:

    $$$N = \sum_{i=1}^{K}{(c_i c_i c_i...l_i times) * 10^{\sum_{j=i+1}^{K}{l_i}}}$$$

    $$$N = \sum_{i=1}^{K}{(111...l_i times) * c_i * 10^{\sum_{j=i+1}^{K}{l_i}}}$$$

    $$$N = \sum_{i=1}^{K}{(\sum_{j=0}^{l_i-1}{10^j}) * c_i * 10^{\sum_{j=i+1}^{K}{l_i}}}$$$

    You need to be able to calculate $$$\sum_{i=0}^{N}{10^i}$$$ fast. That can be done using halving like binary exponentation.

    And $$$\sum_{j=i+1}^{K}{l_i}$$$ is just the suffix sum, which can be precalculated.

    Decrementing N

    I think doing $$$N - 1$$$ is a lot simpler to do since the RLE is given. It changes the last few digits only.

    So after finding $$$N \% M$$$, you can just decrement $$$N$$$ by $$$1$$$ that many times.

    Submission: 73938944

    → Reply
»
2 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

I just discuss about whether or not to use #define int long long on cf-blog like the day before, I don't do it and that wreck me from time to time, and this is the time that the curse cast uppon me, I don't see that my bigmod function overflow at exponent arguent(int) and spending the whole contest just to debug E 😭 I'm going full #define int long long from now on... 🥀 🥀

→ Reply
»
2 months ago, hide # |
 
Vote: I like it +15 Vote: I do not like it

F is same as 576C

→ Reply
»
2 months ago, hide # |
 
Vote: I like it -30 Vote: I do not like it

为什么F题题解中为什么没有Hilbert曲线的做法？

→ Reply
»
2 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I think problem E and F are very good ones for practice.

For prolem E, one needs understand how to calculate a/b mod p, where a/b is some integer. The derivation looks like the following:

let a/b = qp+r, and then we are going to compute r = (a/b) mod p. As a = qbp+rb, then a mod bp = (qbp+rb) mod bp = (qbp) mod bp + (rb) mod bp = (rb) mod bp, as r < p, so (rb) mod bp = rb. Thus we have a mod bp = rb, and r = (a mod bp) / b. So, we get a/b mod p = (a mod bp) / b.

Problem F needs a little bit construction. Whenever we see such a problem, we should never forget the famous sqrt-decomposition idea. I think this is why we are told to solve as many problems as possible, because if you have enough experiences, it will not take a long time to come up with this idea. On the other hand, the complexity analysis part is also very educational. Sometimes, we should consider all the operations as a whole or based on blocks, while sometimes we should consider them one by one.

→ Reply
  • »
    »
    7 weeks ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it 
    We want to compute: floor(N/M) mod p.

Let x = floor(N/M).

By the division algorithm:
x = q*p + r, where 0 <= r < p.

So,
floor(N/M) = q*p + r
=> floor(N/M) mod p = r.

Now relating it to N:

N = M*floor(N/M) + (N mod M)

Substitute floor(N/M) = q*p + r:

N = M*(q*p + r) + (N mod M)
N = q*p*M + r*M + (N mod M)

Thus we cannot write
N/M = q*p + r
because N/M may not be an integer.

But in the editorial he directly wrote:
N/M = q*p + r

Can someone please explain how this step is valid?
    → Reply