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

.

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!!

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!

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

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.