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

Digit dp?

I think my solution is the same. I split the array into subarrays whenever we encounter a 3, and then for each subarray, we store the occurrences of $$$[1, 2]$$$ and $$$[2, 1]$$$. Note that only the first occurrences of the subarray will contribute to the answer.

I have a solution without any casework.

let ignore sequence with single $$$0$$$ first since we can calculate its contribution to answer easily, then we can find that $$$3$$$ can only be at the first sequence, and there will be at most one extra sequence which only have $$$1$$$, and at most one extra sequence only have $$$2$$$.

So we can just do $$$dp[\text{n}][\text{the last element of first sequence}][\text{flag1}][\text{flag2}]$$$ where $$$\text{flag1/flag2}$$$ represent whether we have a extra sequence with $$$1/2$$$.

Nope

Complete code ? Thank you, here's the meme for you.

Why would you paste code without a link ? Improve your manners

Explaination: In a subsequence only the last element matters. We count answer by counting 0s and non-zero sequences. For 0 at position i it contributes i*(n+1-i). We construct a FSM for another part of the anwser, where its states are represented by the last element of each non-zero sequence. By compute with brute force we can show that there are only 16 possible states: (none),1,2,3,12,21,32,31,22,11,112,221,312,321,212,121. Then we can number these states and make the state transition table manually. Remaining work is trivial.

On this question t can be up to 10000 and n can be up to 999999. On the worst case scenario your code perform 10000 * 999999 operation that's why it is getting TLE verdict. It is better to memorize the answer from 1 to 999999 instead of calculating the result repeatedly.

Add edges from new_s and edges to new_t with a very negative value, and add edges from t to s with a very positive value, the new graph will not have negative cycles, find the min cost max flow in the new graph and delete new_s, new_t to run min cost flow from s to t.

probably because push_back is slow

Same code as yours but with C++20 (185029658) gives MLE. I suspect yours is MLE too.

def solveShit():
    m = int(input())
    s = [getStrs(), getStrs()]
    cnt =0
    cur = 1
    flag = False
    for i in range(m):
        if s[0][i]==s[1][i]:
            cur = not cur
        else:
            if s[cur][i]!='B':
                break
        cnt+=1
    if cnt==m:
        flag = True

    cur = 0
    cnt =0
    for i in range(m):
        if s[0][i] == s[1][i]:
            cur = not cur
        else:
            if s[cur][i] != 'B':
                break
        cnt+=1
    if cnt==m:
        flag = True
    if flag:
        print("YES")
    else:
        print("NO")

got TLE with input 1,8388609 where diff=8334608=1<<23 and your solution consumed too much time for factorization. In fact answer is 1 when x,y are both odd numbers, so determine it first can save a lot of time

also there's no need for push duplicated element to s1

Just replace endl with '\n' and your solution will pass.I faced the same issue

Man, just 1 more good contest to go. All the best!

Is the code based on Brent's improvement on Pollard's Rho? FYI, The constant on the one with Brent's improvement is quite smaller than the vanilla one.

do you have any updates? when will the rating be out?

Use '\n' in place of endl to reduce the time of your soln. My solution got accepted during the hacking phase with the same time as yours, but got TLE during system testing..

This is also your solution getting TLE on test 3. You probably have an undefined behavior somewhere in your solution. I don't think the contest authors can do anything about that.