CC_COPY - Editorial


Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iiii63027
Tester & Editorialist: iceknight1093






You’re given a string S. Find an anagram of it that doesn’t match the string "codechef" at any position, or report that no such anagram exists.


Let’s look at a couple of simple cases first:

  • If S contains only a single character (like "cccccccc"), and that character is one of \{\texttt{c, d, e, f, h, o} \} then of course no valid anagram exists.
  • If S contains 7 occurrences of either ‘c’ or ‘e’, no valid anagram exists; because "codechef"contains two of each of them.

In fact, in all other cases, a valid anagram exists.

There are several ways to find an answer, here are a couple.

Author's solution

There’s a fairly simple ad-hoc solution to this problem.
Let’s call index i bad if S_i matches the i-th character of "codechef", and good otherwise.

Repeat the following process:

  • If S is valid, nothing needs to be done: just print it.
  • Otherwise, find a bad index i.
    We need to move S_i somewhere else.
  • Finding where to move it can be done with brute force!
    That is, there will always exist an index j such that swapping S_i and S_j will leave both indices good (do you see why?)
    Find such a j by iterating across all indices, and swap S_i with S_j.

In each step we reduce the number of bad indices by at least one, so within 8 steps we’ll have an answer.

Editorialist's solution

We can use randomization!

That is, repeat the following process till you find a solution:

  • Randomly shuffle the characters of S
  • Check if it satisfies the condition; if it does, stop and print it

It can be shown that even in the worst case, a random shuffle has a \geq \frac{1}{28} chance of being valid.
By repeating this process 300 times, the probability that we fail every single one of those trials is vanishingly small.

In order to not TLE with this approach, you’ll have to cache results - that is, if you’ve found an answer for S previously, simply save it and print it, instead of repeating the randomization process. See the editorialist’s code for an implementation.


\mathcal{O}(1) per testcase.


Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
string codechef = "codechef";
unordered_set<char> bad = {'c', 'o', 'd', 'e', 'h', 'f'};
int violating(string &s)
    for (int i = 0; i < 8; i++)
        if (s[i] == codechef[i])
            return i;
    return -1;
void solve()
    string s;
    cin >> s;
    sort(s.begin(), s.end());
    // Only 3 cases where answer is not possible.
    if (s[0] == s.back() && bad.count(s[0]))
        cout << -1 << nl;
    int countF = 0;
    for (char it : s)
        countF += (it == 'e');
    if (countF >= 7)
        cout << -1 << nl;
    int countC = 0;
    for (char it : s)
        countC += (it == 'c');
    if (countC >= 7)
        cout << -1 << nl;
    // Find the violating index and swap it.
    int violating_index = 0;
    while ((violating_index = violating(s)) >= 0)
        for (int i = 0; i < 8; i++)
            if (i == violating_index)
            swap(s[i], s[violating_index]);
            // If this index can not correct
            if (s[i] == codechef[i] || s[violating_index] == codechef[violating_index])
                swap(s[i], s[violating_index]);
    cout << s << nl;
signed main()
    int t;
    cin >> t;
    while (t--)
Editorialist's code (Python)
codechef = 'codechef'
from random import shuffle
cache = {}
for _ in range(int(input())):
    s = sorted(list(input()))
    ss = ''.join(s)
    if ss in cache:
    cache[ss] = -1
    itr = 0
    while itr < 300:
        itr += 1
        cur = ''.join(s)
        good = True
        for i in range(8): good &= cur[i] != codechef[i]
        if good == True:
            cache[ss] = cur

What about string eccceccc
The anagram of this string which satisfies the codechef position doesn’t exist
Or the eccceccc is the anagram of eccceccc

I don’t understand one thing if someone could explain. According to the requirements, aaaaaaaa should be an approved input which is printed as it is for obvious reasons. Yet when I tried to submit my same contest code in practice, it showed that this test case failed even though my outputs was aaaaaaaa. Why was that so??

1 Like

I might be wrong but it seems to me that eccceccc does actually satisfy the given condition!

c ≠ e
o ≠ c
d ≠ c
e ≠ c
c ≠ e
h ≠ c
e ≠ c
f ≠ c