Your approach for SQRGOOD problem from JAN18

general
, ,
1

Can anyone please explain their solution to SQRGOOD problem from JAN long.

I tried using inclusion-enclusion and binary search but was able to do only 1st subtask.

Thanks :slight_smile:

2

approach that worked for me (broad strokes):

  1. given n, you can guess z, so that your guess will be not further than \Delta = 10^6 from the answer

  2. compute f(z) - number of x \in [1..z], such that x can be simplified

  3. for every x \in [z-\Delta~..~z+\Delta] determine if x can be simplified

  4. move your guess towards the real answer using information from steps 2 and 3

some details:

  1. you can do some experiments and figure out that guess z = a \cdot n will work, a \approx 2.5505460967303765

  2. to compute f(z) let’s define another function g(z, Y) - number of x \in [1..z], such that x is divisible by some y^2~|~y \in Y, then f(z)=g(z,P), where P is set of all prime numbers from [1..\sqrt{z}], also g is recursive function:

g(z,Y)=\lfloor\frac{z}{y^2}\rfloor-g(\lfloor\frac{z}{y^2}\rfloor, Y \setminus y)+g(z,Y\setminus y) ~~ | ~~ y\in Y

first difficulty is that there are lot of prime numbers under \sqrt{z}, so I ended up implementing segmented bit-packed sieve of Eratosthenes with factorization wheel mod 30, it gives you the way to iterate over prime numbers from P very fast (in case you don’t want to store them), so I split set of primes to two subsets P_{small} \subset [1..\sqrt[3]{z}] and P_{big} \subset (\sqrt[3]{z}..\sqrt{z}] and I handled them differently (you can optimize out divisions and cache some stuff for P_{big}, also you don’t need to store them), and you will need to store P_{small}

second difficulty is computing g(z,P_{small}) (required for g(z,P)) reasonably fast, some caching techniques worked for me

  1. you just need to mark numbers on segment [z-\Delta~..~z+\Delta] that are divisible by p^2~|~p \in P, it is simple for p \in P_{small} (works similar to sieve), and the key observation for p \in P_{big} is that multiple of p^2 can happen at most once in the segment, so it can be found during step 2, since you’re not storing P_{big}
1 Like
3

I’ll try (full disclosure: I only got 50 in the contest, but I looked at a couple of the 7* 100pt answers to see what I missed).

Before starting, I would google “counting square-free numbers”. There is a fair amount of theory that you probably don’t need to develop from scratch.

The high-level approach is to develop a sufficiently efficient function, say S(x), which will return the number of Square-Free integers less than or equal to x. We then create a new function H(x) = x - S(x) which gives us the number of “simplfyable radicals” less than or equal to x. Finally, we implement some sort of search (e.g. binary search, root solving, etc.) to repeatedly evaluate H(x) and find the value of x for which H(x) = N and H(x-1) = N-1. One thing that helps here is that H(x) is monotonic and is very well approximated by (1-6/\pi^2)x, so we can use this fact to get “close” to the correct answer very quickly (for me, 2 evaluations was generally good enough to get within 100, after which i brute-forces a square free check).

What remains is to develop an efficient implementation of S(x). This is actually a Project Euler question (#193). For the 10^{14} bar, you can pretty naively implement the following formula which you can search up:

S(n)=\sum_{d=1}^{\lfloor\sqrt{n}\rfloor}\mu(d)\left\lfloor\frac{n}{d^2}\right\rfloor.

Here S(n) is the number of square-free integers less than or equal to n, \lfloor x \rfloor represents the “floor” of x, or equivalently, the greatest integer less than or equal to x, and \mu(d) represents the Mobius function.

What is the Mobius function, you might ask? Well, the Mobius function \mu(x) is defined as

  • 0, if x is divisible by the square of a prime.
  • 1, if x has an even number of prime divisors.
  • -1, if x has an odd number of prime divisors.

If you are so motivated, you can actually derive this equation from nothing more than the same inclusion-exclusion arguments you tried earlier. The following link has the derivation in the appendix: https://arxiv.org/pdf/1107.4890.pdf.

In practice, you can use something very similar to a Sieve of Erastothenes to sieve out \mu(d) in near linear time. If you want to precalculate \mu(x) for 1 \le x \le N for some N, I think you pretty much have two choices:

  • Pre-seive all of the primes up to N, and then sieve \mu(n) directly (initializing to 1s, zeroing out multiples of the square of the prime, and then “inverting” all of the multiples.)
  • Sieve with primes up to \sqrt{N}, but this time, instead of just keeping an array of {0,-1,1}, we keep a “running product” array. You can google this up to. You only have to sieve up to \sqrt{n}, but you have to keep doing products.

I tried both, and I actually found the first to be a bit faster as it avoided the multiplies, but it may have been an artifiact of my code.

For the 10^{16} bar (and especially the 10^{18} bar), I wasn’t able to just use the naive sieve (perhaps there is a way for 10^{16} if you really spend time optimizing it). The trick is to realize that there is a smarter way to calculate that sum S(n). To that end, we need a key result and than a clever idea to use it:

The key result involves the Mertens function M(x), which is simply the running sum of the mobius function. That is

M(x) = \sum_{i=1}^x \mu(i).

The number theory result suggests that the Mertens function can be calculated in sub-linear time. There are a couple of approaches, but one recurrence that can be used is

M(x) = 1 - \sum_{d=2}^{x} M(\lfloor x/d \rfloor).

Deriving this is beyond the scope here.

The other key observation is that, in the evaluation of S(n), once d gets large enough (around \sqrt[3]{2n}), the successive terms \lfloor x/d^2 \rfloor will start matching each other. When this happens, it makes sense to evaluate the sum “in blocks”, where

\mu(d) \lfloor x/(d)^2 \rfloor + \mu(d+1) \lfloor x/(d+1)^2 \rfloor + \cdots + \mu(d+n) \lfloor x/(d+n)^2 \rfloor

with \lfloor x/(d)^2 \rfloor == \lfloor x/(d+n)^2 \rfloor is instead replaced by

\left[\mu(d) + \mu(d+1) + \cdots + \mu(d+n)\right] \cdot (n+1) = \left[M(d+n) - M(d-1)\right] \cdot (n+1) .

We can also play this same “tail trick” in the evaluation of the Mertens recurrence. Once d gets large enough, \lfloor x/d \rfloor will start to repeat in blocks.

The Mertens recurrence is really the hardest part. I saw some efficient function memorization structures for speeding this up in one of the solutions I looked at.

Anyway, that was longer than I intended to write, but perhaps this gives the gist of the 100 point solutions (at least the two I looked at seemed to utilize this approach).

2 Likes