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

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 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://mirror.codeforces.com/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.

First time to solve all the problems in Div.3 ^_^

(But without coding)

Talk is cheap.jpg

Finally solve till E2 :) .... Dream comes true lmao

I think this round's problems where a little too easy for div 3 lol, but I love it. I think I'm hitting Specialist for the first time after this round too, so that's great

Thanks for strong E2 pretests! WA on test 20 was really helpful

D is very cute!
G: About rooted tree hashing

This contest was easy.

Solution to E without any implementations

1. We have to make $$$s$$$ equal to $$$t$$$. Let's use Meet-in-the-middle
2. Let's make $$$s$$$ and $$$t$$$ minimum lexicographical as possible. If after that $$$s=t$$$ answer is YES and NO otherwise.

[solution]

I solved C1 with DP and I couldn't convince myself how PQ works on this problem. Take the case:

5

5 4 2 0 0

I see why it works now because we only have to return count but technically what happens if you simulated is that the first hero picks card 0 and the last two cards are discarded. I think if you had to return the cards that each hero picked in the answer, PQ wouldn't work right?

E can also be solved with DSU. It can be done by merging all positions with distances k and k + 1 between them and checking for each connectivity component if set of letters on corresponding positions in s and t are the same: 195646722

Good contest! A-F were smooth :)

Although I was able to solve A-F however I'm still trying to wrap around the fact that why would initialising the unordered_map elements make a difference.

This works -https://mirror.codeforces.com/contest/1800/submission/195719096

This fails — https://mirror.codeforces.com/contest/1800/submission/195719053

The only difference b/w the 2 being that in the working code I have initialised all characters to 0. Aren't unordered_map elements given a default value 0 when not present? I also tried explicitly checking for the members but no luck!

I would be grateful and really appreciate if someone could help me with this.

Thanks in advance :)

What's the proof of C?

Can anyone explain why this approach works for D? I did testing on random strings in compare with brute force solution and could not find test that would break the solution.

int ans = 0;
pair<char, char> last;
for (int i = 0; i < s.size() - 1; ++i) {
    pair<char, char> cur = { s[i], s[i + 1] };
    if (cur.first > cur.second)
        swap(cur.first, cur.second);
    if (cur != last)
        ++ans;
    last = cur;
}

1592B - Хемосе в магазинах Similar to E1 and E2 But I did not solve them, although I solved this problem more than a year ago

Isn't G a little bit easy for its position?

1592B - Hemose Shopping

Similar to E1 and E2 But I did not solve them, although I solved this problem more than a year ago

Antihash tests? My solutions with unordered_map/cc_hash_table passed (task G), but gp_hash_table got TL on testcase3. And after making my own hash all is OK. UPD after systests. cc_hash_table gave TL. But unordered_map is fine

SO HAPPY !! Got a sub 1k rank for the first time ! Loved the questions

flunked very hard on E1 and E2, stuck for over 1.5 hours and could not solve them..

Forgot to use long long for answer in C1 and C2, and I kept thinking I was using the wrong approach, so I couldn't solve either of them. Gonna fall to newbie now :(

Regarding problem F, the time constraint for this problem is pretty tight,and the judge's behaviour is hence arbitrary. Check these submissions,195747465 and 195747315. I have submitted the exact same code twice, getting accepted verdict in one submission. Could someone suggest a faster algo, and hack this solution if this is'nt the intended one.

UPD: made it faster using hashing, fits well into the time limit now.

So interesting the problems are in this contest,I love this contest!but I think pretest in A maybe weak.

why my solution for problem A got hacked? qwq

For F task I got AC in java but getting wrong answer when i convert in to C++. Please help, i am new to C++

AC 195755004

WA 195754099

in problem A , bad tests -_-