11525 - Permutation

Moderator: Board moderators

11525 - Permutation

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 ?
Ron
Learning poster

Posts: 55
Joined: Mon Jul 23, 2007 5:01 pm
Location: INDIA

Re: 11525 - Permutation

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

Hint: skip the numbers in block

New poster

Posts: 27
Joined: Sun Feb 18, 2007 2:14 pm

Re: 11525 - Permutation

my code gives TLE.
Code: Select all
`AC`

EDIT : Thank you all for advice
Last edited by Ron on Wed Oct 15, 2008 3:28 am, edited 3 times in total.
Ron
Learning poster

Posts: 55
Joined: Mon Jul 23, 2007 5:01 pm
Location: INDIA

Re: 11525 - Permutation

I used binary tree to solve the problem.
Leonid
Experienced poster

Posts: 148
Joined: Thu Dec 22, 2005 5:50 pm

Re: 11525 - Permutation

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

Posts: 27
Joined: Sun Feb 18, 2007 2:14 pm

Re: 11525 - Permutation

Leonid wrote: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.
Robert Gerbicz
Experienced poster

Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek

Re: 11525 - Permutation

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.
Chimed
New poster

Posts: 12
Joined: Mon Oct 20, 2008 10:37 am

Re: 11525 - Permutation

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.
wahaha
New poster

Posts: 16
Joined: Mon Jul 14, 2008 6:18 pm

Re: 11525 - Permutation

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.
roticv
Learning poster

Posts: 63
Joined: Sat Dec 11, 2004 9:28 am

Re: 11525 - Permutation

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

Could anyone give me some hint, plz?
lionking
New poster

Posts: 9
Joined: Tue Feb 17, 2009 6:46 pm