UVa 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 element in ...

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 are the s...

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] = c...

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;[/pascal]

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 pettern o...

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); var ...

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 : integer; g : Int...

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 : Long...

Thanks, I get AC