BledDest has made the task "awoo's favorite problem" :| kinda weired.

It shows tutorial is not available excluding problem A.

Could any tell me why my approach to solving C is giving WA? https://codeforces.net/contest/1697/submission/160346935

My approach:

=> 1. Because we don't have ac or ca operations.

    if((s[i]=='a' && t[i]=='c') || (s[i]=='c' && t[i]=='a')) return "NO\n";

=> 2. Make s[i]=='b' and t[i]=='c' to s[i]='c' and t[i]='c' using bc operation via two pointer approach

    int l=0, r=-1;
    for(l=0;l<n;l++){
      if(s[l]=='b' && t[l]=='c'){
        r=Math.max(l, r);
        while(r<n && s[r]=='b') r++;
        if(r==n) return "NO\n";
        if(s[r]!='c') return "NO\n";
        s[l]='c';
        s[r]='b';
        r++;
      }
    }

=> 3. Finally you can remove characters which are equal i.e; s[i]==t[i] At this moment, we have all c's matched in both s and t Now we can match a's and b's using ab operation

    r=-1;
    for(l=0;l<n;l++){
      if(s[l]==t[l]) continue;
      if(s[l]=='c' || t[l]=='c') return "NO\n";
      if(s[l]=='b') return "NO\n";
      r=Math.max(r, l);
      while(r<n && s[r]=='a') r++;
      if(r==n) return "NO\n";
      if(s[r]=='a') return "NO\n";
      s[l]='b';
      s[r]='a';
      r++;
    }

Is this code correct? Gives AC but just because of a single else break; it got hacked during contest. My rank went down from 2000 to 8k+. Had solved C in 14 mins. This shit hurts! Just missed a single else statement. 160439872

can anyone please explain problem C ?

F's idea was brilliant. It's not hard to recognize it as a 2-sat problem, but I got stuck with "is $$$a_i$$$ equal to $$$x$$$?" and can't come up with the idea presented in the solution.

Great problems overall. Thanks sir.

In the ask_character function, can we not directly input a char instead of inputting a string and then returning its first charachter? Asking cause I seen a string being inputted in someone else's submission too

Can someone tell me how test #3 in problem B is generated? All other tests are fine, but test #3 alone seems to be quite an adversary to the dual-pivot quicksort which is used for the built-in primitive array sorting in java. What's more curious is that the built-in sorting algorithm switches to heap sort if it is too slow. I also tried to make a bad array for a bit via local machine and custom invocation, but it wasn't successful at all.

for problem E Im using this fact that size of each component is at most 4 and use this to solve problem with another way

One can prove or disprove this؟؟

C is a very strange problem. Let me describe my method.

We can replace "ab" with "ba", and replace "bc" with "cb". Firstly, the number of 'a', 'b' and 'c' must be equal in string $$$s$$$ and $$$t$$$. And if we remove 'b' from $$$s$$$ and $$$t$$$, the remaining string $$$s'$$$ and $$$t'$$$ should also be the same. This is because we can't change the relative positions of 'a' and 'c'.

So lets extract all 'b' in $$$s$$$ and $$$t$$$. They must match one by one like this:

• $$$s$$$: ___b_b______b_
• $$$t$$$: _b______b___b_

For a matched pair of 'b', where $$$s_i=t_j=$$$'b'.

• If $$$i=j$$$, then no operation is needed.
• If $$$i<j$$$, then we need to switch this 'b' in $$$s$$$ backward to position $$$j$$$, using operation "bc"->"cb". This means $$$s[i..j]$$$ must be either 'b' or 'c'.
• If $$$i>j$$$, then we need to switch this 'b' in $$$s$$$ forward to position $$$j$$$, using operation "ab"->"ba". This means $$$s[j..i]$$$ must be eigher 'a' or 'b'.

The check can be done using prefix sum.

I don't put that much time into doing Codeforces contests — I am not professionally involved with programming, it is more like a hobby for me. But anyhow, I had been initially very pleased (since I am only a Newbie) during the contest when I had my solutions to A, B and C accepted. But then, during the hacking period, my solution to B was hacked. So, I was curious about what mistake I made. And now that I see the "official" solution to B described as merely "sorting the array and doing prefix sums" — which is what I did — my guess (which seems consistent with other comments) is that apparently by using one of the standard python built-in sort functions ("sorted"), it led to my solution exceeding the time limit. If that is indeed truly what happened (and maybe it wasn't?), that seems to suggest a significant problem on the Codeforces end in setting the time limits.

I think my solution for E is simpler and more intuitive ( I think it might be because I observed that the maximum number of points colored the same is 4 ) I'll copy my comment from the other post (sorry if you read it there too ^_^):

"""

Just did problem E. Awesome problem!

First I noticed that the sizes of equal distance groups can only be 4 at most.

Then I noticed that you just need to keep a list of all points of minimum distance from you.

Then I noticed that the only way to color a few points the same color, is if they are all minimum distance from each other.

Then I noticed that a group (of min dist from each other) has to either be colored the same color, or all different, and this type of coloring is completely independent from the other choices for other groups.

From there it's straight forward, a dynamic programming depending on how many colors remain, and if you choose to color the group in the same color or all different colors (no other options). i.e. dp[number_of_group][colors_remaining][color_same_or_all_different]. dp size is n*n*2.

Don't yet know its rating, but might be the highest rated problem I solved!

"""

The way I found the groups is easy. After adding point X itself to the list of points with minimum distance from X (for convenience), to be part of a group, all the neighbors (with minimum distance) must have the exact same set of neighbors! if and only if one of them isn't — you are not part of a group. this was a simply O(n) for loop.

And this is not dfs as I'm only looking at neighbors!

def solution(a,n):
    p = NUMBER
    # Find list of minimum distance neighbors for each point.
    mins = []
    for i in range(n):
        mn = 10**9
        mins.append([])
        for j in range(n):
            if i == j:
                continue
            dist = distance(a[i], a[j])
            if dist < mn:
                mn = dist
                mins[-1] = [j]
            elif dist == mn:
                mins[-1].append(j)
        # Also add i to mins[i], so now mins[i] represents the possible group!
        mins[i].append(i)
    # sets is a list with same-colored-group SIZES, nothing else.
    sets = []
    visited = [0 for i in range(n)] 
    for i in range(n):
        if visited[i]:
            continue
        visited[i] = True
        # Check whether all the nighbors have the same neighbors (including themselves).
        s = set(mins[i])
        if not all(set(mins[j]) == s for j in mins[i]):
            # If not, this point must be alone, since it's close to someone who has someone closer.
            sets.append(1)
            continue
        # A group of equally min-distance points was found, add its size to "sets".
        sets.append(len(s))
        for j in mins[i]:
            visited[j] = True
    k = len(sets)
    # Just a random assert showing the size of a set is at most 4.
    assert all(x < 5 for x in sets)
    # Build factorials.
    facs = [1 for i in range(n+1)]
    for i in range(1,n+1):
        facs[i] = mult(facs[i-1], i)
    # Add 0 as first element for dp convenience.
    sets = [0] + sets
    # Initiate dp[index_of_group][number_of_colors_left][color_group_same_or_all_different]
    dp = [[[1 for _ in range(2)] for j in range(n+1)] for i in range(k+1)]
    for i in range(1,k+1):
        dp[i][0][0] = 0
        dp[i][0][1] = 0
    # It's important that lonely points (base empty case of 0 also applies) 
    # will have 0 in their [1] (because you cannot choose to "group" a lonely point, 
    # this causes wrong counting ).
    for j in range(n+1):
        dp[0][j][1] = 0

    for i in range(1,k+1):
        for n_cols in range(1,n+1):
            # Pick a color to color all same (since [1] means we group the group)/
            dp[i][n_cols][1] = mult(
                n_cols, 
                plus(
                    dp[i-1][n_cols-1][0],
                    dp[i-1][n_cols-1][1]
                )
            )
            if sets[i] == 1:
                # If lonely point then ignore above calculation.
                dp[i][n_cols][1] = 0
            if n_cols < sets[i]:
                # If not enough colors left than no way to color.
                dp[i][n_cols][0] = 0
                continue
            # Choose size_of_group colors from the available colors, and keep coloring the rest.
            dp[i][n_cols][0] = mult(
                choose_facs(n_cols, sets[i] ,facs),facs[sets[i]])
            dp[i][n_cols][0] = mult(
                dp[i][n_cols][0],plus(
                    dp[i-1][n_cols-sets[i]][0], 
                    dp[i-1][n_cols-sets[i]][1]
                )
            )
    return plus(dp[k][n][0], dp[k][n][1])

Thank you sigma problemsetters for pretests in E! I really love submitting, getting AC on the last 7 minuites, FSTing, fixing it with one if statement in 2 minutes 33 seconds! It is obvious to me that if a problem includes case analysis the pretests should exclude specifically one case so you feel like an idiot! ORZ ORZ ORZ problemsetters.

I liked the problem, it is just painful to perform like a 2520, getting +154, FSTing and realizing that if that was in the testcases, you had time to correct it.

Can anyone explain why I get TLE using Java in question B? https://codeforces.net/contest/1697/submission/160471991

Could Problem F be solved if k is 1e5?

why?????

Can anyone explain C i still don't get it

Here's an approach to problem C with O(n^2) (because the limit is 2 seconds). We will iterate i in the string from 0 to n — 1, if s[i] != t[i] then: *i = n — 1 or s[i] == 'c' or t[i] != s[i] + 1 (since to have 'ba', we need 'ab' and the same with 'cb) => NO *Next, we have j = i + 1, iterating to n — 1 and since we want to swap s[i] and s[j], j is the smallest that s[i] != s[j] *If j = n or s[j] != s[i] + 1 => NO *s[j] = s[i]

This is the code to know more what I'm saying: https://codeforces.net/contest/1697/submission/160477577

Cleaner implementation for problem d 160750718

For D if we binary search on [1, i - 1] (which is what I did during the contest) the number of type 2 queries has a loose upper bound of 1000*log(1000) which is roughly 10000. But the actual number is more like log_2(999)+log_2(998)+...+log_2(1) so I thought that might be under 6000, which was unfortunately wrong.

It's possible to get a very readable implementation for problem F with operator overloading.

For instance, we can make it possible to write ts.either(A[i] < x, A[i] > x) for queries of the 1st type.

A full solution (in Python) is available here: https://codeforces.net/contest/1697/submission/160806370

The trick also works in C++, as it supports operator overloading too.

for D Can we do like this we will ask 2nd query for every substring of length 2, so if we at 0th index and answer for this is 2 then we can say this s[0] and s[1] are different and we will ask first query for index 0 and 1, and if answer is 1 then we will ask first query for 0th index and s[1] will also be s[0] and if we are at ith index i > 0, and answer is 2 for 2nd query , then we will ask first query only for (i+1)th index as we have already know the char at ith index and if answer is 1, then simply s[i+1] = s[i] this way it will ask n-1 query of 2nd type and max 26 query for 1st type

and if this logic is right ,can anyone tell me where i am doing wrong in my implementation. if logic is not right , please tell me where i am thinking wrong in this logic.

My implementation

Your code here..
		#include <bits/stdc++.h>
		using namespace std;	
		#define ll long long
		ll Max = 4e4;
		ll mod = 1e9 + 7;
		int main() {
			// your code goes here
			ios_base::sync_with_stdio(false);
			cin.tie(NULL);
			cout.tie(NULL);
			#ifndef ONLINE_JUDGE
				freopen("input.txt", "r", stdin);
				freopen("output.txt", "w", stdout);
			#endif
			// fill();
			ll tc = 1;	
			// cin >> tc;
			while (tc--) {
				int n;
				cin >> n;
				vector<string>v(n, "#");
				vector<int>a(n-1);
				for (int i = 0; i < n-1; i++) {
					int l = i + 1, r = i + 2;
					cout << "? 2 " << l << " " << r << endl;
					cout.flush();
					cin >> a[i];
				}
				for (int i = 0; i < n-1; i++) {
					if (a[i] == 1) {
						if (v[i] == "#")
						{
							cout << "? 1 " << i+1 << endl;
							cout.flush();
							cin >> v[i+1];
							v[i] = v[i+1];

						}
						else v[i+1] = v[i];
					}
					else {
						if (v[i] == "#") {
							cout << "? 1 " << i << endl;
							cout.flush();
							cin >> v[i];
						}
						if (v[i+1] == "#") {
							cout << "? 1 " << i+1 << endl;
							cout.flush();
							cin >> v[i+1];
						}
					}
				}
				cout << "! ";
				for (auto &x : v) cout << x;
			}
		return 0;
	}
.

In problem E, one observation I could make is that ...
The clique size in a planar graph with equal distance (manhattan) can be atmost 4.
Only <= 4 vertices can be of the same color.
So maybe $$$O(n^4)$$$ .. or like exactly $$$O((n^4)/24)$$$ can pass.