Shuffled Anagrams solution | Round E 2021 – Kick Start 2021

Shuffled Anagrams solution

Problem

Let SS be a string containing only letters of the English alphabet. An anagram of SS is any string that contains exactly the same letters as SS (with the same number of occurrences for each letter), but in a different order. For example, the word kick has anagrams such as kcik and ckki.

Now, let S[i]S[i] be the ii-th letter in SS. We say that an anagram of SS, A, is shuffled if and only if for all iiS[i]A[i]S[i]≠A[i]. So, for instance, kcik is not a shuffled anagram of kick as the first and fourth letters of both of them are the same. However, ckki would be considered a shuffled anagram of kick, as would ikkc.

Given an arbitrary string SS, your task is to output any one shuffled anagram of SS, or else print IMPOSSIBLE if this cannot be done.

Input

The first line of the input gives the number of test cases, TTTT test cases follow. Each test case consists of one line, a string of English letters.

Output

For each test case, output one line containing Case #xxyy, where xx is the test case number (starting from 1) and yy is a shuffled anagram of the string for that test case, or IMPOSSIBLE if no shuffled anagram exists for that string.

Limits

Memory limit: 1 GB.
1T1001≤T≤100.
All input letters are lowercase English letters.

Test Set 1

Time limit: 20 seconds.
11≤ the length of SS 8≤8.

Test Set 2

Time limit: 40 seconds.
11≤ the length of SS 104≤104.

Sample

Sample Input
2
start
jjj
Sample Output
Case #1: tarts
Case #2: IMPOSSIBLE

In test case #1, tarts is a shuffled anagram of start as none of the letters in each position of both strings match the other. Another possible solution is trsta (though you only need to provide one solution). However, in test case #2, there is no way of anagramming jjj to form a shuffled anagram, so IMPOSSIBLE is printed instead.


Analysis

Test set 1

For this test set, since the length of SS 8≤8, we can try every permutation of characters and check whether there exists a permutation such that for all iiS[i]A[i]S[i]≠A[i]. To find every permutation, we can first convert the string to a character array. Then, we swap the first element with every other element and recursively find permutations of the rest of the string.

This can be performed in O(N!)O(N!), where NN is the length of SS.

Test set 2

For this test set, the above solution would exceed the time limits.

The key observation here is that if a character exists more than N2⌊N2⌋ times, then it’s impossible to find such a permutation, because at least one position will have a letter that stays the same. Otherwise, we can sort the letters and keep track of the initial position of each letter.

Let the new sorted letters be PP. We can split the sorted letters into two halves, from index 00 to N2N2P[0:N2]P[0:N2], and from N2N2 to the end, P[N2:]P[N2:]. If NN is odd, split PP such that the second half has an extra letter, where the first half is 00 to N2⌊N2⌋ and the second half is from N2⌈N2⌉ to the end. Then, we put each character from the second half of the sorted letters P[i+(N2)]P[i+(N2)] into the original position of the corresponding letter in the first half P[i]P[i].

Similarly, we put each character from the first half of the sorted letters P[i]P[i] into the original position of the corresponding letter in the second half P[i+(N2)]P[i+(N2)]. Note that if NN is odd, the second half of the sorted letters P[i+(N2)]P[i+(N2)] will occupy the first N2+1⌊N2⌋+1 spaces, while the original first half will occupy the last N2⌊N2⌋ spaces, as shown in the example below. The letter orginally at P[N1]P[N−1] will be in the middle of the array after the swap, replacing P[i+N2]P[i+⌊N2⌋].

Shuffled Anagrams solution

This works because we know that no more than half the characters are equal, and hence the character at P[i]P[i] cannot be equal to the letter at P[i+(N2)]P[i+(N2)].

This can be performed in O(NlogN)O(Nlog⁡N), due to sorting. However, due to the limited size of the alphabet, we can actually sort even faster using a non-comparative sorting algorithm such as counting sort.

Shuffled Anagrams solution | Round E 2021 – Kick Start 2021


Solution – JAVA

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

// Solution
public class Solution {
static InputStream is;
static PrintWriter out;
static String INPUT = "";

static void solve()
{
for(int T = ni(), cas = 1;T > 0;T--,cas++){
out.print("Case #" + cas + ": ");
go();
}
}

static void go()
{
String s = ns();
char[] t = s.toCharArray();
int n = t.length;
int[][] ai = new int[n][];
for(int i = 0;i < n;i++){
ai[i] = new int[]{t[i], i};
}
Arrays.sort(ai, (x, y) -> {
if (x[0] != y[0]) return x[0] - y[0];
return (x[1] - y[1]);
});
char[] u = new char[n];
for(int i = 0;i < n;i++){
u[ai[(i+n/2) %n][1]] = (char)ai[i][0];
}

for(int i = 0;i < n;i++){
if(t[i] == u[i]){
out.println("IMPOSSIBLE");
return;
}
}
out.println(new String(u));
}

public static void main(String[] args) throws Exception
{
long S = System.currentTimeMillis();
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);

solve();
out.flush();
long G = System.currentTimeMillis();
tr(G-S+"ms");
}

private static boolean eof()
{
if(lenbuf == -1)return true;
int lptr = ptrbuf;
while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false;

try {
is.mark(1000);
while(true){
int b = is.read();
if(b == -1){
is.reset();
return true;
}else if(!isSpaceChar(b)){
is.reset();
return false;
}
}
} catch (IOException e) {
return true;
}
}

private static byte[] inbuf = new byte[1024];
static int lenbuf = 0, ptrbuf = 0;

private static int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}

private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
// private static boolean isSpaceChar(int c) { return !(c >= 32 && c <= 126); }
private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }

private static double nd() { return Double.parseDouble(ns()); }
private static char nc() { return (char)skip(); }

private static String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}

private static char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}

private static char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}

private static int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}

private static int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}

while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}

private static long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}

while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}

private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}

Shuffled Anagrams solution | Round E 2021 - Kick Start 2021

Palindromic Hamiltonian Path solution codeforcesPalindromic Hamiltonian Path solution codeforcesPalindromic Hamiltonian Path solution codeforces
Also read : Airline Restrictions codechef solution
Also read : Shuffled Anagrams solution | Round E 2021 - Kick Start 2021
Also read : Birthday Cake solution | Round E 2021 - Kick Start 2021

No Comments, Be The First!

Your email address will not be published.