I became expert for the first time around an year ago. But never got a chance to participate in an unrated div 3 contest. So this is my first unrated div 3.

This div3 round will be the 1800th contest of Codeforces. Congratulations!

....

"do not have a point of 1600 or higher in the rating"?

Whis the last two problems of the contest will be interesting.

looking forward to be pupil finallyy pls

Hope so I reach pupil this time. :-)

My birthday contest! I hope I can become expert. Edit: lol I'm dropping a lot

I hope being specialist after this round

вот блин,почему раунды див3 рейт только для людей с рейтингом меньше 1600(

Apparently I probably get negative delta in the last div 2 round which will put me back to specialist.

If my rating isn't update soon will this round be unrated for me ?

Div.3 is perfect for my first rated contest.
Looking forward to a good rating.

First time to test a codeforces round, The problems are nice, I recommend everyone to participate, have fun and prepare your cats!

muchas gracias aficiónados esto para vosotros SIUUUUUUUUUUUUUUUUUUUUUUUUUUUUU

Круто! Всем удачи на предстоящем 3-ем Диве. Теперь ждём Див. 4)))

This will be my first div 3 contest I'm so excited

There was no Div-3 round in the last month :(. And problems are getting harder nowadays :(.

As a tester, Worst Contest I Have Ever Seen!..

hope a big postive delta I want to rank up to be Specialist:)

this time div3 contest will not be rated for me. Mixed feelings

I hope every participant to get + points and do well today <3.

i will hack you

I have to say it... drumroll.. stringforces

lets become pupil

StringForces

I think first prob should be like: "the string can only contain the letters 'm', 'y', 'a' and 'v' ..."

never thought a day will come that I'll hate strings and string algos.

it's sad that I wasted too much time on D due to a small mistake again :(

I can't reach expert now.

the worst round of my life...

Great Contest!

Enjoyed solving a bunch of problems, Finally back to specialist again :D !

A great Div 3 as always. My best ever contest performance.

A: Pretty trivial, just remove duplicates

B: Process all the good pairs, then for letters with >= 2 occurrences use a k to make them good.

C: Standard priority queue, I took a risk and didn't prove it however. (also got a penalty because I forgot to use long long >.<)

D: Another solution I didn't prove, but I used memoization and checking for !memo[i][s[i]+2] to increment answer

E: I did casework for the easy version, then generalized it for the hard version.

How to solve F?

Nice Div. 4 Contest

Is it possible to calculate the hash when swapping one character with another? I used the polynomial rolling hash algorithm, but my code fails on Test #5 in Problem D, not sure what exactly that I did was wrong. Can someone give me a clue why my intuition was wrong?

Submission

How to solve D?

Wasted 30 minutes in D because I thought hashing would work..

.

stringforces

i think it was nice for speedrunners

In problem $$$E2$$$ why $$$k$$$ may be larger than $$$n$$$ !?

I wasted 15 minutes because of that (I assumed that $$$k≤n$$$), and I'm sure many people failed because of that case.

Nice problems like always. orz ITMO University team

1. bad testcases of problem A.
2. see my this solution is 195584757 wrong for mmeo but it's still accepted

Nice round with a variety of themes!

how can i optimized this solution for problem E1 https://codeforces.me/contest/1800/submission/195690945 I have used brute force approach to check

here answer me how WE COULD SOLVE THE PROBLEM C WITH NOT KNOWING THE QUEUE

Can Someone Please Point Out Why My Code Fails For F?

195704952

My casework solution for E1 lol, it actually helped me realize the general solution for E2 and only needed a few tweaks.

void solve(){
    int n, k;
    cin >> n >> k;
    string a, b;
    cin >> a >> b;
    string x = a, y = b;
    sort(x.begin(), x.end());
    sort(y.begin(), y.end());
    if(x != y){
        cout << "NO" << endl;
        return;
    }
    if(a == b){
        cout << "YES" << endl;
        return;
    }
    if(a.length() >= 6){
        cout << "YES" << endl;
        return;
    }
    if(a.length() <= 3){
        cout << "NO" << endl;
        return;
    }
    if(a.length() == 4){
        swap(a[0], a[3]);
        if(a == b) cout << "YES" << endl;
        else cout << "NO" << endl;
        return;
    }
    if(a.length() == 5){
        if(a[2] == b[2]) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

As a tester, I was late xD

A: Implementaion.

B: For each pair of lowercase and uppercase we count their occurence, let they be cnt1 and cnt2, then it contribute min(cnt1, cnt2) to the answer we can get initially, and abs(cnt1-cnt2)/2 to the answer we can get by operation, so the answer is sum(min(cnt1, cnt2)) + min(k, sum(abs(cnt1-cnt2)/2)).

C: We can maintain a priority queue. We scan the array from left to right, when s[i]>0 we push it into the priority queue, and pop an element and add it to the answer when some s[i]=0.

D: Let f(i) be the string after removing s[i] and s[i+1], then f(i)==f(j) (i<j) is equivalent to s[t]==s[t+2] for all t in range [i, j-1]. Therefore, let the initial answer be n-1, and each t that s[t]==s[t+2] will contribute -1 to the answer.

E: First check the trivial case when s and t are different after sorted. For a pair of (s[i], s[i+1]), if i>=k, we can swap them by:

(s[0], ..., s[i-k], ..., s[i], s[i+1], ..., s[n-1]) --> swap (i-k, i) -->

(s[0], ..., s[i], ..., s[i-k], s[i+1], ..., s[n-1]) --> swap(i-k, i+1) -->

(s[0], ..., s[i+1], ..., s[i-k], s[i], ..., s[n-1]) --> swap(i-k, i) -->

(s[0], ..., s[i-k], ..., s[i+1], s[i], ..., s[n-1])

Similar for i+1+k<n. So if every pair of chars can be swaped like this, which means n>=2*k+1, we can re-arrange the string arbitrarily. If n=2*k, we can swap (s[k-1], s[k]) like this:

(s[0], ..., s[k-1], s[k], ..., s[2*k-1]) --> swap(0, k) -->

(s[k], ..., s[k-1], s[0], ..., s[2*k-1]) --> swap(0, k-1) (we can re-arrange [0, k-1] arbitrarily since we can swap every pair in this range) -->

(s[k-1], ..., s[k], s[0], ..., s[2*k-1]) --> swap(0, k) -->

(s[0], ..., s[k], s[k-1], ..., s[2*k-1])

Finally, if n<2*k, there are some chars in the middle can't be moved, but we can re-arrange every movable chars like steps above. So we need to check every unmovable positions of s and t.

F: Bitmask. Let mask1(s)= the letters occurs odd times in s, mask2(s)= the letters occurs any times in s. Then (s, t) is a good pair is equvalent to popcount(mask)==25 && mask&mask2(s)==mask2(s) && mask&mask2(t)==mask2(t), where mask=mask1(s)^mask1(t). Therefore we can calculate the contribution of every mask[i]=(1<<26)-1-(1<<i) for i in range [0, 25] using a map.

G: Tree hashing. If the root has even number of childs, the hashcode of subtrees of these child must appear in pairs, and if the root has odd number of childs, there must exist a child with symmetric subtree, and the hashcode of other subtrees appear in pairs.