Common Board @ Timus Online Judge

I get TL. How I can improve my program?(+)

Posted by Nazarov Denis (nsc2001@rambler.ru) 17 Feb 2002 15:12

{$A-,B-,D+,E+,F-,G-,I-,L-,N-,O-,P-,Q-,R-,S-,T-,V-,X-}
Program t1176;

Const MaxN   = 1000;
      MaxAns = 32000;
      Cadd   : array[1..4]of byte=
               (1, 4, 16, 64);

Type Mas = array[1..MaxN,1..MaxN div 4]of byte;
      Integer = SmallInt;
      Ans = record
              A : array[1..MaxAns,1..2]of integer;
              L : integer;
             end;

Var   Map       : Mas;
      N,A,i,j   : longint;
      Cur,Max   : longint;
      An,Bn,Cn : Ans;
      b         : byte;
      W         : array[1..MaxN]of integer;
      Idiv4     : array[1..MaxN]of integer;
      Imod4     : array[1..MaxN]of integer;
      CAmod     : array[0..255,1..4]of byte;
      CAdiv     : array[0..255,1..4]of byte;
      Hmul      : array[0..4,1..4]of byte;

Function GetValue(i,j : integer) : byte;
Var Fj,Sj : integer;
    Pvalue : byte;
    k,l,h : byte;
begin
Fj:=Idiv4[j]+1;
if Imod4[j]=0 then Fj:=Fj-1;
Sj:=Imod4[j];
if Sj=0 then Sj:=4;
l:=Map[i,Fj];
Pvalue:=0;
for k:=4 downto 1 do begin
    h:=CAdiv[l,k];
    l:=CAmod[l,k];
    if Sj=k then begin
     Pvalue:=h;
     break;
    end;
   end;
GetValue:=Pvalue;
end;

Procedure SetValue(i,j : integer; value : byte);
Var Fj,Sj : integer;
    Cvalue : byte;
    Pvalue : byte;
    k,l,h : byte;
begin
Fj:=Idiv4[j]+1;
if Imod4[j]=0 then Fj:=Fj-1;
Sj:=Imod4[j];
if Sj=0 then Sj:=4;
l:=Map[i,Fj];
Pvalue:=0;
for k:=4 downto 1 do begin
    h:=CAdiv[l,k];
    l:=CAmod[l,k];
    if Sj<>k then Pvalue:=Pvalue+Hmul[h,k];
   end;
Cvalue:=Hmul[value,Sj];
Map[i,Fj]:=Pvalue+Cvalue;
end;

Procedure WriteIt(An : Ans);
Var i : integer;
begin
for i:=1 to Max do
   Writeln(An.A[i,1],' ',An.A[i,2]);
Halt(0);
end;

Procedure Merge(A,B : Ans;Var C : Ans);
Var Ai,Ci,Bi : integer;
begin
Ci:=0;
Bi:=0;
for Ai:=1 to A.L do begin
    Ci:=Ci+1;
    C.A[Ci]:=A.A[Ai];
    if (A.A[Ai,2]=B.A[1,1])and(Bi=0) then
     for Bi:=1 to B.L do begin
      Ci:=Ci+1;
      C.A[Ci]:=B.A[Bi];
     end;
   end;
C.L:=A.L+B.L;
end;

Procedure Go(Preducate : integer;Var MAns : Ans);
Var i,j,Pred : integer;
begin
Pred:=Preducate;
MAns.L:=0;
While True do begin
   j:=0;
   for i:=1 to N do if W[i]>0 then
    if GetValue(Pred,i)=0 then begin
     j:=i;
     break;
    end;
   if j=0 then break;
   MAns.L:=MAns.L+1;
   MAns.A[MAns.L,1]:=Pred;
   MAns.A[MAns.L,2]:=j;
   W[Pred]:=W[Pred]-1;
   W[j]:=W[j]-1;
   SetValue(Pred,j,1);
   Pred:=i;
end;
end;

begin
For i:=1 to MaxN do Idiv4[i]:=i div 4;
For i:=1 to MaxN do Imod4[i]:=i mod 4;
For i:=0 to 255 do
For j:=1 to 4 do
   CAdiv[i,j]:=i div Cadd[j];
For i:=0 to 255 do
For j:=1 to 4 do
   CAmod[i,j]:=i mod Cadd[j];
For i:=0 to 3 do
For j:=1 to 4 do
   Hmul[i,j]:=i*Cadd[j];
FillChar(W,SizeOf(W),0);
Read(N,A);
Max:=0;
for i:=1 to N do
for j:=1 to N do begin
    read(b);
    SetValue(i,j,b);
    if (b=0)and(i<>j) then begin
     Max:=Max+1;
     W[i]:=W[i]+1;
     W[j]:=W[j]+1;
    end;
   end;
for i:=1 to N do SetValue(i,i,1);
Go(A,An);
While True do begin
   j:=0;
   for i:=1 to N do
    if W[i]>0 then begin
     j:=i;
     break;
    end;
   if j=0 then break;
   Go(j,Bn);
   Merge(An,Bn,Cn);
   An:=Cn;
end;
WriteIt(An);
end.

All this words about problem 1176

Posted by Nazarov Denis (nsc2001@rambler.ru) 17 Feb 2002 15:13

> {$A-,B-,D+,E+,F-,G-,I-,L-,N-,O-,P-,Q-,R-,S-,T-,V-,X-}
> Program t1176;
>
> Const MaxN   = 1000;
>       MaxAns = 32000;
>       Cadd   : array[1..4]of byte=
>                (1, 4, 16, 64);
>
> Type Mas = array[1..MaxN,1..MaxN div 4]of byte;
>       Integer = SmallInt;
>       Ans = record
>               A : array[1..MaxAns,1..2]of integer;
>               L : integer;
>              end;
>
> Var   Map       : Mas;
>       N,A,i,j   : longint;
>       Cur,Max   : longint;
>       An,Bn,Cn : Ans;
>       b         : byte;
>       W         : array[1..MaxN]of integer;
>       Idiv4     : array[1..MaxN]of integer;
>       Imod4     : array[1..MaxN]of integer;
>       CAmod     : array[0..255,1..4]of byte;
>       CAdiv     : array[0..255,1..4]of byte;
>       Hmul      : array[0..4,1..4]of byte;
>
> Function GetValue(i,j : integer) : byte;
> Var Fj,Sj : integer;
>     Pvalue : byte;
>     k,l,h : byte;
> begin
>   Fj:=Idiv4[j]+1;
>   if Imod4[j]=0 then Fj:=Fj-1;
>   Sj:=Imod4[j];
>   if Sj=0 then Sj:=4;
>   l:=Map[i,Fj];
>   Pvalue:=0;
>   for k:=4 downto 1 do begin
>     h:=CAdiv[l,k];
>     l:=CAmod[l,k];
>     if Sj=k then begin
>      Pvalue:=h;
>      break;
>     end;
>    end;
>   GetValue:=Pvalue;
> end;
>
> Procedure SetValue(i,j : integer; value : byte);
> Var Fj,Sj : integer;
>     Cvalue : byte;
>     Pvalue : byte;
>     k,l,h : byte;
> begin
>   Fj:=Idiv4[j]+1;
>   if Imod4[j]=0 then Fj:=Fj-1;
>   Sj:=Imod4[j];
>   if Sj=0 then Sj:=4;
>   l:=Map[i,Fj];
>   Pvalue:=0;
>   for k:=4 downto 1 do begin
>     h:=CAdiv[l,k];
>     l:=CAmod[l,k];
>     if Sj<>k then Pvalue:=Pvalue+Hmul[h,k];
>    end;
>   Cvalue:=Hmul[value,Sj];
>   Map[i,Fj]:=Pvalue+Cvalue;
> end;
>
> Procedure WriteIt(An : Ans);
> Var i : integer;
> begin
>   for i:=1 to Max do
>    Writeln(An.A[i,1],' ',An.A[i,2]);
>   Halt(0);
> end;
>
> Procedure Merge(A,B : Ans;Var C : Ans);
> Var Ai,Ci,Bi : integer;
> begin
>   Ci:=0;
>   Bi:=0;
>   for Ai:=1 to A.L do begin
>     Ci:=Ci+1;
>     C.A[Ci]:=A.A[Ai];
>     if (A.A[Ai,2]=B.A[1,1])and(Bi=0) then
>      for Bi:=1 to B.L do begin
>       Ci:=Ci+1;
>       C.A[Ci]:=B.A[Bi];
>      end;
>    end;
>   C.L:=A.L+B.L;
> end;
>
> Procedure Go(Preducate : integer;Var MAns : Ans);
> Var i,j,Pred : integer;
> begin
>   Pred:=Preducate;
>   MAns.L:=0;
>   While True do begin
>    j:=0;
>    for i:=1 to N do if W[i]>0 then
>     if GetValue(Pred,i)=0 then begin
>      j:=i;
>      break;
>     end;
>    if j=0 then break;
>    MAns.L:=MAns.L+1;
>    MAns.A[MAns.L,1]:=Pred;
>    MAns.A[MAns.L,2]:=j;
>    W[Pred]:=W[Pred]-1;
>    W[j]:=W[j]-1;
>    SetValue(Pred,j,1);
>    Pred:=i;
>   end;
> end;
>
> begin
> For i:=1 to MaxN do Idiv4[i]:=i div 4;
> For i:=1 to MaxN do Imod4[i]:=i mod 4;
> For i:=0 to 255 do
>   For j:=1 to 4 do
>    CAdiv[i,j]:=i div Cadd[j];
> For i:=0 to 255 do
>   For j:=1 to 4 do
>    CAmod[i,j]:=i mod Cadd[j];
> For i:=0 to 3 do
>

Re: May be Link List will be faster !

Posted by Tran Nam Trung (trungduck@yahoo.com) 17 Feb 2002 19:35

> > {$A-,B-,D+,E+,F-,G-,I-,L-,N-,O-,P-,Q-,R-,S-,T-,V-,X-}
> > Program t1176;
> >
> > Const MaxN   = 1000;
> >       MaxAns = 32000;
> >       Cadd   : array[1..4]of byte=
> >                (1, 4, 16, 64);
> >
> > Type Mas = array[1..MaxN,1..MaxN div 4]of byte;
> >       Integer = SmallInt;
> >       Ans = record
> >               A : array[1..MaxAns,1..2]of integer;
> >               L : integer;
> >              end;
> >
> > Var   Map       : Mas;
> >       N,A,i,j   : longint;
> >       Cur,Max   : longint;
> >       An,Bn,Cn : Ans;
> >       b         : byte;
> >       W         : array[1..MaxN]of integer;
> >       Idiv4     : array[1..MaxN]of integer;
> >       Imod4     : array[1..MaxN]of integer;
> >       CAmod     : array[0..255,1..4]of byte;
> >       CAdiv     : array[0..255,1..4]of byte;
> >       Hmul      : array[0..4,1..4]of byte;
> >
> > Function GetValue(i,j : integer) : byte;
> > Var Fj,Sj : integer;
> >     Pvalue : byte;
> >     k,l,h : byte;
> > begin
> >   Fj:=Idiv4[j]+1;
> >   if Imod4[j]=0 then Fj:=Fj-1;
> >   Sj:=Imod4[j];
> >   if Sj=0 then Sj:=4;
> >   l:=Map[i,Fj];
> >   Pvalue:=0;
> >   for k:=4 downto 1 do begin
> >     h:=CAdiv[l,k];
> >     l:=CAmod[l,k];
> >     if Sj=k then begin
> >      Pvalue:=h;
> >      break;
> >     end;
> >    end;
> >   GetValue:=Pvalue;
> > end;
> >
> > Procedure SetValue(i,j : integer; value : byte);
> > Var Fj,Sj : integer;
> >     Cvalue : byte;
> >     Pvalue : byte;
> >     k,l,h : byte;
> > begin
> >   Fj:=Idiv4[j]+1;
> >   if Imod4[j]=0 then Fj:=Fj-1;
> >   Sj:=Imod4[j];
> >   if Sj=0 then Sj:=4;
> >   l:=Map[i,Fj];
> >   Pvalue:=0;
> >   for k:=4 downto 1 do begin
> >     h:=CAdiv[l,k];
> >     l:=CAmod[l,k];
> >     if Sj<>k then Pvalue:=Pvalue+Hmul[h,k];
> >    end;
> >   Cvalue:=Hmul[value,Sj];
> >   Map[i,Fj]:=Pvalue+Cvalue;
> > end;
> >
> > Procedure WriteIt(An : Ans);
> > Var i : integer;
> > begin
> >   for i:=1 to Max do
> >    Writeln(An.A[i,1],' ',An.A[i,2]);
> >   Halt(0);
> > end;
> >
> > Procedure Merge(A,B : Ans;Var C : Ans);
> > Var Ai,Ci,Bi : integer;
> > begin
> >   Ci:=0;
> >   Bi:=0;
> >   for Ai:=1 to A.L do begin
> >     Ci:=Ci+1;
> >     C.A[Ci]:=A.A[Ai];
> >     if (A.A[Ai,2]=B.A[1,1])and(Bi=0) then
> >      for Bi:=1 to B.L do begin
> >       Ci:=Ci+1;
> >       C.A[Ci]:=B.A[Bi];
> >      end;
> >    end;
> >   C.L:=A.L+B.L;
> > end;
> >
> > Procedure Go(Preducate : integer;Var MAns : Ans);
> > Var i,j,Pred : integer;
> > begin
> >   Pred:=P

Re: May be Link List will be faster !

Posted by Algorist 18 Feb 2002 01:06

Well, I used a linked list. And I got MEMORY LIMIT EXCEEDED. That's
the strange about this EASY problem. I use linked list, and if it
happens to have to connect each point to each other i have 1000 *1000
ints, which is quite big........ the strange here is different-> i use
char m[1000][1000] and it's all ok
I go through the array only ONCE which is 10^6 operations...... that
is quite low for the standarts..... if you want to, i'll send my
source :)) And, i get Time Limit Exceeded...... I cannot realise how
is that possible..... a very strange thing, that problem!

It's really EASY problem and linked list is O.K.

Posted by Nazarov Denis (nsc2001@rambler.ru) 18 Feb 2002 13:17

> Well, I used a linked list. And I got MEMORY LIMIT EXCEEDED. That's
> the strange about this EASY problem. I use linked list, and if it
> happens to have to connect each point to each other i have 1000
*1000
> ints, which is quite big........ the strange here is different-> i
use
> char m[1000][1000] and it's all ok
> I go through the array only ONCE which is 10^6 operations......
that
> is quite low for the standarts..... if you want to, i'll send my
> source :)) And, i get Time Limit Exceeded...... I cannot realise
how
> is that possible..... a very strange thing, that problem!

Re: It's really EASY problem and linked list is O.K.

Posted by Algorist 18 Feb 2002 18:24

Well, I asked a person who got AC ad he also told me it's OK with
linked list....... but I cannot where is the problem. It's true, I
use the STL container "list", and I get Memory Limit.... maybe Timus
is not OK with STL.................
And about the problem -> I mentioned a couple of times that it is
really EASY, and that is why I am angry-> because in the contest I
submitted it 21 times, and I got all either Memory Limit Exceeded, or
Time Limit Exceeded, while my both solutions are OK :
1. Linked list and two stacks-> I get Memory Limit...... and there is
NO WAY!!!!!! since many people got AC with a linked list.....
2. Adjacency matrix -> Time Limit........ all I do is go through te
matrix TWICE, and after that go through one stack TWICE......the
stack has max 32000 elements...., that is 2*(10^6+32000) which is
quite a small number for the standarts...... but I got TL.... too
bad...
Now I'll write a list by myself, and see if it worx.....