## 10625 - GNU = GNU'sNotUnix

Moderator: Board moderators

liux0229
New poster
Posts: 8
Joined: Thu May 20, 2004 1:30 pm
Location: China

### 10625 - GNU = GNU'sNotUnix

I've been working on problem 10625, GNU's Not Unix.
I have tried my best to let my program passed by the judge, but always it says I've got the wrong answer. (Also put a 64 bit structure in cos the problem states that the output data will be contained in a 64-bit int). I wonder if there is some special case that I have not yet considered of. So can anyone set up some test data that can cover all aspects of the problem and the answers to them so I can find out where is wrong.
Thank you very much!
Liux
neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba
Hi liux!

I solved this problem using unsigned long long type for the result, after getting several WA just because of problems printing the result.

Hope it helps...!!!
anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
Hello,
will you please describe the algorithm you have used to solve the porblem??
getting WA 5 times.
"Everything should be made simple, but not always simpler"
Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
If you're getting WA, maybe you should explain your algorithm..
anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
I have applied simulation to solve it. But, I think, there is a mathemetical solution(purely) to the problem. Would you please explain the mathematical way please??
Anupam
Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
It depends on what you mean by simulation. I consider my method a simulation.

The important note is that it doesn't matter what the actual string is, but the number of times a character appear in the input (and each time a rule is applied..).
medv
Learning poster
Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

### I get WA yet, but I know the Math

Hi!
I built a matrix m[33..126,33..126] where m[i,j] = amount of letters with ASCII code j in a rule, beginning with a letter with ASCII code i.
For example , if I had only 3 letters (A,B,C) and rules
A->ABC
B->BAAC
C->CB
then I would get matrix ((1 1 1)(2 1 1)(0 1 1)).
In each query I have a Word, a Letter and Number (of iterations).
I evaluate matr = m^Number (^ - power) in O(log Number) time, then I have matr[i,j] = amount of letters with ASCII code j that will be generated
if I would begin with letter ASCII i.

For example, input query is: ABC A 3
matr = m^3 = ((9 9 9)(12 12 12)(6 6 6))
Input string is ABC, Letter is A.
So the answer is matr[1,1] +matr[2,1]+matr[3,1] = 27.

By the way, I wrote in Pascal, and I used extended.
Is there in pascal some integer 64-bit type?
medv
Learning poster
Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

### 10625 - Why WA?

program p10625;
const
MIN = 33;MAX = 126;
type
row = array[MIN..MAX] of extended;
var
TempM,m,m1:array[MIN..MAX] of row;
inp,i,j,k,tests,rules:integer;
number,Left,Right:integer;
ch,letter:char;
s:array[MIN..MAX] of integer;
res:extended;

procedure copy(var a,b:array of row);
var
i,j:integer;
begin
for i:=0 to MAX-MIN do
for j:=MIN to MAX do
b[i,j] := a[i,j];
end;

procedure mult(a,b:array of row; var res:array of row);
var
i,j,k:integer;
s:extended;
begin
for i:=0 to MAX-MIN do
for j:=MIN to MAX do
begin
s := 0;
for k:=MIN to MAX do
s := s + a[i,k]*b[k-MIN,j];
res[i,j] := s;
end;
end;

procedure MakeOne(var m:array of row);
var
i:integer;
begin
FillChar(m,sizeof(m),0);
for i:=0 to MAX - MIN do
m[i,i+MIN] := 1;
end;

function IsZeroRow(m:array of row;RowNumber:integer):boolean;
var
i:integer;
begin
IsZeroRow := True;
for i:=MIN to MAX do
if m[RowNumber,i] > 0.0 then
begin
IsZeroRow := True; Exit;
end;
end;

begin
for i:=1 to tests do
begin
FillChar(TempM,sizeof(TempM),0);
for j:=1 to rules do
begin
while not eoln do
begin
Right := Ord(ch); TempM[Left,Right] := TempM[Left,Right] + 1;
end;
end;
for j:=1 to inp do
begin
copy(TempM,m);
for k:=MIN to MAX do
if IsZeroRow(m,k) then m[k,k] := 1;
FillChar(s,sizeof(s),0);
while ch <> ' ' do
begin
Inc(s[Ord(ch)]);
end;

MakeOne(m1);
while number > 0 do
begin
if number mod 2 = 1 then mult(m,m1,m1);
number := number div 2;
mult(m,m,m);
end;

res := 0;
for k := MIN to MAX do
res := res + s[k]*m1[k,Ord(letter)];
writeln(res:0:0);
end;
end;
end.
gawry
New poster
Posts: 19
Joined: Fri Aug 02, 2002 5:54 pm
I think it was rather runtime error than a real wrong answer.

Code: Select all

``````program p10625;
const
MIN = 33;MAX = 126;
type
row = array[MIN..MAX] of int64;
matrix = array[MIN..MAX] of row;
var
TempM,m,m1:matrix;
inp,i,j,k,tests,rules:integer;
number,Left,Right:integer;
ch,letter:char;
s:array[MIN..MAX] of integer;
res:int64;

procedure copy(var a,b:matrix);
var
i,j:integer;
begin
for i:=MIN to MAX do
for j:=MIN to MAX do
b[i,j] := a[i,j];
end;

procedure mult(a,b:matrix; var res:matrix);
var
i,j,k:integer;
s:int64;
begin
for i:=MIN to MAX do
for j:=MIN to MAX do
begin
s := 0;
for k:=MIN to MAX do
s := s + a[i,k]*b[k,j];
res[i,j] := s;
end;
end;

procedure MakeOne(var m:matrix);
var
i:integer;
begin
FillChar(m,sizeof(m),0);
for i:=MIN to MAX do
m[i,i] := 1;
end;

function IsZeroRow(m:matrix;RowNumber:integer):boolean;
var
i:integer;
begin
IsZeroRow := True;
for i:=MIN to MAX do
if m[RowNumber,i] > 0 then
IsZeroRow := False;
end;

begin
for i:=1 to tests do
begin
FillChar(TempM,sizeof(TempM),0);
for j:=1 to rules do
begin
while not eoln do
begin
Right := Ord(ch); TempM[Left,Right] := TempM[Left,Right] + 1;
end;
end;
for k:=MIN to MAX do
if IsZeroRow(TempM,k) then TempM[k,k] := 1;
for j:=1 to inp do
begin
copy(TempM,m);
FillChar(s,sizeof(s),0);
while ch <> ' ' do
begin
Inc(s[Ord(ch)]);
end;

MakeOne(m1);
while number > 0 do
begin
if number mod 2 = 1 then mult(m,m1,m1);
number := number div 2;
mult(m,m,m);
end;

res := 0;
for k := MIN to MAX do
res := res + m1[k,Ord(letter)]*s[k];
writeln(res);
end;
end;
end.
``````
Now it should work but it will be also a little bit too slow, mostly because I have changed extended to int64 - extended give wrong answer for this test case:

Code: Select all

``````1
1
A->AA
1
A A 62
``````
So maybe you should think about another method (hint - n<=10000 so it may be a really simple one).
misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

### Re: I get WA yet, but I know the Math

medv wrote:By the way, I wrote in Pascal, and I used extended.
Is there in pascal some integer 64-bit type?
Freepascal compiler supports the types int64 (64-bit signed int) and qword (64-bit unsigned), if I recall correctly.
liux0229
New poster
Posts: 8
Joined: Thu May 20, 2004 1:30 pm
Location: China

I used simulation and it's much quicker than the math way metioned above, which involves too many wasted multiplications with 0
Hedge
New poster
Posts: 11
Joined: Thu Jul 29, 2004 8:59 pm

### 10625 GNU = GNU'sNotUnix

Hello. I am trying to solve problem 10625 but i got wa a couple of times and cant figure out why. I use a simulating approach. I store the current number of each printable char and in every recursion step i add for every rule the number of the the char which i substitute to the number of the chars who take the place of it. I took care that i substitute all rules at one time and i use unsigned long long int.
Is there anything i havent took care or any tricky input, especialy in the input format?
Anyone have some tricky test cases?

Hedge
Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
There's already a discussion found here:

http://online-judge.uva.es/board/viewto ... ight=10625
Hedge
New poster
Posts: 11
Joined: Thu Jul 29, 2004 8:59 pm
I read this thread already, but it wasnt realy useful for me, because the discussion went in some other directions. So i started a new thread.
Hedge
New poster
Posts: 11
Joined: Thu Jul 29, 2004 8:59 pm
Hello. I am trying to solve problem 10625 but i got wa a couple of times and cant figure out why. I use a simulating approach. I store the current number of each printable char and in every recursion step i add for every rule the number of the the char which i substitute to the number of the chars who take the place of it. I took care that i substitute all rules at one time and i use unsigned long long int.
Is there anything i havent took care or any tricky input, especialy in the input format?
Anyone have some tricky test cases?