11525 - Permutation

[Ron]

I am getting TLE.
My approach is simple. I am using n-times delete function to delete a value which is already used for print.
Is it right way ?

[pvncad]

You can improve the algorithm further. You don't need to n iterations to find what to print.

Hint: skip the numbers in block

-pvncad

[Ron]

my code gives TLE.

Code: Select all

AC

EDIT : Thank you all for advice

[Leonid]

I used binary tree to solve the problem.

[pvncad]

Hint: split the vectors into smaller ones so that you search and removal time reduces.

[Robert Gerbicz]

I used binary tree to solve the problem.

More precisely it's possible to solve this problem by interval tree (this is also a binary tree) in O(N*log(N)) time and in O(N) memory.

[Chimed]

Done both idea

Using binary tree and splitting to subarrays.
But didn't understand why subarray method is faster than the other? Was it good test for this idea or generally it holds. Anyway best method might use binary tree because it is safe and usefull afterward.

[wahaha]

should i use BigNum in this problem, i think if n = k! it's a very very big number.

another question is if this problem should use BigNum, it seems O(klgk) is not fast enough in my solution .

i need some help.

[roticv]

There is no need to compute factorials. Just find the kth smallest number that is not used (k starts from 0...so-on).

People have suggested using interval/segment trees to solve this problem. I've used fenwick trees to solve it. It is possible to find the kth smallest number using binary search.

[lionking]

I don't understand why this problem can use interval tree to solve it?

Could anyone give me some hint, plz?