OJ Board

I think that 0.8 sec can be achieved using a O(n^3) algorithm. I am not sure about that 0.2 sec can be achieved but I belive. Abishek, please, check your inbox.

I used dynamic memory allocation to minimaze memory usage.

type tarr = array[1..maxn]of word;
parr = ^tarr;
var inf : array[1..maxn, 1..maxn]of parr;

...

getmem(inf[i, j], (j - i + 1) shl 1)

To speed-up my solution I used 2 ideas:
1.) if inf[i, j, k] = 0 then you should not consider this ...

But how you calculate a[j]? Please, explain it. I used 3-dim array to store maximum score in reducing i-j with the last color being the color of j and length k and another 3-dim array to speed-up seeking in the first array.

Yes, I have seen you submision :)
But you write
please refer to gush's post in the other thread(use search for 10559)

gush wrote

color[z] must be defferent from color[z + 1] and
color[z + 1] should be the same as color

This aproach is wrong. You also should consider then color[z] and color ...

Thanks, but I've got Accepted already. I used the same aproach as gush. But I wonder how to get Accepted under 1 sec ?! My solution work 1.652 sec and 4988 KB.

I've got TimeLimitExceeded with my DP algorithm:

Let Inf[i, j, k] be the highest score that I can get from i postion to j position clicking j-th box at last and length of the last segment is k

Then

Inf[i, i, 1] = 1
Inf[i, i + 1, 1] = 2 if color[i] <> color[i + 1]
Inf[i, i + 1, 2] = 4 if color ...

I've got many WA's
Please tell me what can be wrong? are there any tricks ?

Soory, I've found the error

Word is a string formed only by 'a'..'z', 'A'..'Z'
fun&games - 2 words
better4you - 2 words

I used such code to parse the text

[pascal] s := s + ' ';
t := '';
for i := 1 to length(s) do
if s in ['a'..'z', 'A'..'Z'] then t := t + s else
if t <> '' then begin process_word(t); t := ''; end ...

Let's talk about 10679's tests. I think that they are very easy.

First of all, if in Aho-Corasick you compute failure function in dfs order you got accepted. That's very strage, because almost every randomized test check this.

Aho-Corasick have complexity O(m + z), where z is the number of ...

Thanks, ulin! It was really helpful for me - I've got Accepted

Can anyone explain me why my code (it was accepted 3 days later) gets TLE :evil: . I am using KMP

[pascal]{$A-,B-,D+,E+,F-,G-,I-,L-,N-,O+,P-,Q-,R-,S-,T-,V-,X+}
const maxlen = 110000;

type my_string = record
len : longint;
sa : array[1..maxlen]of char;
end;

procedure read_str(var a : my_string ...

It is really very strange, because the same code in C++ get Accepted. Why it happened?

I write a program using PIE but it get WA. Please, help me!

[pascal]Program p10542;

Var T, t_id : Integer;
i, D : Integer;
j : Int64;
a, b : Array[1..10]of Int64;

function gcd(a, b : Int64) : Int64;
begin
if a = 0 then gcd := b else gcd := gcd(b mod a, a);
end;

procedure rec(id, v ...

I also got WA many times.
My program output in the last test case "15484". I think it is right. Can anybody explain to me why the answer 15484 is incorrect.

Look at my program for my algorithm (I can't explain it using only words :) ):

[pascal]Program p10542;

Type Integer = Int64;

Var T, t_id ...

Thanks, I get AC