529  Addition Chains
Moderator: Board moderators
529  wrong judge input!?
The problem states:
"The input file will contain one or more test cases. Each test case consists of one line containing one integer n (1 <= n <= 100). Input is terminated by a value of zero (0) for n. "
I'm trying to apply BFS to this problem implemented with a queue which is ok for n <= 100. But i was getting MLE. So a decided to probe the judge for n > 100 and gotcha!
this code gives TLE:
[cpp]
int main()
{
while (cin >> n, n)
{
while (n == 200); //this line gets TLE!!!
}
return 0;
}
[/cpp]
Is my concept wrong?
Thanx in advance.
 N
"The input file will contain one or more test cases. Each test case consists of one line containing one integer n (1 <= n <= 100). Input is terminated by a value of zero (0) for n. "
I'm trying to apply BFS to this problem implemented with a queue which is ok for n <= 100. But i was getting MLE. So a decided to probe the judge for n > 100 and gotcha!
this code gives TLE:
[cpp]
int main()
{
while (cin >> n, n)
{
while (n == 200); //this line gets TLE!!!
}
return 0;
}
[/cpp]
Is my concept wrong?
Thanx in advance.
 N

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
From the yellow exclamation mark:
19/04/01, Warning: The new upper limit for n is 10000
Judges haven't migrated yet this to the HTML. Please read always such things, like exclamations near the problem description
Best regards
DM
PS. I think, that in the near future this thing should be migrated to HTML, but as you should know, judges have a lot of work and lack of time
19/04/01, Warning: The new upper limit for n is 10000
Judges haven't migrated yet this to the HTML. Please read always such things, like exclamations near the problem description
Best regards
DM
PS. I think, that in the near future this thing should be migrated to HTML, but as you should know, judges have a lot of work and lack of time
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)
Born from ashes  restarting counter of problems (800+ solved problems)

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
It's a standard problem of many of us I think that best way is to have own copy of problems and update it self or using www part of judge with problems
So you are next But don't worry  everything will be OK
Best regards
DM
So you are next But don't worry  everything will be OK
Best regards
DM
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)
Born from ashes  restarting counter of problems (800+ solved problems)
529  How can I reduce the search time
Hello:
I tried to solve this problem in IDS but but my IDS solution is
poor. It takes a lot of time to generate the answers for 1 to 10000
numbers. I tried my best to find out a process for reducing the
search space, but I failed.
Could anyone tell me, how can I reduce the search space in IDS?
Or is it possible to solve this problem in BFS.
If anyone explain any process then it will be a great help for me.
I tried to solve this problem in IDS but but my IDS solution is
poor. It takes a lot of time to generate the answers for 1 to 10000
numbers. I tried my best to find out a process for reducing the
search space, but I failed.
Could anyone tell me, how can I reduce the search space in IDS?
Or is it possible to solve this problem in BFS.
If anyone explain any process then it will be a great help for me.
ids should work..
This problem can be easily solved using IDS.. but you have to do appropriate prunning.
At each step, consider the maximum number you can make at the last depth.
For example:
if you currently have 1 2 3 , then the highest number you can make at the 6th depth( let that be the last depth) is 3 * 2^3 = 24 and if your target number is more than 24 then there is no need to proceed through this branch and you can easily prune at this point.
I applied the above approach and it got AC.
Hope it helps.
At each step, consider the maximum number you can make at the last depth.
For example:
if you currently have 1 2 3 , then the highest number you can make at the 6th depth( let that be the last depth) is 3 * 2^3 = 24 and if your target number is more than 24 then there is no need to proceed through this branch and you can easily prune at this point.
I applied the above approach and it got AC.
Hope it helps.
529addition chains
I know a great deal was said here about 529, where,in particular,IDA*(by the way, can anyone give me good URL about IDA*,IDS and the like?)was mentioned, and so on.
I figured it out that m>=ln(n)(base 2) neccessarily, but this and all else
that I derived from this appears to be insufficient!(the fact is, it got PE(i.e. accepted), but in 0.179CPU),but I still see it should be tweaked here and there or performed in other way. Please,help,fellows!
I figured it out that m>=ln(n)(base 2) neccessarily, but this and all else
that I derived from this appears to be insufficient!(the fact is, it got PE(i.e. accepted), but in 0.179CPU),but I still see it should be tweaked here and there or performed in other way. Please,help,fellows!
Last edited by serur on Thu Oct 09, 2008 9:47 am, edited 2 times in total.
529 going runtime error,plz why
I'm getting RE in this following code...
sample inputoutput is expected...
My code here
sample inputoutput is expected...
My code here
Code: Select all
#include<stdio.h>
long x[105];
long result[105][50];
void bcktrking(long s,long k,long N)
{
x[k] = s;
long stack[50];
long top = 0,t,p;
long i,j,temp;
if(k>=result[N][0])
return;
for(i = 0;i<=k;i++)
for(j = 0;j<=k;j++)
{
temp = x[i]+x[j];
if(s >= temp temp>N)
continue;
for(t = 0;t<top;t++)
if(stack[t] == temp)
break;
if(t!=top)
continue;
for(p = 0;p<=k;p++)
if(stack[p] == temp)
break;
if(p != k+1)
continue;
stack[top++] = temp;
}
if(s == N)
{
if(result[N][0]<k)
return;
for(i = 0; i<=k ; i++)
result[N][i] = x[i];
result[N][0] = k;
}
else
{
for(i = top1;i>=0;i)
bcktrking(stack[i],k+1,N);
}
}
main()
{
long N,i;
for(i = 1;i<=100;i++)
{
result[i][0] = 150;
bcktrking(1,1,i);
}
//freopen("c:\in.txt","r",stdin);
//freopen("c:\out.txt","w",stdout);
while(1)
{
scanf("%ld",&N);
if(N == 0)
break;
for(i = 1; i<result[N][0] ; i++)
printf("%ld ",result[N][i]);
printf("%ld\n",N);
}
return 0;
}

 Learning poster
 Posts: 76
 Joined: Thu Mar 13, 2003 5:12 am
 Location: Russia
what da ... is this?
I am aggravated. what da ... is this nonsence with java?
I was struggling with this vector thing replacing add by addElement and all this bullshit and finally I got a message like this
I was struggling with this vector thing replacing add by addElement and all this bullshit and finally I got a message like this
for program for 529. I am not intending to say this is the best code ever. But this message is just enraging for its informational cost is zero. What is wrong with this?Here are the compiler error messages:
/tmp/ccqwa4vumain.o: In function `main':
/tmp/ccqc0qmBmain.i(.text+0x12): undefined reference to `_CL_4Main'
collect2: ld returned 1 exit status
Code: Select all
package src;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.Vector;
class Main
{
private static final int MAX_ITERATION = 10000;
Vector m_answers = null;
Vector m_sequences_sorted_by_lenth = null;
int m_test_count = 1;
static String ReadLn (int maxLg) // utility function to read from stdin
{
byte lin[] = new byte [maxLg];
int lg = 0, car = 1;
try
{
while (lg < maxLg)
{
car = System.in.read();
if ((car < 0)  (car == '\n')  (car == ' ')) break;
lin [lg++] += car;
}
}
catch (IOException e)
{
return (null);
}
if ((car < 0) && (lg == 0)) return (null); // eof
return (new String (lin, 0, lg));
}
StringTokenizer GetTokens()
{ String input;
if((input = Main.ReadLn (255)) == null) return (null);
return new StringTokenizer (input);
}
int ReadInt()
{
//return m_test_count++ % (MAX_ITERATION + 1);
StringTokenizer strToken = GetTokens();
return Integer.parseInt(strToken.nextToken());
}
String ReadString()
{ return Main.ReadLn (255);
}
public static void main (String args[]) // entry point from OS
{
Main myWork = new Main(); // create a dinamic instance
myWork.Begin(); // the true entry point
return;
}
void Begin()
{
int n;
while (true)
{
n = ReadInt();
if(n == 0)
{
break;
}
System.out.println(getAnswer(n));
}
}
private String getAnswer(int n)
{
String strOutput = "";
Vector calculatedAnswer = calculateAnswer(n);
Vector firstAnswer = (Vector) calculatedAnswer.elementAt(0);
for (int i = 0; i < firstAnswer.size();i++)
{
Integer element = (Integer) firstAnswer.elementAt(i);
strOutput += element + " ";
}
return strOutput.trim();
}
private Vector getAnswers()
{
if (m_answers == null)
{
m_answers = new Vector(MAX_ITERATION);
// create a vector of vectors
Vector first_answers = new Vector();
Vector first_answer = new Vector();
first_answer.addElement(new Integer(1));
first_answers.addElement(first_answer);
m_answers.addElement(first_answers);
}
return m_answers;
}
/**
* here starts dynamic programming.
*
* @param n 
* 1based sequence number
* @return  vector of vectors. each vector is a possible sequence for n + 1
* given in problem situation
*/
private Vector calculateAnswer(int n)
{
Vector answers = (Vector) readAnswerFromMemory(n);
if (answers == null)
{
for (int i = n  1; i > 0 && calculateAnswer(i) == null; i);
answers = new Vector();
int nMinSequenceLength = 0;
for (int iter = 0; iter < getSequencesSortedByLenth().size() && nMinSequenceLength == 0; iter++)
{
Vector vector = (Vector) getSequencesSortedByLenth().elementAt(iter);
if (vector == null)
{
continue;
}
for (int iterator = 0; vector.size() > iterator;iterator++)
{
Integer element = (Integer) vector.elementAt(iterator);
Vector calculatedAnswer = calculateAnswer(element.intValue());
for (int iterator1 = 0; iterator1 < calculatedAnswer.size(); iterator1++)
{
Vector one_answer = (Vector) calculatedAnswer.elementAt(iterator1);
if (testAnswer(one_answer,n))
{
// ok this answer fits us
nMinSequenceLength = iter + 2;
Vector new_answer = (Vector) one_answer.clone();
new_answer.addElement(new Integer(n));
answers.addElement(new_answer);
break;
}
}
}
}
Vector vector = null;
if (m_sequences_sorted_by_lenth.size() < nMinSequenceLength)
{
m_sequences_sorted_by_lenth.setSize(nMinSequenceLength);
}
vector = (Vector)m_sequences_sorted_by_lenth.elementAt(nMinSequenceLength  1);
if (vector == null)
{
vector = new Vector();
m_sequences_sorted_by_lenth.setElementAt(vector,nMinSequenceLength  1);
}
vector.addElement(new Integer(n));
m_answers.setElementAt(answers,n  1);
}
return answers;
}
private Object readAnswerFromMemory(int n)
{
if (n > getAnswers().size())
{
getAnswers().setSize(n);
}
return getAnswers().elementAt(n  1);
}
private boolean testAnswer(Vector calculatedAnswer, int n)
{
for (int iter = 0; iter < calculatedAnswer.size(); iter++)
{
Integer element = (Integer) calculatedAnswer.elementAt(iter);
if(search(calculatedAnswer,n  element.intValue()))
{
return true;
}
}
return false;
}
private boolean search(Vector calculatedAnswer, int v)
{
int l = 0, r = calculatedAnswer.size()  1, m;
while (l <= r) {
m = (l + r) / 2;
int value = ((Integer) calculatedAnswer.elementAt(m)).intValue();
if (value > v) {
r = m  1;
} else if (value < v) {
l = m + 1;
} else
{
return true;
}
}
return false;
}
public Vector getSequencesSortedByLenth()
{
if (m_sequences_sorted_by_lenth == null)
{
m_sequences_sorted_by_lenth = new Vector();
Vector first_answer = new Vector();
first_answer.addElement(new Integer(1));
m_sequences_sorted_by_lenth.addElement(first_answer);
}
return m_sequences_sorted_by_lenth;
}
}
it would be great if you replied this post. really.

 Learning poster
 Posts: 76
 Joined: Thu Mar 13, 2003 5:12 am
 Location: Russia
The maximum limit of n can be 10000. I used IDA* search and got it Accepted.
Ami ekhono shopno dekhi...
HomePage
HomePage

 Learning poster
 Posts: 76
 Joined: Thu Mar 13, 2003 5:12 am
 Location: Russia
Re: ids should work..
thanks, sohel, very much indeed. with your piece of advice the problem is so easy. I read other posts about some hueristics which sounds really doubtful, I mean I could not figure out where it comes from. Anyway, your solution is real simple and nice. thankssohel wrote:This problem can be easily solved using IDS.. but you have to do appropriate prunning.
At each step, consider the maximum number you can make at the last depth.
For example:
if you currently have 1 2 3 , then the highest number you can make at the 6th depth( let that be the last depth) is 3 * 2^3 = 24 and if your target number is more than 24 then there is no need to proceed through this branch and you can easily prune at this point.
I applied the above approach and it got AC.
Hope it helps.
it would be great if you replied this post. really.