where ever i go,i see your comments

ScreenCast for A-D.

good luck brooo!! without take part this contest!!

you have gained more contribution than me by using my meme.

Too relatable

This itself is an expectation

Send code? I got it through even with Rust:

fn sieve(n: usize, lpf: &mut Vec<usize>, primes: &mut Vec<usize>) {
    lpf.resize(n + 1, 0);
    for x in 2..=n {
        if lpf[x] == 0 {
            lpf[x] = x;
            primes.push(x);
        }
        for i in 0..primes.len() {
            let p = primes[i];
            if x * p > n {
                break;
            }
            lpf[x * p] = p;
            if x % p == 0 {
                break;
            }
        }
    }
}

let lpf = &mut Vec::new();
let primes = &mut Vec::new();
sieve(10_000_000, lpf, primes);

Should be easy to translate to C++

I think generating primes till root(10^7) is sufficient for the problem.

You dont need to generate prime numbers up to 10^7. Generating till sqrt(10^7) is sufficient.

I ised linear sieve of erastothenes and it didn't led me to tle !

Here is a test case that might help:

$$$\texttt{6}$$$

$$$\texttt{2 1 3 1 1 2}$$$

For me this was wrong: it is possible to have a sequence of size $$$3$$$ (excluding $$$0$$$'s),

Just before failing on WA16 my states:

vector <int> st[Maxs] = {{}, {1}, {2}, {1, 2}, {2, 1},
                         {3}, {3, 1}, {3, 2}, {3, 1, 2}, {3, 2, 1}};

I passed it with states:

vector <int> st[Maxs] = {{}, {1}, {2}, {1, 2}, {2, 1},
                         {1, 1}, {1, 1, 2}, {1, 2, 1},
                         {2, 2}, {2, 1, 2}, {2, 2, 1},
                         {3}, {3, 1}, {3, 2}, {3, 1, 2}, {3, 2, 1}};

States represent the order of relevant stacks. Some duplicates should be allowed as 3 could consume the first duplicate.

try "aaaa"

Precompute the factorisation, or more specifically only the smallest prime factor. This can be done with a linear sieve (there's a cf blog on it). I posted my code 4 comments above.

How did you factorized ? If you used seive, then I don't think it would have given you TLE!

$$$O(\sqrt{n})$$$ will clearly TLE. Instead you can use $$$O(\log n)$$$ factorization using eratosthenes' sieve (or you may be able to squeeze pollard's rho in TL but I think it would be hacked afterwards)

Same here. I have seen a lot of solutions that passed that way. It is either we have missed something in the implementation or most of the solutions that passed that way will be hacked.

I factorized $$$y - x$$$ and did not get TLE: 184943623

Note: I used a sieve to generate the largest prime factor for each odd number from $$$3$$$ to $$$10^7$$$. I could have just used any prime factor (by letting the $$$j$$$-loop start from $$$i^2$$$), which would've been faster.

If you TLE'd, my guess is that your sieve might not have been a very good one (e.g., outer loop running till $$$10^7$$$ instead of its square root)

Need factorized |y-x| carefully.

We can save the min factor of any number less than 10^7. Now for factorizing |y-x|, we can remove its min factor, and do it again, until all of factor found.

My issue (and I suspect a lot of other getting TLE on D) turned out to be using "<< endl" instead of "<< \n". 1e6 instead of usual 1e5 output lines turns out to be the magic threshold where output speed matters, and even such small issue can kill you.

I don't think so, but looking at your submission, it can be optimised by using a linear sieve instead.

Waiting for a reply to the same question! xd!!

One of my WA submissions fails on

5

1 2 3 2 1

Edit: Okay, your latest submission fails on this case too

https://mirror.codeforces.com/blog/entry/109994?#comment-979536

Okay, i understood my mistake, thanks

My idea (didn't write up a complete solution btw, so take this with a grain of salt):

The number of non-zero subsequences is at most 3. We can try to count how many subsegments will generate each possible number of subsequences.

• No non-zero subsequences -> The subsegment contains only 0s. We can easily count how many there are.

• Exactly one non-zero subsequence -> If we look at the non-zero values of the subsegment, we must not have a 2 followed by a 1 or a 1 followed by a 2 (so there is always a 3 in between)

• Exactly two non-zero subsequences -> This seems to be the hardest, so I was planning to find this by subtracting the others off of the total.

• Exactly three non-zero subsequences -> There are two sub-cases:

• • Second non-zero subsequence ends with 1: Subsegment contains a 2 followed by a 1 (ignoring 0s in between). Later, after some 3, we get a 1 (so both non-zero subsequences end with 1) and then a 2 (which must form a third non-zero subsequence). Ignore all 0s in between.
• • Second non-zero subsequence ends with 2: Symmetric to the other case

The challenge I faced with these counts is on the 0s. It's not enough to just find some segment that fulfills a condition, because a group of 0s can merge easily with whatever fulfills the left side and also whatever fulfills its right side, and I couldn't figure out how to deal with this effectively.

$$$\gcd(a + k, b + k) = \gcd(a + k, b - a)$$$, so for it to not be $$$1$$$, we want $$$p \mid a + k$$$ where $$$p$$$ is a prime factor of $$$b - a$$$. Therefore, we generate all prime factors of $$$b - a$$$, which is precomputed by sieving. Then, $$$p \mid a + k$$$ means $$$k = (-a) \mod p$$$. Take the minimum over all prime factors.

DP was also my first instinct, but then I realized that the path was simply forced to go up/down if the other cell was also Black, and from then on the only possible continuation was going to the right, and repeat.

Me, too, wasted some of my time by thinking in the direction of DP ;)

lol i also did a dp solution haha new learning for me

Depends on how far you thought ahead.

My Submission: 184943623