## 529 - Addition Chains

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

Moderator: Board moderators

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

### 529 - Addition Chains

I can't understand why this program gets Accepted

I use a such algorithm:

1. Consider that sequence <a0,a1,..,am> is good if and only if it is the answer for N = am

2. If sequence <a0,a1,..,am,a(m+1)> is good then the sequence <a0,a1,..,am> is also good.

So, I find all good sequences with length 1, then 2, then 3 etc.

The maximum length of good sequences (for N=1..10000) is 18 (Anyone who get Accepted can said so). There are about 2000000 good sequences of length 17.

But, in my program I consider
maximum length = 15
maximum number of good sequences = 50000

and it get Accepted

I want to get Accepted with correct program!
Can anyone help me?

[pascal]Program p529;

Const MaxD = 15;
MaxN = 10000;
MaxComb = 50000;

Type ChainType = Array[0..MaxD]of ShortInt;

Var Inf : Array[1..MaxN]of ChainType;
NewT,OldT : Array[1..MaxComb]of ChainType;
nt,ot : Integer;
N,i,j : Integer;

Procedure Rec(Step,WT : Integer);
Var i,j,k,p : Integer;
begin
for i:=Step downto 1 do
for j:=Step downto i do begin
p:=OldT[WT,i]+OldT[WT,j];
if (p>OldT[WT,Step]) And (p<=MaxN) then
if Step+1<Inf[p,0] then begin
for k:=1 to Step do Inf[p,k]:=OldT[WT,k];
Inf[p,Step+1]:=p;
Inf[p,0]:=Step+1;
end;
end;
end;

Procedure Rec2(Step,WT : Integer);
Var i,j,k,p : Integer;
begin
for i:=Step downto 1 do
for j:=Step downto i do begin
p:=OldT[WT,i]+OldT[WT,j];
if (p>OldT[WT,Step]) And (p<=MaxN) then
if Step+1=Inf[p,0] then begin
if nt=MaxComb then exit;
nt:=nt+1;
for k:=1 to Step do NewT[nt,k]:=OldT[WT,k];
NewT[nt,Step+1]:=p;
end;
end;
end;

begin
Inf[1][0]:=1;
Inf[1][1]:=1;
for i:=2 to MaxN do Inf[i,0]:=100;

ot:=1;
OldT[1]:=Inf[1];
for i:=2 to MaxD do begin
nt:=0;
for j:=1 to ot do Rec(i-1,j);
if i<MaxD then for j:=1 to ot do Rec2(i-1,j) else Break;
for j:=1 to nt do OldT[j]:=NewT[j];
ot:=nt;
end;

While True do begin
if N=0 then Break;
Write('1');
for i:=2 to Inf[N][0] do Write(' ',Inf[N]);
Writeln;
end;
end.[/pascal]

tonyk
New poster
Posts: 7
Joined: Mon May 05, 2003 5:11 pm

### 529 Addition Chains Help!!

I don't know how to slove this problem.
Anyone give me some hints??
Or give me a correct program(written in C or C++)
Many thanks!!

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore
I'm not sure about others, but I used IDA* with an obvious heuristic...

Learning poster
Posts: 57
Joined: Sun Sep 29, 2002 12:00 pm
Location: in front of the monitor :-)
Contact:
junjieliang, thank you for your very useful hint. i got AC in 0.029 sec time. however, there are much better time than that. did someone use anyother technique?

junjieliang, have you used IDA* for any other prob on this site?

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore
Well, I just started learning IDA*, so I've not used it on any other problems yet.

Ronald29
New poster
Posts: 15
Joined: Sat May 24, 2003 3:57 am
Find all posibility using recursive. to find the minimum, try to find it on each level, don't go to the next level of recursive if all value in one level not checked. It's the most simple algorithm I can found, if anyone know another algorithm please let me know. thx, hope this can help you...tonyk

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:
junjieliang wrote:I'm not sure about others, but I used IDA* with an obvious heuristic...
Hi
What is IDA* please ? Could anyone give me a good URL describing it ?
(isn't it that sort of Alpha and Beta cut ?)

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:
Hi.
I finally found what is ID (Incremental Deepening). I used it, and have a fine program for n <= 100 (wich makes the chain length be 9).
But with the new limit, n <= 10000, I can't solve it !! It's far too slow... I stop my deepening as soon as the new element to insert in the chain is > n. Is there a better condition ?

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:
Hi
I don't understand why you consider your program as wrong... If your program gets AC with your limits, this means that there are not cases longer than 15 in the sample input. So, if you change your constants, it should still work, because it will find the answer with length 15 before having to try length 18.
Or is there something that I did not understand in your explanation (sorry, I'm not familiar with pascal).

(BTW : I'm still stuck with this problem, TLE, though using incremental deepening. Any idea ?

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore
Hi,

I think what you're saying is iterative deepening search instead, where you increase the limit by a constant value (eg 1) after every search to go deeper.

IDA* is slightly different. Instead of adding 1, you use a heuristic to guess how much to increase by. This heuristic should not overestimate however, else the algorithm will be wrong.

Hope that helps.

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
hey, check out again, your program gets wa..
--
anupam
"Everything should be made simple, but not always simpler"

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:
junjieliang wrote:Hi,

I think what you're saying is iterative deepening search instead, where you increase the limit by a constant value (eg 1) after every search to go deeper.

IDA* is slightly different. Instead of adding 1, you use a heuristic to guess how much to increase by. This heuristic should not overestimate however, else the algorithm will be wrong.

Hope that helps.
Mmmm.... I guess I see the global meaning of it all, but I don't see wich euristic I could use. I'll try to think of it. If I'm still stuck by tomorow, could you please give me a hint ?

But, anyway, even if I can "guess" what the length of the chain is (should be >= ln(n) with ln in basis 2, I think), the search in between the chain is still veeery long, isn't it ?

This is the first time I meet that kind of algorithm (always used simple stupid BFS)...

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:
Hi

After a whole night trying to find the heuristic mentionned above, I'm ashamed to confess that I don't see it
Could you please give me a hint ? I'm stuck and it's prettily annoying me ... :/
Thanks !

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore
You're right about the heuristic having something to do with log base 2. Assume that in your search the last number is n, and your target is t. Then an estimate of the number of steps more that you need will be log(t/n), where the log base 2 of course...

To shorten the runtime, you can break early with the help of the heuristic. Say you're at depth 5, and the heuristic says there are at least 3 steps more. If your upper bound so far is less than 8 (5 + 3), then you know there's no way you can get an answer, and you can just break out of the search early.

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:
Thank you

I'll try this as soon as I'll have recuperated from SWERC (it was today, and I'm a bit dead)...

Thank you