11031 - Looking for a Subset

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

11031 - Looking for a Subset

Post by Darko » Mon May 15, 2006 10:19 am

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
New poster
Posts: 32
Joined: Sun Oct 30, 2005 2:22 am

Post by tywok » Mon May 15, 2006 10:44 am

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.
Last edited by tywok on Mon May 15, 2006 8:17 pm, edited 1 time in total.
Impossible is nothing

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Mon May 15, 2006 10:47 am

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
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Mon May 15, 2006 10:55 am

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

C
New poster
Posts: 35
Joined: Mon Apr 17, 2006 1:04 pm

How can it be proved??

Post by C » Tue May 16, 2006 6:01 pm

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 ?

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: How can it be proved??

Post by sohel » Wed May 17, 2006 8:17 am

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) ).

Timo
Learning poster
Posts: 70
Joined: Tue Oct 11, 2005 2:44 am
Location: Indonesia

Post by Timo » Wed May 17, 2006 9:43 am

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.
"Life is more beautiful with algorithm"

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu May 18, 2006 1:55 am

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.
Ami ekhono shopno dekhi...
HomePage

C
New poster
Posts: 35
Joined: Mon Apr 17, 2006 1:04 pm

Post by C » Thu May 18, 2006 4:07 am

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!
Last edited by C on Tue May 23, 2006 11:49 pm, edited 1 time in total.

bijon
New poster
Posts: 18
Joined: Thu Jan 06, 2005 2:12 pm

Post by bijon » Fri May 19, 2006 7:52 pm

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
New poster
Posts: 24
Joined: Sun Oct 03, 2004 10:03 am

I checked it...

Post by Victor Barinov » Sat May 20, 2006 12:15 pm

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
New poster
Posts: 18
Joined: Thu Jan 06, 2005 2:12 pm

Post by bijon » Sat May 20, 2006 12:30 pm

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
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:

Post by Solaris » Thu Jun 15, 2006 11:54 pm

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)
Where's the "Any" key?

Bert
New poster
Posts: 3
Joined: Mon Jun 19, 2006 9:57 am
Location: Hong Kong

Post by Bert » Mon Jun 19, 2006 10:01 am

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~ ^^

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Mon Jun 19, 2006 8:27 pm

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.

Post Reply

Return to “Volume 110 (11000-11099)”