11031 - Looking for a Subset

[Darko]

Can someone check this I/O?
Input:

Code: Select all

25 9
1 19 12 2 18 23 11 22 15 25 20 24 3 10 8 14 16 17 9 21 5 7 4 6 13 
1
2
3
4
5
6
7
8
9
0 0

Output:

Code: Select all

Set 1:
  Subset 1:
    1
  Subset 2:
    1 19
  Subset 3:
    1 12 18
  Subset 4:
    1 12 18 23
  Subset 5:
    1 12 18 23 25
  Subset 6:
    1 2 11 15 20 24
  Subset 7:
    1 2 3 10 14 16 17
  Subset 8:
    1 2 3 10 14 16 17 21
  Subset 9:
    Impossible

Thanks in advance.

P.S. At least I found out that my nlogk was too slow the way it was.

[tywok]

It differs from my ACed output:

Code: Select all

I posted a not correct output and removed it. I run an old version which was WA.

[mf]

tywok, some of your outputs are not increasing sequences.

Here's my AC output:

Code: Select all

Set 1:
  Subset 1:
    1
  Subset 2:
    1 19
  Subset 3:
    1 19 23
  Subset 4:
    1 19 23 25
  Subset 5:
    1 12 18 23 25
  Subset 6:
    1 12 15 16 17 21
  Subset 7:
    1 2 11 15 16 17 21
  Subset 8:
    1 2 3 10 14 16 17 21
  Subset 9:
    Impossible

[Darko]

Thanks, I don't know why I thought that the answer was the first sequence of the given length...

[C]

Well my code used 5.070 CPU time. And I use a o(n^2) algorithm,
and i see the ranklist almost all codes run under 1 CPU time, how can i do that? can anyone suggest any better ones ?

[sohel]

Well my code used 5.070 CPU time. And I use a o(n^2) algorithm,
and i see the ranklist almost all codes run under 1 CPU time, how can i do that? can anyone suggest any better ones ?

You can convert O(n^2) to O( n log(n) ) or to be more precise O( n log(h) ).

[Timo]

to C

for convert from O(n^2) to O(n log(h) ) you can use the O(n log(h) ) LDS Algorithm.

First time see this problem my algo is same with you O(n^2).
But think a few minutes the inner loop can be replace by Binary Search.
I think O(n^2) will give TLE, but I don't know it can get AC in 5 seconds.

Hope it helps you .

[Jan]

I think O(n^2) will give TLE, but I don't know it can get AC in 5 seconds.

The reason is quite simple. The input file was set in such a way that an O(n^2) solution would exceed the contest time limit. But I donot think that a 10000^2 loop can be acc. Amaizing! We will try to set a new input file.

Thanks.

[C]

To Timo and sohel:

Thanks for the idea, I will try once again in the next few days!!

To Jan:
It seems that I am lucky. Well I can also try once again to submit with my current solution after u set a new input file and to see if your input is good enough

I got ACC by using a nlogn LIS algo. GREAT!

[bijon]

i know it is simply a LDS problem and my prog gives same output as mf.
but i got wrong answer in 0.107 sec and cannot find bugs.my algorithm is
i use LDS from the reverse of the array then find the increasing seqence
from the front side for each query.
can anyone check if my given output is correct or not?
INPUT:

Code: Select all

10 2
340 526 188 739 489 387 988 488 710 173
1
4
10 7
153 292 997 441 953 831 441 423 618 905
1
2
8
5
7
3
4
11 5
903 731 834 353 363 690 668 156 718 281 874
5
1
3
4
2
9 5
112 243 288 336 493 950 1283 1670 2473
3
5
6
7
5
7 6
1 12 417 551 232 3023 3044
1
2
3
4
5
6
12 8
944 334 960 471 650 834 2333 2 23444 1000 1400 24000
5
4
2
6
3
1
7
8
16 6
308 704 408 26 773 950 91 276 834 803 223 22 1044 1155 1 33 
3
4
2
6
5
1
24 5
151 3257 745 979 433 138 221 12325 348 44472 299 780 393 959 917 241 57767 245 66606 428 970 533 88843 999429
8
12
10
5
3
19 8
651 557 569 489 622 45 605 374 301 866 383 31 600 45 375 222 687 508 289
3
15
4
8
5
6
2
7
3 0
623 835 523
0 0

OUTPUT:

Code: Select all

Set 1:
  Subset 1:
    340
  Subset 2:
    340 526 739 988
Set 2:
  Subset 1:
    153
  Subset 2:
    153 292
  Subset 3:
    Impossible
  Subset 4:
    153 292 441 831 905
  Subset 5:
    Impossible
  Subset 6:
    153 292 997
  Subset 7:
    153 292 441 953
Set 3:
  Subset 1:
    353 363 690 718 874
  Subset 2:
    903
  Subset 3:
    731 834 874
  Subset 4:
    353 363 690 718
  Subset 5:
    731 834
Set 4:
  Subset 1:
    112 243 288
  Subset 2:
    112 243 288 336 493
  Subset 3:
    112 243 288 336 493 950
  Subset 4:
    112 243 288 336 493 950 1283
  Subset 5:
    112 243 288 336 493
Set 5:
  Subset 1:
    1
  Subset 2:
    1 12
  Subset 3:
    1 12 417
  Subset 4:
    1 12 417 551
  Subset 5:
    1 12 417 551 3023
  Subset 6:
    1 12 417 551 3023 3044
Set 6:
  Subset 1:
    944 960 2333 23444 24000
  Subset 2:
    944 960 2333 23444
  Subset 3:
    944 960
  Subset 4:
    334 471 650 834 2333 23444
  Subset 5:
    944 960 2333
  Subset 6:
    944
  Subset 7:
    334 471 650 834 2333 23444 24000
  Subset 8:
    Impossible
Set 7:
  Subset 1:
    308 704 773
  Subset 2:
    308 704 773 950
  Subset 3:
    308 704
  Subset 4:
    308 704 773 950 1044 1155
  Subset 5:
    308 704 773 950 1044
  Subset 6:
    308
Set 8:
  Subset 1:
    151 3257 12325 44472 57767 66606 88843 999429
  Subset 2:
    Impossible
  Subset 3:
    Impossible
  Subset 4:
    151 3257 12325 44472 57767
  Subset 5:
    151 3257 12325
Set 9:
  Subset 1:
    557 569 622
  Subset 2:
    Impossible
  Subset 3:
    557 569 622 866
  Subset 4:
    Impossible
  Subset 5:
    45 374 383 600 687
  Subset 6:
    Impossible
  Subset 7:
    651 866
  Subset 8:
    Impossible
Set 10:

Thanks in advance.

[Victor Barinov]

Hello!

My AC program gives the same output, but there in your output is one extra space at every line. Maybe this is a reason of WA?..

[bijon]

Victor wrote:

but there in your output is one extra space at every line

my output didn't print extra space.it was happened when you copied from
this page. anyways,is there any tricky i/o?still getting worng answer.


Thanks in advance.

[Solaris]

Hi bijon, first of all thanx to you as I used your I/O to get AC

just a hint .. there can be negative values as input ... (at least that was the reason for which I was suffering)

[Bert]

Hi, I understand there is nlogk algorithm for LIS/LDS problem. But I cannot understand how this can be applied here for the required answers. Can anyone further explain a bit, please?
Thanks~ ^^

[sohel]

I have solved this problem using LDS .... I am not sure whether it can be solved using LIS.

Reverse the input array and apply LDS. Then isn't the last value, with a seq # more than the reqd value, the first number in the answer.