Yes, you are right. Sorry for the typo. :(

It seems that a lot of people are asking so I have updated the article to include it as the 4th example.

Yes, you are right.

Still, for the sake of argument, one would need to show how to compute that in $$$O(1)$$$, which is basically what I was doing below. :)

It is more about compressing the code to fit in the page limit in a typeable and checkable style than to read it, since you only need to type/copy-paste it during the contest anyway.

Actually, reading, checking and understanding the code in the reference should be done before a contest, when you have plenty of time to refactor the code and get familiar with it. Much time is unnecessarily wasted should you have to read or question a code in the reference during a contest.

...Or if you run short on preparation time, just figure out the interface and forget about the implementation. You only need to type it or copy-paste it during the contest anyway, which, of course, does not need readability at all.

I do agree it is the worst code style though, but just think about the 25-page limit of the World Final. :)

Auto comment: topic has been updated by Nisiyama_Suzune (previous revision, new revision, compare).

Auto comment: topic has been updated by Nisiyama_Suzune (previous revision, new revision, compare).

Simply substitute $$$n=gcd(i,j)$$$ in this formula.

Fixed. Thank you!

I think that there is an invalid test case in Problem F. It appears that the test case 11 has M > 100000.

TLE Code: 43149555

AC Code: 43144968

I think that Problem F can also be dealt with easily should one know about the technique of Extended Eratosthenes Sieve.

That is, we can even solve the problem for n ≤ 10¹¹ without the memory limit. :)

My code: 41366266

By the way, Problem E can also be done by finding the minimal string rotation of two convex hulls and compare them with brute force.

That is an interesting idea. Unfortunately, I have rechecked the code and it seems that the code works well on random cases. The information is updated at the end of the post.

Auto comment: topic has been updated by Nisiyama_Suzune (previous revision, new revision, compare).

I think that Div 1. E can be solved with a simple segment tree.

First, just as the tutorial says, we check the possibility of "INCORRECT". Then, each of the m moments can be treated as a open-ended 3D-box, i.e. denote the moment as (x_i, y_i, z_i), if x_i < x_l, the restriction for knowing the moment (x, y, z) is "CLOSED" using this knowledge will be x ≤ x_i, if x_l ≤ x_i ≤ x_r, there will be no restriction for x, and if x_i > x_r, the restriction will be x ≥ x_i. The same goes for y_i and z_i. Putting the 3 restrictions together gives you a open-ended 3D-box. The query is actually asking whether each point is in any of them.

This is not difficult as it seems to be. First, there are actually 8 kinds of different boxes, regarding the  ≥  or  ≤  sign. We can deal with them by mirroring the coordinate and do the same process 8 times, so we only need to focus on {(x, y, z)|x ≤ x_i, y ≤ y_i, z ≤ z_i} situations. This is done by a scanning line trick. We sort both the queries and the boxes by descending x coordinate. Then each time we need to update something like {(y, z)|y ≤ y_i, z ≤ z_i} when we meet a box, which is simply done by a segment tree in the range of [1, y_max], maintaining the maximum value of z_i on y_i so that there is a box covering {(y, z)|y = y_i, z ≤ z_i}.

My code: 40807344

Awww...My bad. Will fix it, sorry!

Based on my knowledge, only crossing out even numbers first does not make a sieve O(n), so I doubt its correctness on complexity. For instance, 105 will be visited multiple times (for 3, 5 and 7) in your code. Therefore, I think your code still performs in . However, I do think there is not too much difference between O(n) and in sieves. The reason why I introduced the algorithm is mainly that it can help to compute the multiplicative functions, where other sieves are less likely to do so.

You are right :)

It appears that I accidentally saved it as a draft. The issue should be fixed by now. Sorry for the inconvenience!

Thanks for the compliment:)

It would appear that this technique is established in 1978 by David Gries and Jayadev Misra at the communication of the ACM. They had a paper here. However, I was unable to purchase it so I cannot determine whether it is true.

I see. My friend has also made a hack to my own program:

7
abababc
3
ababc
1

Many thanks!

Would you mind sharing why most people got E WA'd by using dp[sprefix][xcnt][flag]? I tried to come up with a counterexample but nevertheless failed.

Actually, you can see the test cases here for yourself.

That's pretty unexpected. I originally thought about some edge cases, but did not ponder too much on the algorithm. Thanks a lot!

Actually, anyone mind sharing what E's test 24 or its general idea is? A lot people get WA'd but the case is too long to be read or copied.