it takes a lot of my times.

Can somebody write input?

Please could anybody give me the test case?

Thanks

Code link: REMOVED after ac

I can't provide a test though but the bug that was causing WA was simple.

My DP recurrence was simple, dp[s][e] contains the shortest folding for the segment a[s]a[s+1]...a[e], where 'a' is the main string. Now, then I was calculating dp[s][e] I made an error and dp[s][e] was in some rare cases containing solutions of dp[s][e+1]dp[s][e+2]... ans the resulting sequence was containing lower length then actually possible.

Edited by author 19.08.2013 11:15

Edited by author 19.08.2013 15:43

In the text of the problem there is AAAAAAAAAABABABCCD is 10(A)2(BA)B2(C)D , where CC is translated to 2(C), but in both examples this rule is not obeyed: in the first example CC is NOT translated to 2(C) , and same with EE in second example. And in text there is "where X is a decimal representation of an integer number greater than 1". Maybe i'm missing something?

EDIT: And also i have found error in example in the text of the problem: AAAAAAAAAABABABCCD is 10(A)2(BA)B2(C)D; sequence ABABABCCD should be translated to 3(AB)2(C)D.

Edited by author 01.08.2011 05:07

Edited by author 01.08.2011 05:09

Please, help!

How do people do it?
I did O(n^3) and it passes in 0.031

if you know faster solution, please send me to imslavko@gmail.com

---

Всем привет
Как люди сдали эту задачу за 0.015?
У меня получилось только за О(н^3) и 0.031 сек.
Если Вы знаете решение лучше, пожалуйста отправьте на imslavko@gmail.com

Can I have a test for WA 27 please?

My programm using dp...
Why I have WA 25.Give any test,please.

Sorry for bad English.

[code deleted]


Edited by author 22.01.2007 15:33

Edited by author 22.01.2007 15:41

Edited by author 22.01.2007 17:50

can i include string.h ???

I has written O(N^3) solution.
But I think there is O(N^2) one...
If somebody knows please tell me (here or sk1@hotbox.ru)

Help!
Here's my programm:
var s:array [1..100] of char;
r:array [1..100,1..100,1..100] of char;
l:array [1..100,1..100] of byte;
n,i,j,z,k,a,b:integer;
bool:boolean;
function f (i:byte):byte;
begin
 if (i>=10) and (i<100) then f:=4 else if i=100 then f:=5 else f:=3;
end;
begin
 i:=1; fillchar (l,sizeof (l),0);
 while not eoln do begin Read (s[i]); inc (i); end;
 n:=i-1;
 for j:=1 to 4 do
  for i:=1 to n-j+1 do begin
   for z:=i to i+j-1 do r[i,j,z-i+1]:=s[z];
   l[i,j]:=j;
  end;
 for j:=5 to n do
  for i:=1 to n-j+1 do begin
   a:=0;
   for z:=1 to j-1 do
    if (l[i,j]>l[i,z]+l[i+z,j-z]) or (l[i,j]=0) then
     begin
      l[i,j]:=l[i,z]+l[i+z,j-z];
      a:=z;
     end;
   b:=0;
   for z:=2 to j do
    if j mod z=0 then
     begin
      bool:=true;
      for k:=i to i-1+j-j div z do if s[k]<>s[k+j div z] then begin bool:=false; break; end;
      if bool then if l[i,j]>=f(z)+l[i,j div z] then
       begin
        l[i,j]:=f(z)+l[i,j div z];
        b:=z;
       end;
     end;
   if b=0 then
    begin
     for z:=1 to l[i,a] do
     r[i,j,z]:=r[i,a,z];
     for z:=1 to l[i+a,j-a]
     do r[i,j,z+l[i,a]]:=r[i+a,j-a,z];
    end else
    begin
     if b<10 then begin
      r[i,j,1]:=chr (b+ord ('0'));
      r[i,j,2]:='(';
      for z:=1 to l[i,j div b] do r[i,j,z+2]:=r[i,j div b,z];
      r[i,j,l[i,j div b]+3]:=')';
     end else if b<100 then begin
      r[i,j,1]:=chr (b div 10+ord ('0'));
      r[i,j,2]:=chr (b mod 10+ord ('0'));
      r[i,j,3]:='(';
      for z:=1 to l[i,j div b] do r[i,j,z+3]:=r[i,j div b,z];
      r[i,j,l[i,j div b]+4]:=')';
     end else begin
      r[i,j,1]:='1';
      r[i,j,2]:='0';
      r[i,j,3]:='0';
      r[i,j,4]:='(';
      for z:=1 to l[i,j div b] do r[i,j,z+4]:=r[i,j div b,z];
      r[i,j,l[i,j div b]+5]:=')';
     end;
    end;
  end;
  for i:=1 to l[1,n] do write (r[1,n,i]);
end.
It gets ML on test 20.

var try:byte;
begin
end.

0.046 sec 457 Kb
I think that before system upgrade it should works near to 0.5 sec.