10534 - Wavio Sequence

[Sanghack]

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

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]

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

[little joey]

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]

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]

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 !

[carneiro]

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]

[junjieliang]

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]

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 ?

[UFP2161]

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]

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)

[Yarin]

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]

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]

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]

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]