OJ Board

Does someone have some input/output for this problem?
I've tested my solution with many case and it goes ok, but I just got WA.

PS: My output for 0 is two blank lines...

JPFarias
jpfarias@lcc.ufrn.br

check your output has trailing space.

Try this input:

-x8y+9x3-1+y
x5y+1+x3
x+1
x+y+1
x4+y7+xy56+100x3+100x3+100x3+75y84x23+y23
x+y+x2y2+x3y3
y3-3y2+3y-1
1+y+y2+y3+y4+y5+y6+y7+y8+y9+y10+y11+y12+y13+y14+y15+y16+y17+y18+y19+y20+y21+y22
100x100+100y100
100x100-100y100
57x-57x+yx34-45x+100x100-24x35+75x3y34
57x-57x+yx34-45x+100x100-24x35+75x3y34
x3+75y3
12x-100y
100x-1+50y+12x34y60+56x56y56-x2y6
25
45x45+68xy35-y12x25+100y-x25+y4x25-y100
x2-y23x24+y12x25
32x19y85-64x18y85+32x17y85-x3+x3y58+2x2-2x2y58-x+xy58
x+2x2+3x3+4x4+5x5+6x6+7x7+8x8+9x9+10x10+11x11+12x12+13x13+14x14+15x15+16x16+x50
#

the output should be:

13 2 11 8 6 5 5 2 3 3
-x y - x y + 8x y + 9x - x y + x y + 8x + x y - 1 + y
2
x + 2x + xy + 1 + y
26 87 25 86 24 84 23 85 7 3 6 2 6 3 5 5 2 4 4 4 59 3 3 10 3 26 3 58 2 9 2 25 2 56 7 23 57 8 24
75x y + 75x y + 75x y + 75x y + x y + x y + 300x y + x + 300x y + 300x + x y + x y + 300x y + x y + x y + x y + x y + x y + x y + xy + xy + xy + y + y
2 23 24 25
- + 2y - y + y - 2y + y
200 200
10000x - 10000y
200 135 134 103 34 101 70 69 68 2 38 34 37 35 36 35 6 68 4 34 2
10000x - 4800x + 200x y + 15000x y - 9000x + 576x - 48x y + x y - 3600x y + 150x y + 2160x - 90x y + 5625x y - 6750x y + 2025x
4 3 3 4
12x - 100x y + 900xy - 7500y
56 56 34 60 2 6
1400x y + 300x y - 25x y + 2500x - 25 + 1250y
70 12 69 23 50 12 50 16 50 24 49 23 49 27 49 35 47 27 27 4 27 12 26 47 25 13 25 58 25 112 24 24 24 123 3 35 2 2 100
45x y - 45x y - x y + x y - x y + x y - x y + x y + 45x - x + x y - x y + 68x y + 100x y - 68x y - x y - 100x y + x y + 68x y + 100x y - x y
69 85 68 85 67 85 53 53 58 52 52 58 51 51 58 35 85 34 85 19 19 58 18 18 58 18 85 2 2 58
32x y - 64x y + 32x y - x + x y + 2x - 2x y - x + x y + 512x y - 544x y - 16x + 16x y + 17x - 17x y + 32x y - x + x y

Let

I think you got it wrong. Maximum exponent is a^100 * a^100 = a^(100 + 100) = a^200, i.e. 200.
I've solved it using one array 100*100 for a term with x (possibly y), and one array of 100 for a term with only y.

Maxim

I can't believe it... You're right, of course... Man, I should sleep a little more...
By the way, thanks. You saved me a lot of headaches

Is it safe to assume this problem is an implementation of the FFT? I know there are other (easier) ways to do this, but is the input small enough to warrant a simple solution? If the input is half large, and speed is an issue, then the FFT is the way to go, I'm sure.

FFT on two-dimensional funcions? How do you see that?

Hmm.. Good point.

So not another hint. My "simple" solution got 0.000s.

Well I solved it using "traditional" methods and it ran really fast.

Sometimes I overthink the problems and dig myself into a hole. I guess part of the experience gained doing such problems is knowing when to worry about efficiency and when to just solve it Q&D.

I am not sure when I should add the space between the signs. for that sample output above i do not understand why they didnt have a space between +x^3y

also in the input can you have something like:
0
0
or
x-x
y-y

It's a typo. There should be a space there.

As for your input, I believe they are both valid, and my program returned 0 for both.

Hi people. Can anyone help me. What is wrong with my program? I get always correct answers on my tests. I've done this problem even in USACO - ace.delos.com. But here I get WA.

[pascal]program The_Errant_Physicist;

const
num: array[0..200] of string[3] = ('0','1','2','3','4','5','6','7','8','9','10',
'11','12','13','14','15','16','17','18','19','20',
'21','22','23','24','25','26','27','28','29','30',
'31','32','33','34','35','36','37','38','39','40',
'41','42','43','44','45','46','47','48','49','50',
'51','52','53','54','55','56','57','58','59','60',
'61','62','63','64','65','66','67','68','69','70',
'71','72','73','74','75','76','77','78','79','80',
'81','82','83','84','85','86','87','88','89','90',
'91','92','93','94','95','96','97','98','99','100',
'101','102','103','104','105','106','107','108','109','110',
'111','112','113','114','115','116','117','118','119','120',
'121','122','123','124','125','126','127','128','129','130',
'131','132','133','134','135','136','137','138','139','140',
'141','142','143','144','145','146','147','148','149','150',
'151','152','153','154','155','156','157','158','159','160',
'161','162','163','164','165','166','167','168','169','170',
'171','172','173','174','175','176','177','178','179','180',
'181','182','183','184','185','186','187','188','189','190',
'191','192','193','194','195','196','197','198','199','200');

type
Term = record
c: Integer;
e: array['x'..'y'] of Integer;
end;
Polynomial = record
n: Integer;
t: array[1..200] of Term;
end;

var
u,v: string;
pa,pb,pc: Polynomial;

procedure getterms(a: string; var b: Polynomial);
var
i,l,s,c,e: Integer;
t: Char;
begin
l:=length(a);
b.n:=0; i:=1;
while i<=l do
begin
inc(b.n);
s:=1;
while a in ['+','-'] do
begin
if a='-' then s:=-s;
inc(i);
end;
c:=0;
if a in ['0'..'9'] then
begin
while (a in ['0'..'9'])and(i<=l) do
begin
c:=c*10+ord(a)-48;
inc(i);
end;
c:=c*s;
end else
begin
c:=s;
end;
b.t[b.n].c:=c;
while (a in ['x','y'])and(i<=l) do
begin
t:=a;
inc(i);
if (a in ['0'..'9'])and(i<=l) then
begin
e:=0;
while (a in ['0'..'9'])and(i<=l) do
begin
e:=e*10+ord(a)-48;
inc(i);
end;
end else e:=1;
b.t[b.n].e[t]:=e;
end;
end;
end;

procedure swap(var a,b: Term);
var
c: Term;
begin
c:=a; a:=b; b:=c;
end;

procedure multiply(a,b: Polynomial; var c: Polynomial);
var
i,j,k: Byte;
t: Term;
begin
c.n:=0;
for i:=1 to a.n do
for j:=1 to b.n do
begin
fillchar(t,sizeof(t),0);
t.c:=a.t[i].c*b.t[j].c;
t.e['x']:=a.t[i].e['x']+b.t[j].e['x'];
t.e['y']:=a.t[i].e['y']+b.t[j].e['y'];
k:=c.n;
while (k>0)and((t.e['x']<>c.t[k].e['x'])or(t.e['y']<>c.t[k].e['y'])) do dec(k);
if k>0 then
begin
c.t[k].c:=c.t[k].c+t.c;
end else
begin
inc(c.n);
k:=c.n;
c.t[k]:=t;
while k>1 do
begin
if (c.t[k].e['x']>c.t[k-1].e['x'])or((c.t[k].e['x']=c.t[k-1].e['x'])and(c.t[k].e['y']<c.t[k-1].e['y'])) then swap(c.t[k],c.t[k-1]) else break;
dec(k);
end;
end;
end;
end;

procedure len(x: Integer; var l: Byte);
begin
if x=0 then l:=0 else
if x<10 then l:=1 else
if x<100 then l:=2 else
if x<1000 then l:=3 else
if x<10000 then l:=4 else l:=5;
end;

procedure print(a: Polynomial);
var
i,j,k,l,l1,l2: Byte;
s,z,u: string;
begin
s:='';
z:='';
k:=1;
while (a.t[k].c=0)and(k<=a.n) do inc(k);
if k<=a.n then
for i:=1 to a.n do
if a.t[i].c<>0 then
begin
if (i=k)and(a.t[i].c<0) then
begin
s:=s+' ';
z:=z+'-';
end else
if i>k then
begin
s:=s+' ';
if a.t[i].c>0 then z:=z+' + ' else z:=z+' - ';
end;
if (abs(a.t[i].c)>1)or((abs(a.t[i].c)=1)and(a.t[i].e['x']=0)and(a.t[i].e['y']=0)) then
begin
len(abs(a.t[i].c),l);
for j:=1 to l do s:=s+' ';
str(abs(a.t[i].c),u);
z:=z+u;
end;
if a.t[i].e['x']>0 then
begin
s:=s+' ';
z:=z+'x';
if a.t[i].e['x']>1 then
begin
s:=s+num[a.t[i].e['x']];
len(a.t[i].e['x'],l);
for j:=1 to l do z:=z+' ';
end;
end;
if a.t[i].e['y']>0 then
begin
s:=s+' ';
z:=z+'y';
if a.t[i].e['y']>1 then
begin
s:=s+num[a.t[i].e['y']];
len(a.t[i].e['y'],l);
for j:=1 to l do z:=z+' ';
end;
end;
end;
l1:=length(s);
while (s[l1]=' ')and(l1>0) do
begin
delete(s,l1,1);
dec(l1);
end;
l2:=length(z);
while (z[l2]=' ')and(l2>0) do
begin
delete(z,l2,1);
dec(l2);
end;
if l1<l2 then
begin
writeln(s,'':l2-l1);
writeln(z);
end else
begin
writeln(s);
writeln(z,'':l1-l2);
end;
end;

begin
{$IFNDEF ONLINE_JUDGE}
assign(input,'126.in'); reset(input);
assign(output,'126.out'); rewrite(output);
{$ENDIF}
readln(u);
while u='' do readln(u);
while u[1]<>'#' do
begin
readln(v);
while v='' do readln(v);
fillchar(pa,sizeof(pa),0);
fillchar(pb,sizeof(pb),0);
fillchar(pc,sizeof(pc),0);
getterms(u,pa);
getterms(v,pb);
multiply(pa,pb,pc);
print(pc);
readln(u);
while u='' do readln(u);
end;
{$IFNDEF ONLINE_JUDGE}
close(input); close(output);
{$ENDIF}
end.[/pascal]

Thanks in advance.

hi there,

my code ran and i am getting a "wrong answer" result. i can't see what i have done wrong as my output for the sample input is almost identical (html seems to have cut the whitespace from the sample output so i cannot check, and there appears to be a trailing space in the sample, which is not in the description). i have also tried quite a few of my own inputs... please help!

i tried to solve this in the most obvious way; i created a 2D array of ints, the 1st index denoting X and the 2nd Y. the actual value is then the coefficient; so poly[3][2]=2 would mean 2x^3y^2. i then created 3 main functions to deal with this object; a parser to convert stdin into such an array, a multiplication function, and a print function.

anyone got any more test cases and expected outputs? perhaps i have a subtle bug...

you can see my source code from my webpage
http://fommil.homeunix.org/~samuel/file ... icist.html[/url][/code]