PERMTGEN - Permutation Generator

Hasan Jaddouh has invented a new algorithm for generating permutations this algorithm takes an array with length N as input and generate a permutation with length N from this array.

The array must satisfy (1 <= Ai <= i) in order for the resulting array to be a permutation. Here is the pseudo code of the algorithm:

read N
for i=1 to N do
    read A[i]
for i=1 to N do
    for j=1 to i-1 do
        if A[j] >= A[i] do
            A[j] = A[j]+1
for i=1 to N do
    print A[i]

but unfortunately for Hasan Jaddouh, his algorithm is too slow for big arrays so he asked you to help him to find a fast way to implement his algorithm.

your program should read input same as the pseudo code and output the new array.

Input

first line contains integer N (1 <= N <= 105).

second line contains N integers separated by spaces each integer is between 1 and 109 inclusive.

Note: in order for Hasan Jaddouh's algorithm to work and generate a permutation the constraint (1 <= Ai <= i) must be satisfied but to make this problem harder this constraint is not guaranteed so it's also not necessary that the output is a permutation.

Output

Output N integers separated by spaces, the new array after applying Hasan Jaddouh's algorithm.

Example

Input:
4
4 2 1 3

Output:
7 4 1 3

Added by:Hasan Jaddouh
Date:2013-05-06
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem

hide comments
2023-07-29 20:09:13 Oleg
Solution from https://www.spoj.com/problems/KHAOTMPL accepted without any changes.

Last edit: 2023-07-29 20:10:33
2013-05-13 03:09:15 Pushkar Mishra
Finally got the bug. My algorithm becomes n^2 for the worst case when all elements of the actual array are 1.
Thank you.

Last edit: 2013-05-13 03:19:00
2013-05-12 17:44:33 Pushkar Mishra
I am pretty sure my algorithm is nlogn for all inputs. How can I make output faster?
Thank you.

RE: it's not a matter of fast input/output method it's a matter of fast algorithm,

try this test case on your PC and see how much time your code takes:

100000
1 1 1 1 .... 1 1 1 1

Last edit: 2013-05-12 17:54:19
2013-05-12 15:19:30 Pushkar Mishra
@Author: It is a great question. I have almost got it correct. Can you please provide some tricky test cases. It will be of great help. you can email me as well: pushkar72@hotmail.com
Thank you.

RE: your code outputs strange characters, your problem is inside function "tostr"

By the way, after you fix your function tostr your code still TLE , are you sure you code guarantee O(log(n)) worst-case for each number?

my code O(N log N) worst-case and its total running time is 0.5s for all test cases

Last edit: 2013-05-12 17:14:13
2013-05-12 08:27:09 Pushkar Mishra
My program gives SIGSEGV error. My code runs fine on my machine and on several online compilers. Please check. Submission ID: 9246288
Thank you.

RE: try to run you code on MS C++ compiler, it will give you Runtime error.

or you can see your code here -deleted-
got Runtime error

Last edit: 2013-05-12 16:28:17
2013-05-11 14:34:07 Pushkar Mishra
Time limit is too strict for python and java.

RE: good algorithm + fast IO method = AC even for slow languages

Last edit: 2013-05-11 19:26:32
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.