529 - Addition Chains

[Lebedenco]

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

[Dominik Michniewski]

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

[Lebedenco]

Ok. My fault.

Actually, I have downloaded the volumes in html.zip format and haven't realized there were a fix.html for this problem...

thank you for the hint.

N

[Dominik Michniewski]

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

[Mahmud776]

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.

[sohel]

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.

[serur]

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!

[sds1100]

i don't know

[serur]

Ah...

[Tanu]

I'm getting RE in this following code...
sample input-output 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 = top-1;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;
}

[Experimenter]

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

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

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?

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 -
	 *            1-based 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;
	}
}

[chunyi81]

Try removing the line "package src;" and try submitting again. I used to submit my solutions to some problems in UVA in Java, but I did not use packages at all in any solution I submitted to the UVA online judge.

[Experimenter]

ok, thanks very much. that might be the case. thanks, mate.

[Jan]

The maximum limit of n can be 10000. I used IDA* search and got it Accepted.

[Experimenter]

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.

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. thanks