Sometimes the Codeforces community is crazy. Why is this normal comment being downvoted so many times? Can we stop this kind of "insane downvoting"?

NO way . Only solving 1 / 2 question can't make you green

I tend to do worse on educational rounds for some reason, probably because I have trouble with 'classical' problems. I think edu is very high quality, and I'm impressed how many good problems they can come up with in such a short time frame.

+1

Yeah! ...Editorial will be released after the end of contest where you can find the solutions to all the problems!

Is this a joke or what

Thats intended :)

US :)

I got C Idea in 30 minutes, then I spent 1:15 hours thinking of D but In vain.

Could you give me a hint?

C is not annoying if solve it the right way:

1) Initially drop all 'b' from both strings – if resulting strings are not equal then answer is NO.

2) In initial strings find all occurrences of 'a' – k-th occurrence in first string should be less or equal to k-th occurrence of 'a' in second string. And similar to 'c' but it should be more or equal.

Because it's ICPC mode

First, remove all occurrence of '$$$b$$$' and check if they are same. Second, find each occurrence of each non-'$$$b$$$' character in both $$$s$$$ and $$$t$$$. If it is a '$$$a$$$', it must appear in $$$s$$$ no later than in $$$t$$$. If it is a '$$$c$$$', it must appear in $$$s$$$ no earlier than in $$$t$$$.

It's more of a proof problem. I'm not sure tho.

There seem to be more solutions to C. I'll explain mine.

First, we need to make a few observations:

1. both strings s and t should have equal amounts of 'a', 'b', and 'c'
2. 'c' cannot be moved towards right in string s (So, each 'c' in s should be present towards the right of its counterpart in string t)
3. 'a' cannot be moved towards left in string s (So, each 'a' in s should be present towards the left of its counterpart in string t) by doing the given operations.

Let's start with the observation#2:

To move a 'c' towards the left from index i to j(j < i), the range [j, i-1] should have all 'b's. Try moving each 'c' in s to its correct position in t. If we cannot move a 'c', we cannot convert s to t.

Now, all 'c's should be in their correct positions(if possible)

Similarly, with the observation#3:

To move a 'a' towards the right from index j to i(j < i), the range [j+1, i] should have all 'c's. Try moving each 'a' in s to its correct position in t. If we cannot move a 'a', we cannot convert s to t.

Now all 'a's should be in their correct positions(if possible)

Since all 'a's and 'c's are in their correct positions, now we just need to check if all b's are there in their correct positions and determine the answer.

Implementation:

To check if a range contains all b's and make point updates while moving a character from one index i to j(the move is a direct swap of s[i] and s[j] and not actual swaps between adjacent characters to reach the destination), we can use Segment Tree with range query and point updates.

hope my implementation using stack give you some hint :-160349549

Double binary search. First binary search to find the point where a new alphabet first shows up in the string (counting from the left), and then, we iterate through the string from left to right. For each character of the string, we save the last occurrence of the letter, and to determine the unknown character, we do a binary search on the array of indexes of last occurrences to find the index at which the unknown character does not contribute to the number of distinct characters. This should yield a $$$O(26logn+nlog26)$$$

We are going to use binary search.

Imagine you are trying to figure out index ith, and imagine you already know all characters from 0th to (i — 1)th.

you can add all the right most index of each character that you have found in an index array, this index size is at most 26. You are going to binary search on this index.

let say you are considering index jth before ith. if from j to i — 1, the index at i already appears, then you have the same count from j to i — 1, and j to i, bc ith doesnt add anything new. So you can binary search the right most position where this is true, then you can find an index j that is the same with i. so each binary search check, you can check the count from mid to i — 1 and mid to i, mid to i — 1 can be updated after every ith, so it's free. If you can't find this then you can use the first query.

the total used is at max 6 * 10, you only use 5 times in the binary search, at only use the first type when there's a new character.

Shortly, you restore the characters of s from left to right. The first character is restored by query "? 1 1". For each of the next characters, let's ask if this character is new (by query "? 2 1 i"). If it's new, ask "? 1 i"; otherwise, find the previous occurrence of the i-th character with binary search.

To run only 5 queries of type 2 in binary search, you can see that we are interested in segments of type $$$[last_c, i]$$$, where $$$last_c$$$ is the last occurrence of some character on the prefix we know.

Keep track of known letters and their last positions. Build the string up from the front by querying the entire string up to that position to find out if its a new letter (if it is then use query type 1 to find out what it is) otherwise do a binary search with the array of last positions to work out which letter it is.

will you please tell me why this code fails? 160354394

How to solve E?

F is two sat . You can make some variable : (a[i]<=x) is true or false , (a[i]>=x) is true or false.

What's the observation for D ?

A and B make this round somehow "speedforces". But D has a clean solution and I think it's a good problem. I have no idea whether C has a clean (and PROVED) solution because my solution for C was terrible.

That is true, the total number of 2 Query will be less than log(26)*1000, Do you search the last 26 characters[a-z] instead of all the previous characters?