| # | User | Rating |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
Is this problem doable with less than $$$O(n\sqrt{n}log(log(n)))$$$ time?
Given an array $$$p$$$, assuming $$$p_i=O(n)$$$. The array is cut to $$$O(\sqrt{n})$$$ blocks.
There is only one kind of query:
$$$1\ i\ j\ k$$$: Count the numbers from block $$$i$$$ to block $$$j$$$ such that $$$p_k$$$ is a multiple of (the query must be done in $$$O(1)$$$).
Any help is appreciated.
Given the problem below: Find the lexicographically minimum cyclic shift of a binary string s of length n ($$$n\leq 3*10^4$$$). A normal brute force solution runs in only 0.05s:
string x = s;
for (int i = 1; i < s.size(); i++)
{
string x2 = string(s.begin() + i, s.end()) + string(s.begin(), s.begin() + i);
if (x2 < x)
x = x2;
}
cout << x << endl;
I only know an $$$O(n^2)$$$ algorithm (the algorithm above) or $$$O(n^2/w)$$$ using bitsets. Is this the intended solution, or is there any better algorithm?
When I was doing 1207F - Remainder Problem, I don't know why my program got TLE. Then this ONE trick cut 1 second off my program. You can see this video for more information: https://www.youtube.com/watch?v=ssDBqQ5f5_0. When the compiler compiles x/9, the code roughly converts to ((long long)954437177*x)>>33. Division is a much more expensive operation than multiplies and shifts. But what's the special constant 954437177? It's $$$\lceil \frac{2^{33}}{9} \rceil$$$. So we have this identity which is vaild for every $$$0\leq a < 2^{31}, 0 < x < 2^{31}$$$:
You can clearly see how this speeds up 1207F: 244531668, 244540601. Note that gcc also does this trick on 64 bits.
After brute forcing with $$$a = 2^{31}-1$$$ I got this new, fixed identity. This should work for all $$$a$$$ (while the old one does not).
This is only a suggestion. GCC 13.2 have nearly full C++23 support & (we once had GCC 11 with C++20). So I just want that GCC 13.2 (or 14) has C++23 support enabled with -std=c++23 (as another GCC 13 compiler option, or when GCC 14 is released, or when GCC 11 is back).
