K-Unique Sequence

What should be the output ... here

1 1
44

please clearify..

What makes it different from the first example test case?

Last test case is wrong....please admin check it ...

there is 2 8 2 10 3 6  are also valid solution,....

@Devraj: "If there are several solutions, output the lexicographically smallest one."

@all Singhs : Please read all the sections of the question carefully before asking a question here. Don't ask to check your code and read all the comments before posting your query.

For example input i have got good output but keep getting "wrong answer" after submit. What else sample input i can test for ? Any hints?

should two different sets also be unique??

i.e.

for

6 3

2 3 4 2 3 4

is below soltn valid??

(2,3,4),(2,3,4)

1 <= N <= 50000

0 <= a_i <= 1000000000

why is it 1000000000, shouldnt it be 50000 ? :|

Can anyone explain?

@Alan : We are not allowed to share any thing more than what is given in the question, till the contest ends. Thinking of tricky cases is part of solving the problem.

@Unknown, Nitish : There are no such things mentioned. Do not assume anything. Problem statement is clear.

@Unknown Cipher: Yes, it is valid.

@Nitish: I don't see any problem with that constraint.

Problem Input statement says->

"The next line contains a sequence of N integers a_i, where a_i is the i-th element of the sequence."

For N the range mentioned is 1 <= N <= 50000

For the sequence 0 <= a_i <= 1000000000

if its a sequence of N integer, it should be only 50000! Please correct me if I have misinterpreted some details.

@Nitish: The number of elements can be up to 50000 and each element of it can be between 0 and 1000000000, inclusive. There's nothing wrong with this.

Thanks Ashar. It was a misinterpretation from my side.

Something seems fishy... it says, "lexicographically smallest one" and not "numerically smallest one"

So, shouldn't the answer to last test case have been 2 3 2 6 10 8, as "10" comes lexicographically before "8"?

(2,3),(2,6),(10,8)

in fact, 10 2 2 3 6 8 must come... then,the results must be numerically ordered... amn't i right?

is lexicographically here means just comparison between numbers. This is what i get from sample output.

@ All: Sequence A is lexicographically smaller than sequence B if A contains a smaller number at the first element they differ.

@Devraj Singh Chouhan:

i think u should read the question 3 or 4 times.

all ur doubts will become clear.

time exceed.....isn't the next_permutation of STL fast enough?

Are the subsequences non-overlapping?

i.e

For N = 4, K = 2

Can we say 1 2 1 1 is K-unique?

Because [1..2] is 2-unique and [2..3] is again 2-unique?

Assuming the last case is correct.

I think my doubt is self answered.

The subsequences must indeed be "non-overlapping".

@ Ravi : If you split a sequence of length N into N/K subsequences, each of K contiguous elements, they must be non-overlapping.

(1, 2, 1, 1) is not 2-unique.

My code runs perfect on every type of testcase I can conceive yet gives a wrong answer of codechef.

I have tried covering all corner cases on my own. Everything looks fine! :|

What shoud be an individual's strategy in such cases?

@Nitish : One thing would be generate lots and lots of test-data randomly with very low constraints on the input and check your ouput with that of a bruteforce code's. Though I hardly do that and usually take a long break away from computer :)

Its a deadlock condition for me. :(

@Devraj Shing Chouhan : no need of answer ( specially when you also don't know ! )

/sources/Main.java:8: class TestUnique is public, should be declared in a file named TestUnique.java public class TestUnique{ ^ 1 error

what does this mean?

TestUnique is my class name

is it an error to declare it as public?

is the output of third input correct.....

shouldn't it be 2 6 2 8 3 10

can you provide test case file of some input

Devraj singh chouhan...u are a funny guy!!

@dharma : Your public class name should be "Main".

(2 3 2 6 8 10) is lexicographically smaller than (2 6 2 8 3 10).

@Devraj : No.

In case of 2,10,2,8,4,2 is the split it into contiguous elements of the form (10,2) (8,4) (2,2) valid ? should first set of these subsequences (10,2) start necessarily from beginning ?

@myriad: The order of elements in the sequence must be preserved.

Thanks @ Ashar faudi

my answer is showing run time error everytime..why it is so ????

I too have the same error.

@Ashar ... what you mean to say ... by order of elements in the sequence must be preserved.????  I can't see in the test cases the order has been preserved.... :-o

@Admin... I got wrong answer first... then I checked my codes logic.. and changed it... and it can't effect my running time.. :-o .. not it shows.. TL.... :-o .. how come??? wrong answer I can take... bt. TL exceed... on my system it runs for 0.23 sec... :-o

@Admin.. Oops... my mistake... :-) ... I didn't tried for worst case... :-) .. sorry!!

@All... now am just blank.. what to do... :-o ... after contest is over... I ll request to any one if interested and can tell me... why I am getting TLE.... :-( ... hoping for some one will help me out...

Thanks in advance... :-)

@Nitin: I meant, for example, (1, 2, 3, 4) is split into (1, 2), (3, 4) not (1, 3), (2, 4). This was to answer myriad's clarification.

can we rotate lastand first element of this array.....?????

@Devraj: what do you mean by "rotate" ?

my means that..... 1 2 3 4 there are one continous seq. is (4,1) (2,3) after rotation of array...

The statement says nothing about rotation.

huh!! lots of optimization!!!

I am getting correct answer for all the test cases given in sum and comments but still getting wrong answer can any one suggest some critical test cases....

I tried the problem with three different logics. Each time the logic was more efficient in terms of time and space. Still the output is TIME LIMIT EXCEEDED. I know there is still room for optimization but now i am running short of ideas. Never mind. It's always a race between you and you :)

in following seq.

2 2 3 4

can we consider (4,2) as continous seq./////

@Devraj: No.

Hmm  writing out just the 50000 numbers takes more time than 5 sec... what about that?:S

why my solution of O(nlgn) complexity is timing out?????

Of course because it takes more than 5 seconds on some test files.

@Manoj:::in above case this is how this is continous seq. of 4 subseq.

(1,1,2,3) is not continous.

if i use list container and delete elements frm it...could it cause time limit exceeded????

@Nikhil - I am using the hash set and still it is causing the time limit. So you can guess what the list will do.

@CodeChef Admin: When will we be able to start submitting solutions again? For this contest... I get a "something wrong with the contest configuration" error whenever I submit.