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 :)

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?

Never downvote a post due to the reason "there are already many downvotes and I would like to add more". If you downvote a post you should really have a "good reason" otherwise it's only making this community crazy and unfriendly.

too many queries leads to wa

I guess no, as the query limit is an obvious indication to do a binary search.

Probably due to slow I/O in python. It's better to load / write data at once.

Just wait until the announcement post gets updated. It should have a hyperlink "Editorial" by then.

I've replaced Arrays.sort with counting sort.

You can also use boxing from int to Integer, 'cause objects (of class Integer, for example) are sorting with MergeSort (worst time NlogN), but primitives are sorting with QuickSort (medium time is better, but worst time is N^2).

public static void sort(int[] a) {
    int n = a.length;
    Integer[] arr = new Integer[n];
    for(int i = 0; i < n; i++) arr[i] = a[i]; //copy int array to Integer array
    Arrays.sort(arr); //sort Integer array
    for(int i = 0; i < n; i++) a[i] = arr[i]; //copy Integer sorted array to int array
    //worst time is NlogN
}

With 27000, you don't need binary search at all.

(misunderstood the point, so deleted)

Think of it this way: you pay for the x most expensive items first, and then because of the offer, the store refunds you for the first y cheapest items of your purchase. because x = y, so you don't need to spend a penny after the refund.

Kind of easier C implementation

int cnt[3][2]{};
for (int i = 0; i < n; ++i)     ++cnt[s[i] - 'a'][0];
for (int i = 0; i < n; ++i)    ++cnt[t[i] - 'a'][1];

for (int i = 0; i < 3; ++i)    if (cnt[i][0] != cnt[i][1]) return no();

fill_n(&cnt[0][0], 6, 0);

for (int i = 0; i < n; ++i) {

    cnt[s[i] - 'a'][0] ++;
    cnt[t[i] - 'a'][1] ++;

    if (s[i] == 'c' and cnt[0][0] != cnt[0][1]) return no();
    if (s[i] == 'a' and cnt[2][0] != cnt[2][1]) return no();
    if (cnt[0][0] < cnt[0][1]) return no();
    if (cnt[2][0] > cnt[2][1]) return no();
    if (cnt[2][0] < cnt[2][1] and cnt[1][0] <= cnt[1][1]) return no();
}

yes();

I did not read your code but did the same. When you move 'c' don't forget to do the swap. Example : 4 abbc bcab My code https://codeforces.me/contest/1697/submission/160335317

same, make the round unrated

This is how interactive problems work — not only on CF, but in official ICPC contests as well. There is no separate verdict for exceeding the number of queries (what should it be? RE, TL, something new?), so the WA verdict is used for it almost everywhere.

Note that the phrasing in the problem is "you MAY receive some other verdict", not "you WILL receive". This is due to the fact that, in interactive problems, two separate programs are used to judge your submission, and in some occasions, their verdicts can be different (for example, the interactor says that you should get WA for sending too many queries, but then your solution crashes or spends too much time, so it's eligible for WA/RE/TL). That's why you should terminate your program immediately after receiving the response "your query is incorrect", which you don't do.

I didn't see you check 0 as return value, so the verdict will be WA.

yes exactly this statement is the reason why I spent ~1.5 hrs thinking that either my logic or my implementation was wrong. It literally says that you will get "Some other verdict instead of Wrong answer"