PDECODE - Decode the Strings
Bruce Force has had an interesting idea how to encode strings. The following is the description of how the encoding is done:
Let x1, x2 ... xn be the sequence of characters of the string to be encoded.
- Choose an integer m and n pairwise distinct numbers p1,p2 ... pn from the set {1, 2 ... n} (a permutation of the numbers 1 to n).
- Repeat the following step m times.
- For 1 ≤ i ≤ n set yi to xpi, and then for 1 ≤ i ≤ n replace xi by yi.
For example, when we want to encode the string "hello", and we choose the value m = 3 and the permutation 2, 3, 1, 5, 4, the data would be encoded in 3 steps: "hello" → "elhol" → "lhelo" → "helol".
Bruce gives you the encoded strings, and the numbers m and p1 ... pn used to encode these strings. He claims that because he used huge numbers m for encoding, you will need a lot of time to decode the strings. Can you disprove this claim by quickly decoding the strings?
Input
The input contains several test cases. Each test case starts with a line containing two numbers n and m (1 ≤ n ≤ 80, 1 ≤ m ≤ 109). The following line consists of n pairwise different numbers p1 ... pn (1 ≤ pi ≤ n). The third line of each test case consists of exactly n characters, and represent the encoded string. The last test case is followed by a line containing two zeros.
Output
For each test case, print one line with the decoded string.
Example
Input: 5 3 2 3 1 5 4 helol 16 804289384 13 10 2 7 8 1 16 12 15 6 5 14 3 4 11 9 scssoet tcaede n 8 12 5 3 4 2 1 8 6 7 encoded? 0 0 Output: hello second test case encoded?
hide comments
madhur4127:
2018-03-19 10:55:07
no inversion, just permutation matrix and hardest part was to input string with whitespace. cin.ignore() did the job. |
|
Deepak Gupta:
2014-10-11 14:00:43
Use gets() twice to read string, to avoid new line issues |
|
Somnath Singh :D:
2011-08-31 14:46:33
Contruct the Symmetry group , tht's will give u the idea to do ... with O(nlog) .
|
|
Adrian Kuegel:
2010-08-17 09:21:39
I think your algorithm is O(m * n), which is of course too slow. It is possible to solve this problem in O(n) or in O(n log m). |
|
Adrian Kuegel:
2010-04-16 08:56:52
no |
|
nishaanth:
2010-04-10 15:46:37
has it to do with number of inversions?? |
Added by: | Adrian Kuegel |
Date: | 2008-07-12 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | University of Ulm Local Contest 2008 |