a_gt3_rs's blog

By a_gt3_rs, history, 2 weeks ago, In English

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.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By a_gt3_rs, history, 3 weeks ago, In English

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?

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By a_gt3_rs, history, 5 months ago, In English

A. Guess the DNA!

Solution

B. Bit GCD

Solution

C. Permu Shift

Solution

D. Biased Coin

Solution

Full text and comments »

  • Vote: I like it
  • -7
  • Vote: I do not like it

By a_gt3_rs, history, 7 months ago, In English

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}$$$:

$$${\lfloor \frac{a}{x} \rfloor} ={ \lfloor{\frac{a*\lceil{2^{31+\lfloor{log_2(x)}\rfloor}/x}\rceil}{2^{31+\lfloor{log_2(x)}\rfloor}}}\rfloor}.$$$

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).

Full text and comments »

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

By a_gt3_rs, history, 8 months ago, In English

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).

Full text and comments »

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