10625 - GNU = GNU'sNotUnix

All about problems in Volume 106. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10625 - GNU = GNU'sNotUnix

Post by liux0229 »

:wink: 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

Post by neno_uci »

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...!!! :D
anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam »

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:

Post by Larry »

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:

Post by anupam »

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:

Post by Larry »

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

Post by medv »

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?

Post by medv »

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
readln(tests);
for i:=1 to tests do
begin
FillChar(TempM,sizeof(TempM),0);
readln(rules);
for j:=1 to rules do
begin
read(ch); Left := Ord(ch);read(ch);read(ch);
while not eoln do
begin
read(ch);
Right := Ord(ch); TempM[Left,Right] := TempM[Left,Right] + 1;
end;
readln;
end;
readln(inp);
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);
read(ch);
while ch <> ' ' do
begin
Inc(s[Ord(ch)]);
read(ch);
end;
read(letter);read(ch);
readln(number);

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

Post by gawry »

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

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

Post by misof »

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

Post by liux0229 »

:lol:
OK...Now I get passed. Thank all of you for your advices
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

Post by Hedge »

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?
Thank you in advance,

Hedge
Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry »

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

Post by Hedge »

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

Post by Hedge »

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?
Post Reply

Return to “Volume 106 (10600-10699)”