## 10534 - Wavio Sequence

Moderator: Board moderators

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

### It's my simple (?) code

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

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

### 10534 Wavio Sequence - what are the trickies?

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

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 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 , 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!

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
FillChar(m,SizeOf(m),0);

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

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

carneiro
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:
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

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
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:
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:
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
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
try this input:
20
13 7 5 7 6 7 2 7 3 20 9 9 15 20 9 10 12 12 4 13

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

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.