MY02 - Play with Strings

no tags 

All you have to do is implement the following algorithm, which is a very popular compression technique.

  1. You are given an input string A. (For example ababc)
  2. Find all the rotations of A (In this case, they are ababc, babca, abcab, bcaba, cabab)
  3. Now sort them (After sorting, we have ababc, abcab, babca, bcaba, cabab)
  4. Then arrange them as follows:
    • ababc
    • abcab
    • babca
    • bcaba
    • cabab
  5. Now pick out the last column. It is ‘cbaab’. This is the result of this algorithm.
  6. Also observe that the 1st row has the original string. (Use 1 indexing)

Now, for this problem, you are given the output and the row number that has the original string. For the above example, it is ‘cbaab’ and 1.

Given these 2 parameters, you just need to decode it. (i.e. find the original string.)

Input:

Each test case has 2 lines.

1st line – An integer R that represents the row that contains the original string.

2nd line - A string that represents the output of the above algorithm. (Length of string <=2000) (All characters are lower case).

The input is terminated with R=-1.

Output:

The original string.

Sample

Input
1
cbaab
3
mnoag
-1

Output
ababc
mango

hide comments
cegprakash: 2019-05-09 20:21:11

How many test cases? n^2 log n times out

Last edit: 2019-05-09 20:59:47
topke: 2016-02-06 14:47:01

@n.7n: Is R always <= 2000 and the is that also correct for string? Im getting bunch of SIGSEGV and i don't whats wrong, can you take a look?
Yea nothing seems to be working out more SIGSEGV idk why

Last edit: 2016-02-06 14:58:49
Krishna Nakkeeran: 2014-02-22 15:16:36

My 75th in spoj.....

n.7n: 2014-02-22 15:16:36

Re :D Agreed . And thanks for your observation :)

Last edit: 2013-11-13 15:29:11
:D: 2014-02-22 15:16:36

Re: abdou 00
I think you can assume test data describes valid encodings.

Re: narayanan
I'm with Alex on this one. I don't really care what wiki says. It's exactly 0% compression ratio every time. It's encoding (very weak) not compression.

Problems itself is very good though.

abdou_93: 2014-02-22 15:16:36

@~ .. this is valid case
1
abcd
?

n.7n: 2014-02-22 15:16:36

@Alex Anderson: U shall refer the wiki link.

Last edit: 2013-10-22 20:57:22
Alex Anderson: 2014-02-22 15:16:36

Hmm, well, I wouldn't call this compression.

Last edit: 2013-10-22 20:56:29

Added by:n.7n
Date:2013-10-11
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Wikipedia