I found that calling the clock either using std::chrono or clock seems to yield random results that weren't reflecting the runtime.

Example (484E - Sign on Fence): 351863278, 351863257, 351863126.

Example (CPU clock tester): 351862293, 351861650, 351860904.

I just discovered a problem, https://qoj.ac/contest/1901/problem/8616, that the intended solution is https://codeforces.me/blog/entry/67001. Is there any sub $$$O(nq)$$$ solution for this problem?

I have a question regarding Div 3/4 editorials: Why isn't range trees being used in any problem except last Div 3 problem? Many problems seems more intuitive to do with range trees than with sets. No need for iterators and is certainly more flexible, too. One such example I have seen is 1374E2 - Чтение книг (сложная версия), where two Fenwick trees with binary lifting is, in my opinion, more direct and easy to understand than the editorial's solution.

Given a tree rooted at node $$$1$$$, each node $$$i$$$ has value $$$a_i$$$, let $$$s(u)$$$ denote the set of nodes in $$$u$$$'s subtree. You should calculate the sum: $$$\sum_u{(XOR_{c\in s(u)}(a_c+d(u,c)))}$$$.

I have reduced the problem to:

• Add 1 to every number on a segment.

• Find XOR on a segment.

But I can't think of any DS that solves the problem above. Any help will be appreciated.

I have this code here: https://codeforces.me/contest/444/submission/310588587. It is really weird that:

• On custom invocation, it sometimes output 6, then after that it just do -1

• The res[id][i] value never seems to be written to the correct value (2), even though I have checked for overflow and the value is correct

• On my machine, it output 2 as normal.

• Putting res as a global variable fixes the above.

Can anyone explains why this happen, is it a bug in my code or a bug on Codeforces?

There is a problem that I solved earlier: Find how many permutations p s.t. $$$|p_i-i|\leq k$$$ for all $$$i$$$. Constraints: $$$n\leq 10^9,k\leq 4$$$. I solved it using matrix multiplication (converted ARC132C 's transitions to matrix form), but naively multiplying the matrix creates the insane complexity of $$$O(64^k*\log(n))$$$. By skipping the non-zero terms in the left hand side, I was able to get it passed. Can anyone explain why this passes, and maybe prove the complexity of it?

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?

A. Guess the DNA!

B. Bit GCD

C. Permu Shift

D. Biased Coin

When I was doing 1207F - Задача об остатках, 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 \lt 2^{31}, 0 \lt x \lt 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).