FAKEHASH - Faketorial Hashing
First, let’s define a function, ord(ch) = the position of ch in the alphabet + 1, where ch can be any lowercase letter. So, ord(a) = 2, ord(b) = 3, ord(c) = 4, … ord(z) = 27.
Let fact(x) be x! or the factorial of x. A few examples, fact(1) = 1, fact(2) = 2, fact(3) = 6, fact(4) = 24, fact(5) = 120, etc. Given a string S of length N, consisting of lowercase letters only, the Faketorial Hashing of S, is defined as below:
fake_hash(S) = fact(ord(S)) × fact(ord(S)) × fact(ord(S)) × …… × fact(ord(S[N - 1]))
In other words, it is the product of the factorial of the ord() value of all the characters in S (That’s right, no modulus! Unlike the lame polynomial hashing). Not only that we have a new hashing mechanism in place, but we would also like to crack this now. Given a string S1 consisting of lowercase letters only, your task is to find a different string S2 consisting of lowercase letters, such that, fake_hash(S1) = fake_hash(S2) and S1 ≠ S2.
If there are multiple possible choices for S2, you need to find the lexicographically smallest one, or output the word “Impossible” without quotes, if it is not possible to find such a string.
InputThe first line contains an integer T, denoting the number of test cases. Each test case contains the string S1 consisting of lowercase letters (a-z) only.
Except for the sample, the following constraints will hold:
OutputFor each test case, output the case number followed by the required output. Please refer to the sample input/output section for the precise format.
Input: 10 tourist petr mnbvmar bmerry xellos sevenkplus dragoon zzz snapdragon zosovoghisktwnopqrstuvwxyzoos Output: Case 1: aaaaabbdnstttu Case 2: aqst Case 3: abmmnrv Case 4: aaabbnrry Case 5: aaaaaaadddlnuz Case 6: aaaaaaabbddddnquuuz Case 7: aaaaaaaaaaaaabdnnnt Case 8: Impossible Case 9: aaaaaaaaaabdnnnpst Case 10: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaffffjnnnnqqttttuuuuxxzzzzzz
Is it doable with Naive Backtracking? I need help.
For some reason the answer checker keeps running for days (or so it seems) without coming with a verdict.