10534 - Wavio Sequence

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

Moderator: Board moderators

Sanghack
New poster
Posts: 16
Joined: Wed Jul 17, 2002 5:55 pm
Location: Seoul, Korea

It's my simple (?) code

Post by Sanghack » Wed Aug 13, 2003 6:16 am

[cpp]int seqIndex;
// left to right increase order
for(seqIndex=0;seqIndex<size;seqIndex++){
incOrder[seqIndex]=1;
for(int i=seqIndex-1;i>=0;i--){
if(seq == seq[seqIndex]-1 && incOrder[seqIndex] < incOrder+1){
incOrder[seqIndex]=incOrder+1;
break;
}
if(seq < seq[seqIndex] && incOrder[seqIndex] < incOrder+1){
incOrder[seqIndex]=incOrder+1;
}
}
}
// right to left increase order (namely decrease order)
int max=INT_MIN;
for(seqIndex=size-1;seqIndex>=0;seqIndex--){
decOrder[seqIndex]=1;
for(int i=seqIndex+1;i<size;i++){
if(seq == seq[seqIndex]-1 && decOrder[seqIndex] < decOrder+1){
decOrder[seqIndex]=decOrder+1;
break;
}
if(seq < seq[seqIndex] && decOrder[seqIndex] < decOrder[i]+1){
decOrder[seqIndex]=decOrder[i]+1;
}
}
// find max value.
if(decOrder[seqIndex]==incOrder[seqIndex] && max<decOrder[seqIndex]){
max=decOrder[seqIndex];
}
}[/cpp]


It's my core code. But it is O(n^2). So I can't escape from TLE.

I have to think more...

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

10534 Wavio Sequence - what are the trickies?

Post by little joey » Fri Aug 29, 2003 2:02 pm

I'm opening a new thread, because the previous one dealt mainly with runtime. That is not my point, runtime is fine, but getting tons of WA.
So either I'm stupid (which of course I am...) or I don't understand the question. Am I right that:

1. The wavio sequence can be the whole sequence, so WAVIO({1,2,1})={1,2,1}, with length 3?

2. The length of the sequence is always odd, so WAVIO({1,2,3,1})={1,2,1} (or {1,3,1}) with length 3?

3. If there's only one element, the length is always one (WAVIO({1}={1})?

4. There are no empty sequences to process (N>0, as given in the description)?

5. All numbers fit into an SINT32 (no long long or int64 needed)?

Please help me. I've hand checked hundreds of randomly generated sequences, and I cannot find my error. Can anyone publish some tricky cases?

-little joey

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede » Fri Aug 29, 2003 4:10 pm

according to what i know, all of your assumtion are correct. i think there is no trickies input. i just run LIS twice, and got AC.

regards
titid
Kalo mau kaya, buat apa sekolah?

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Fri Aug 29, 2003 5:41 pm

Thank you!
Knowing that my assumptions were right, I could closer examine my algorithm.
I found an off by one error in my binary search :oops: :oops: :oops: , but that only became manifest after scanning some 100 numbers in the sequence...
The most elementary algorithms are the hardest to code error free.
Programming in Pascal has curses and blessings: there are no built in functions for routine tasks :( , but you C/C++ guys will never know what binary search is realy all about :)!

medv
Learning poster
Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

10534 WA - Help me!

Post by medv » Sun Sep 21, 2003 7:47 pm

I run twice Longest Increasing sequence during O(n * log(n)),
but get WA!
Is there any tricks? Or where is my mistake?

program p10534;
const
max = 10010;
var
n,i,j,mx,counter:integer;
b,e,middle:integer;
left,right,m,l,r:array[1..max] of integer;
begin
while not eof do
begin
readln(n);
FillChar(m,SizeOf(m),0);
for i:=1 to n do read(m[i]); readln;

counter := 2;
l[1] := m[1]; left[1] := 1;
for i:=2 to n do
begin
if m[i] > l[counter-1] then
begin
l[counter] := m[i];
left[i] := counter;
Inc(counter);
continue;
end;

b := 0; e := counter - 1;
while (e - b > 1) do
begin
middle := (b + e) div 2;
if m[i] > l[middle] then b := middle
else e := middle;
end;
l[e] := m[i];
left[i] := e;
end;

counter := n-1;
r[n] := m[n]; right[n] := 1;
for i:=n-1 downto 1 do
begin
if m[i] > r[counter+1] then
begin
r[counter] := m[i];
right[i] := n - counter + 1;
Dec(counter);
continue;
end;

b := counter+1; e := n+1;
while (e - b > 1) do
begin
middle := (b + e) div 2;
if m[i] > r[middle] then e := middle
else b := middle;
end;
r[b] := m[i];
right[i] := n + 1 - b;
end;


mx := 0;
for i:=1 to n do
if ((left[i] = right[i]) and (left[i] > mx)) then mx := left[i];
writeln(2*mx-1);
end;
end.

carneiro
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:

Post by carneiro » Sat Oct 04, 2003 12:47 am

I did a O(n*m) where m is the largest increasing subsequence size. And it passed time okay, but I'm getting WA.

Is there any trick input ? Could somebody throw in some INPUTs with correct OUTPUTs ?

Thanks !
[]s
Mauricio Oliveira Carneiro

carneiro
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:

let me start :-)

Post by carneiro » Sat Oct 04, 2003 3:48 am

Ok, let me start with the INPUT / OUTPUT for this problem.

For the following Input :

Code: Select all

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

My *WA* program answers the following :

Code: Select all

9
9
1
9
1
1
11
5
3
7
9
9
7
7
7
9
5
7
7
9
7
7
9
7
7
9
9
9
9

What sould be the " accepted " output ?

thanks ![/code]
[]s
Mauricio Oliveira Carneiro

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Sat Oct 04, 2003 5:06 am

Output from AC program:

Code: Select all

9
9
1
9
1
1
11
5
3
7
9
9
7
7
7
9
7 <- Your program gives 5
7
7
9
7
7
9
7
7
9
9
9
9
Wish you good luck, and get AC soon! :D

carneiro
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:

Post by carneiro » Sat Oct 04, 2003 8:55 pm

Fixed and ACCEPTED =P

thanks junjieliang !!!!!!!!!

but , this brought some curiosity to me ... the only thing I changed was :

j = (min(f, t)*2) - 1;

into :

j = min(f, t);

and after all calculations ..

j = j*2-1

what possible difference can it make ?
[]s
Mauricio Oliveira Carneiro

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Sun Oct 05, 2003 1:01 am

I don't know what your min function returns, but assuming j's an int .. if min returns like a short, the original might overflow while doing the calculations, where as the second one won't .. just a hunch .. i dunno what else it could be though

carneiro
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:

Post by carneiro » Sun Oct 05, 2003 3:20 am

Could be that also, but the values in question are around 10 (like 7 and 5). My min function is the following :

Code: Select all

#define min(a,b) ((a)<(b))?(a):(b)
[]s
Mauricio Oliveira Carneiro

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:

Post by Yarin » Mon Oct 06, 2003 9:34 am

You must have a () around your whole define:

#define min(a,b) ((a)<(b)?(a):(b))

Otherwise it will expand to (a)<(b)?(a):(b)*2-1
which is evaluated a<b?a:(b*2-1)

The () around (a)<(b) ain't necessary

yatsen
Learning poster
Posts: 68
Joined: Fri Nov 23, 2001 2:00 am
Location: taiwan

Post by yatsen » Fri Oct 31, 2003 11:12 am

junjieliang wrote:I solved this problem with an O(N^2) algo, but I believe that only happens in the worst case (or maybe not, if I did a better analysis of the complexity).

Another way would be to use the O(n log n) algo for LIS, which is just modifying a loop in the original algorithm to use binary search. Does anybody need the code? It can be obtained from the USACO training gateway, or I can post it here...
Please post it here or pm to me.
Thanks very much!

yatsen
Learning poster
Posts: 68
Joined: Fri Nov 23, 2001 2:00 am
Location: taiwan

Post by yatsen » Mon Nov 03, 2003 6:02 am

try this input:
20
13 7 5 7 6 7 2 7 3 20 9 9 15 20 9 10 12 12 4 13
The answer is 7.

I think you should add something before

l[e] := m;
left := e;

My solution (in C) is to modify like this:

if(m<=l)
{
l=m;
left=b;
}
else
{
l[e] = m;
left = e;
}

Zhou Yiyan@SHU
New poster
Posts: 12
Joined: Tue Jul 30, 2002 9:24 am
Location: SHU, Shanghai, China

I used LIS of O(nlogn) version, but still WA

Post by Zhou Yiyan@SHU » Sun Jul 18, 2004 8:52 am

I have read all the posts about 10534, and used double LIS of O(nlogn) version, the bi_search also have been tested. But it still got WA, can someone tell me what's wrong with my code?
[cpp]
code deleted
[/cpp]
Last edited by Zhou Yiyan@SHU on Sun Jul 18, 2004 12:29 pm, edited 1 time in total.

Post Reply

Return to “Volume 105 (10500-10599)”