Page 1 of 2

11031 - Looking for a Subset

Posted: Mon May 15, 2006 10:19 am
by 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.

Posted: Mon May 15, 2006 10:44 am
by 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.

Posted: Mon May 15, 2006 10:47 am
by 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

Posted: Mon May 15, 2006 10:55 am
by Darko
Thanks, I don't know why I thought that the answer was the first sequence of the given length...

How can it be proved??

Posted: Tue May 16, 2006 6:01 pm
by 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 ?

Re: How can it be proved??

Posted: Wed May 17, 2006 8:17 am
by sohel
C wrote: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) ).

Posted: Wed May 17, 2006 9:43 am
by 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 :D.

Posted: Thu May 18, 2006 1:55 am
by Jan
Timo wrote: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.

Posted: Thu May 18, 2006 4:07 am
by C
To Timo and sohel:

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

To Jan:
:wink: 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 8) 8)

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

Posted: Fri May 19, 2006 7:52 pm
by 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.

I checked it...

Posted: Sat May 20, 2006 12:15 pm
by 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?..

Posted: Sat May 20, 2006 12:30 pm
by 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.

Posted: Thu Jun 15, 2006 11:54 pm
by Solaris
Hi bijon, first of all thanx to you as I used your I/O to get AC :D

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

Posted: Mon Jun 19, 2006 10:01 am
by 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~ ^^

Posted: Mon Jun 19, 2006 8:27 pm
by 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.