## 10157 - Expressions

Moderator: Board moderators

Yu Fan
New poster
Posts: 26
Joined: Thu Nov 13, 2003 3:52 am
wow~
i've thought about it for a long~ time but cannot construct a correct recursive function before i couldn't avoid counting identical expressions

anyway, thank you~ lantimilan
New poster
Posts: 11
Joined: Sat Mar 19, 2005 11:12 am
Location: HKU
Contact:

### bigint multiplication

I was unable to figure out the formula without multiplication. But I would like to confirm that the recurrence with O(n*d) multiplication still can get you to AC, but the trick is in integer multiplication.

I learned this from misof, who pointed out that you can use vector<int> to store large integers. Then you can multiply by blocks of 10^9 also.

One might try to imlement fast integer mult algorithm like the O(n^log2(3)), Karatsuba's algorithm or even FFT, but those complicated algorithms may not help this problem as our integer is not large enough to warrant the constant overhead -- This is Unix, any explanatory error message is seen as a sign of weakness

ntoskr
New poster
Posts: 1
Joined: Fri May 01, 2009 6:45 am

### Re: 10157 - Expressions

The recurrence I found is not efficient enough. Generating the whole 150*150 bignum table takes 22sec on my computer. I used vector<int> to implement bignum plus and mul, by blocks of 10^9 as lantimilan mentioned. I also tried memorization to avoid calculating unused cells for a given set, but there is no way I can get under 10sec limit.

how to find a more efficient recurrence?

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

### Re: 10157 - Expressions

Could anyone tell me if my IO is correct ??

Input:

Code: Select all

``````32 2
32 4
32 6
32 8
32 10
32 12
32 14
32 16
32 18
32 20
32 22
``````
Output:

Code: Select all

``````1
4782969
15411789
24623433
25725681
19567089
11434365
5285745
1961825
587305
141165
``````
Thank you all for help :)
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

crip121
New poster
Posts: 29
Joined: Tue Jul 08, 2008 9:04 pm

### Re: 10157 - Expressions

Code: Select all

``````32767
5828185
8558854
2937932
404984
22536
403
1
0
0
0``````

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

### Re: 10157 - Expressions

You can tried to build table offline to pass this ntoskr wrote:The recurrence I found is not efficient enough. Generating the whole 150*150 bignum table takes 22sec on my computer. I used vector<int> to implement bignum plus and mul, by blocks of 10^9 as lantimilan mentioned. I also tried memorization to avoid calculating unused cells for a given set, but there is no way I can get under 10sec limit.

how to find a more efficient recurrence?
Have you ever...
• Wanted to work at best companies?
• Struggled with interview problems that could be solved in 15 minutes?
• Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

chipchip3412
New poster
Posts: 7
Joined: Mon Jun 10, 2013 2:14 pm

### Re: 10157 - Expressions

WA again and again Please help me.
My code:

Code: Select all

``````{\$mode objfpc}
uses math;
type
bignum=record
size: longint;
a: array[0..501] of int64;
end;
var
i,j,k,n,d: longint;
dp: array[0..151,0..151] of bignum;

operator :=(x: longint): bignum;
begin
fillchar(result.a,sizeof(result.a),0); result.size:=1; result.a:=x;
end;

operator +(x,y: bignum): bignum;
var i: longint; tmp: int64;
begin
result.size:=max(x.size,y.size); tmp:=0;
for i:=1 to result.size do
begin
inc(tmp,x.a[i]+y.a[i]); result.a[i]:=tmp mod 1000000000; tmp:=tmp div 1000000000;
end;
if tmp>0 then
begin
inc(result.size); result.a[result.size]:=tmp;
end;
end;

operator -(x,y: bignum): bignum;
var i: longint; tmp: int64;
begin
result.size:=x.size; tmp:=0;
for i:=1 to result.size do
begin
inc(tmp,x.a[i]-y.a[i]); result.a[i]:=(tmp+1000000000) mod 1000000000;
if tmp<0 then tmp:=-1 else tmp:=0;
end;
while (result.size>1) and (result.a[result.size]=0) do dec(result.size);
end;

operator *(x,y: bignum): bignum;
var
i,j: longint; tmp1: int64;
tmp: bignum;
begin
result:=0;
for i:=1 to y.size do
begin
fillchar(tmp.a,sizeof(tmp.a)*(i-1),0);
tmp.size:=x.size+i-1; tmp1:=0;
for j:=i to tmp.size do
begin
inc(tmp1,x.a[j-i+1]*y.a[i]); tmp.a[j]:=tmp1 mod 1000000000; tmp1:=tmp1 div 1000000000;
end;
if tmp1>0 then
begin
inc(tmp.size); tmp.a[tmp.size]:=tmp1;
end;
result:=result+tmp;
end;
end;

var
s,tmp: ansistring;
i: longint;
begin
s:='';
for i:=1 to x.size do
begin
str(x.a[i],tmp);
while (i<x.size) and (length(tmp)<9) do tmp:='0'+tmp;
s:=tmp+s;
end;
writeln(s);
end;

function get(d,n: longint): bignum;
var
i: longint;
begin
if n=0 then exit(1);
if d=0 then exit(0);
if dp[d,n].size=0 then
begin
dp[d,n]:=0;
for i:=0 to n-1 do dp[d,n]:=dp[d,n]+get(d-1,i)*get(d,n-i-1);
end;
exit(dp[d,n]);
end;

begin
//  assign(input,'chip.in'); reset(input); assign(output,'chip.out'); rewrite(output);
for i:=1 to 150 do
for j:=1 to 150 do dp[i,j].size:=0;
while not eof do
begin
if (n mod 2=1) or (n<d*2) then writeln(0) else
if (n=d*2) or (d=1) then writeln(1) else
if n=d*2+2 then writeln(n-3) else answer(get(d,n div 2)-get(d-1,n div 2));
end;
//  close(input); close(output);
end.
``````
Is my I/O correct for this test case?
Input:

Code: Select all

``````1
300 75
``````
Output:

Code: Select all

``````288326485174850821398164354817718717716005785198152613184829833272394220
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10157 - Expressions

That I/O is correct, and I also checked your code against all possible inputs and they match my AC C++ code.
I'm not an expert on Pascal.
Check input and AC output for thousands of problems on uDebug!

chipchip3412
New poster
Posts: 7
Joined: Mon Jun 10, 2013 2:14 pm

### Re: 10157 - Expressions

Yeah, that's strange, I've tried all the tests given here but still WA on both UVA and PC Thank you anyway, could you take a look at http://online-judge.uva.es/board/viewto ... 6&start=45? ? Same problem 