PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iiii63027
Tester & Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
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.
EXPLANATION:
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.
TIME COMPLEXITY
\mathcal{O}(1) per testcase.
CODE:
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;
return;
}
int countF = 0;
for (char it : s)
{
countF += (it == 'e');
}
if (countF >= 7)
{
cout << -1 << nl;
return;
}
int countC = 0;
for (char it : s)
{
countC += (it == 'c');
}
if (countC >= 7)
{
cout << -1 << nl;
return;
}
// 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)
continue;
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]);
else
break;
}
}
cout << s << nl;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
solve();
}
}
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:
print(cache[ss])
continue
cache[ss] = -1
itr = 0
while itr < 300:
itr += 1
shuffle(s)
cur = ''.join(s)
good = True
for i in range(8): good &= cur[i] != codechef[i]
if good == True:
cache[ss] = cur
break
print(cache[ss])