10157 - Expressions

[Yu Fan]

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]

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

[ntoskr]

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]

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

[crip121]

Code: Select all

32767
5828185
8558854
2937932
404984
22536
403
1
0
0
0

[DD]

You can tried to build table offline to pass this

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?

[chipchip3412]

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[1]:=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[1],sizeof(tmp.a[1])*(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;

procedure answer(x: bignum);
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
    readln(n,d);
    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]

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.

[chipchip3412]

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