Swapping mismatchesProblem code: C1 |
All submissions for this problem are available.
You are given a sequence w of integers. A mismatch is any such pair of neighbouring elements of sequence w[i] and w[i+1], that w[i]>w[i+1]+1.
As long as there is any mismatch, you solve it by swapping the mismatching numbers. Given an input sequence, calculate one of the possible output mismatch-less sequences obtained by successively solving mistmatches by swapping.
Input
First - 1<=t<=10 - the number of tests. For each test: first - 1<=n<=100000. Then, n nonnegative integers.
Output
For each test, you should output exactly n integers.
Example
Input: 2 4 4 3 2 1 4 4 3 1 2 Output: 4 3 2 1 1 4 3 2
| Date: | 2009-04-20 |
| Time limit: | 1s |
| Source limit: | 50000 |
| Languages: | C C99 strict C++ PAS gpc PAS fpc JAVA NICE JAR C# C#2 NEM ST ASM D FORT ADA BASH PERL PYTH RUBY LUA ICON PIKE PHP SCM guile SCM qobi LISP sbcl LISP clisp HASK CAML CLPS PRLG WSPC BF ICK TEXT |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
Ok, am getting a feeling that something is wrong with this problem... Its saying Timeout for my linear solution. Can someone please verify?
can u explain the second output ?
ya it is like this
Anyone please Correct me if I am wrong. This is what I have understood.
The input sequence is
--->4 3 1 2
pair (3 1) are mismatch so they swap, now the sequence become
---->4 1 3 2
pair (4 1) are mismatch so they swap, now the sequence become
---->1 4 3 2
now no pair is mismatch.
this concludes to the final answer.
The question reports that the time limit is 1s. But accepted answers have time limit beyond this. Can someone please explain what is exactly the time efficency criteria??
guys plz help me....
should the input takes unsigned long or ve integer means just 2^31 -1
or it should take 2^32 -1 value also
please help me guys...
first of all what does "t" means here "the number of tests" ???
if so how could it be (-1
sandeep> its not "-1" it is "-" dash symbol
can any one help me, i am getting correct out put , but it is displaying wrong, i cant understand , i applied on 1000 numbers and checked it.//
Hi All,
I have got correct answer too.... But i really dot understand why it says wrong answer. I tried possible test case inputs. Can somebody please help?
@Srikanth The contest is still running and asking for help is not right.
@Prunthaban K
thanks for reminding me.... :)
"calculate one of the possible output mismatch-less sequences obtained by successively solving mistmatches by swapping."
Does this mean any sequence that doesn't have mismatch and exclusively contains all the elements given in the list?
are the numbers unique ?
"Given an input sequence, calculate one of the possible output mismatch-less sequences obtained by successively solving mistmatches by swapping"
...Doesn't a sorted list (ascending) match one of the possible outputs not having any mismatches? Based on the requirements mentioned, the sorted list should also be an acceptable solution.
Pls confirm.
Thanks...
Pinkesh, I dont think that's correct. Consider the sequence
4 5 6 2 1
the sorted seq in ascending order would be: 1 2 4 5 6
however the only way to obtain that result is to break the rules of the problem by swapping 4 and 5; 4 and 6; 5
Yes Puneet, you are correct. Thanks for pointing out.
i've a N (log N^2) algorithm but it is TLE. Anyone care to help me or suggest better. It is similar to merge sort. I divide into 2 halfs and then combine then.
http://codepad.org/AZj4Jwrn
@tvrju
It's against the spirit of competition to ask for any help during the contests.
Try on your own and after the contest post on the forum. You will get help then.