10157 - Expressions

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

Moderator: Board moderators

User avatar
Yu Fan
New poster
Posts: 26
Joined: Thu Nov 13, 2003 3:52 am

Post by Yu Fan » Wed Jun 22, 2005 6:17 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~ :P

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

bigint multiplication

Post by lantimilan » Tue Nov 20, 2007 5:21 pm

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

Post by ntoskr » Fri May 01, 2009 7:04 am

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

Post by Dominik Michniewski » Sat Mar 26, 2011 7:17 pm

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

Post by crip121 » Sun Mar 27, 2011 1:38 pm

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

Post by DD » Tue Feb 19, 2013 5:18 am

You can tried to build table offline to pass this :oops:
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

Post by chipchip3412 » Tue Jul 23, 2013 9:17 am

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10157 - Expressions

Post by brianfry713 » Wed Jul 24, 2013 1:59 am

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

Post by chipchip3412 » Wed Jul 24, 2013 6:39 am

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

Post Reply

Return to “Volume 101 (10100-10199)”