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

sohel
Guru
Posts: 856 Joined: Thu Jan 30, 2003 5:50 am
Location: New York
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

.

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

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

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!

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

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

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.