Maybe in python it's float("inf")

I understand if you don't like it, it is slightly different, but calling it cringe without any feedback isn't very nice, don't you think? :)

Subtask means the problem will be divided into two parts, one will be easier with lower constraints and one will be harder with higher constraints.

I think the most important issue is that both C++14 and C++17 (32 bit) don't support __int128.

I wonder why no one has mentioned it before, at least on CF.

If there is a corresponding Div. 1 round, then you belong to Div. 1

Arre Pogi, tum yaha??

Versions of tasks with different sub-conditions.

For example:

D1 and D2 from https://mirror.codeforces.com/contest/1934/standings

D1 and D2 from https://mirror.codeforces.com/contest/1903/standings

two problems without partial points

i put contest specifically in lc biweekly time so i can get a high rank after a long time

it became speedforces

SAFE!

Deleted.

Hint:

First consider the 2*n size array where, in first half all elements from 1 to n are present and in the remaining half all elements from 1 to n are present {these two half will have same xor}.

then, try to think what will happen if we swap some of the elements.

It's just that the codeforces is lagging

U

The second smallest element with frequency 1 is the answer.

0 0 1 1 2

Answer is 3

0 0 1.

Alice picks 1. Bob picks 0. Alice picks 0. Mex is 2.

0 1 1 2 2

Actual answer : 3 Your answer. : 2

How did you solved it ?

Code is not public yet.

Man, I'm stress testing with actual AC codes rn and nothing's coming up. What the actuall fuck

Can you share the test case?

Edit: Nvm, system tests are over

Hello , I took a look at your solution , you only subtract 3 when the sequence is alternating ababababa, but it's actually you need to remove all the odd values, 3 5 7 ...

If you have a palindrome, say abcddcba, and you append a character x at the end. Under what condition will it remain a palindrome?

there was a long queue (~10mins) towards the end of the contest, its the only fair decision

Same, I left before the round was finished.

Fully agreed. Also, no announcement was sent to Div1 contestants before the scheduled end time.

But never give up until the last moment, right? Leaving early is not the right approach.

I apologize that the original announcement of extension has not reached the Div1 participants. Normally, it is sent simultaneously to both contests, however, I can see that this time it has only been sent to Div2. I guess either I misclicked, or the system malfunctioned.

Did not get the notice of the extension and hence did not submit D2 which was a couple minutes of debug away. :(

If the substring has all identical characters, the answer is zero. If the substring contains alternating characters such as ababab, the answer is summataion of all even $$$k$$$. Otherwise, all $$$k \geq 2$$$ contribute the answer, except the original substring, which will contribute only if it is not a palindrome.

The crucial idea is : If you have a palindrome, and you append a character at the end, there are a very limited set of scenarios in which the new string would also remain palindrome (that's where the motivation for alternating string comes in).

wrong

Lol I did the same mistake too..

Can you share it's solution.

You might be surprised to hear that it was actually placed at 2F(1D) when I tested

Well done, Amazing performance Kevin114514. It was a nice comeback, indeed!!!

At least I used it, hope it will pass systests

i did using hashing

Yes, this should be correct. By the way, since we are already using polynomial hashes, can't we just compare substring hash with its reverse for equality?

Checking whether the substring is a palindrome or not within the given constraints was the most difficult part for me

For polynomial hashes of a substring, you can use some sort of prefix sums, instead of a segment tree, because there are no updates.

I Just do what you said, but it gives WA on pre#2.

Code:

#include <bits/stdc++.h>
using namespace std;

class Hash {
    typedef unsigned long long ull;
    vector<ull> h, p;
    ull mod = 1145141919810LL;
public:
    void generate(const string& s) {
        h.resize(s.size());
        p.resize(s.size() + 1);
        h[0] = s[0];
        for (int i = 1; i < s.size(); i++)
            h[i] = (h[i - 1] * 131 + s[i]) % mod;
        p[0] = 1;
        for (int i = 1; i <= s.size(); i++)
            p[i] = p[i - 1] * 131 % mod;
    }
    ull getHash(int l, int r) {
        if (l > r) return 0;
        if (l == 0) return h[r];
        return (h[r] - h[l - 1] * p[r - l + 1] % mod + mod) % mod;
    }
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n, q;
        cin >> n >> q;
        string s;
        cin >> s;
        string t = s;
        reverse(t.begin(), t.end());
        Hash Hs, Ht;
        Hs.generate(s);
        Ht.generate(t);
        while (q--) {
            int l, r;
            cin >> l >> r;
            l--, r--;
            // abcde
            // 01234
            // edcba
            // 01234
            int xl = n - r - 1, xr = n - l - 1;
            auto sum = [](int L, int R) -> long long {
                return (long long)(L + R) * (R - L + 1) / 2;
            };
            if (Hs.getHash(l, r - 1) == Hs.getHash(l + 1, r)) cout << 0 << '\n';
            else {
                long long ans = sum(2, r - l + 1);
                if (Hs.getHash(l, r) == Ht.getHash(xl, xr))
                    ans -= (r - l + 1);
                if (r - l + 1 >= 4 && Hs.getHash(l, r - 2) == Hs.getHash(l + 2, r)) {
                    // 3, 5, 7, 9, ... (r - l + 1)
                    int R = r - l + 1;
                    if (R % 2 == 0) R--;
                    else R -= 2;
                    int nums = (R - 3) / 2 + 1;
                    ans -= (long long)(3 + R) * nums / 2;
                }
                cout << ans << '\n';
            }
        }
    }
    return 0;
}

/*
121212
1111111

abcdefg
  abcdefg
abababa

ababababababababababa

a bcdedcbax
b=x
c=a
d=b
e=c

abababababab

3,5,7,9

abbabbabb
*/

I think that for checking if given substring in a string is a palindrome, we can use Manacher (but I also did it with hashes)

Did exactly same, still getting WA on test 2, maybe some edge case, disappointing contest for me.

You can also use manacher algorithm for checking palindrome. It's O(n).Manacher

Imagine if there are two 0's, two 1's, two 2's, ..., two 100's. Will Alice be able to guarantee a MEX of 101?

Group the numbers into two groups. One group containing numbers that are repeated only once (single-repeated numbers), and the other group contains numbers that are repeated 2 or more times (multi-repeated numbers). Sort the single-repeated numbers.

Now, the single-repeated numbers are the main thing both Alice and Bob fight over. Because the other numbers are repeated 2 or more times, so if Bob picks one such number, Alice can pick the other copy of the number so both of them will have that number.

So if there are 0 or 1 single-repeated numbers, Alice will grab the number first.

If 2 or more, both of them try to take the single-repeated numbers in ascending order. So Bob will take the second smallest single-repeated number (that may become the MEX).

Now just insert these single-repeated and multi-repeated numbers into a set and find MEX.

Submission for reference

try this case n = 5, k = 2, 1 2 3 4 4 1 2 3 5 5