PDECODE - Decode the Strings

no tags 

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.

  1. 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).
  2. Repeat the following step m times.
  3. 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?


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 ≤ pin). 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.


For each test case, print one line with the decoded string.


5 3
2 3 1 5 4
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
0 0

second test case

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


nishaanth: 2010-04-10 15:46:37

has it to do with number of inversions??

Added by:Adrian Kuegel
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