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

Lebedenco
New poster
Posts: 5
Joined: Mon Aug 23, 2004 6:55 am

529 - wrong judge input!?

Post by Lebedenco » Mon Sep 06, 2004 8:50 pm

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
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Tue Sep 07, 2004 12:02 am

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

Lebedenco
New poster
Posts: 5
Joined: Mon Aug 23, 2004 6:55 am

Post by Lebedenco » Tue Sep 07, 2004 4:10 am

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... :oops:

thank you for the hint.

N

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Tue Sep 07, 2004 8:05 am

It's a standard problem of many of us :oops: I think that best way is to have own copy of problems and update it self or using www part of judge with problems :D
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)

Mahmud776
New poster
Posts: 22
Joined: Mon Dec 22, 2003 9:29 am
Location: Canada

529 - How can I reduce the search time

Post by Mahmud776 » Tue Mar 08, 2005 3:47 pm

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.

:oops: :oops: :oops: :oops: :oops:

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

ids should work..

Post by sohel » Wed Mar 09, 2005 11:00 am

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
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

529-addition chains

Post by serur » Mon Mar 13, 2006 9:43 pm

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!
Last edited by serur on Thu Oct 09, 2008 9:47 am, edited 2 times in total.

sds1100
Learning poster
Posts: 95
Joined: Sat Dec 10, 2005 2:09 pm

1

Post by sds1100 » Tue Mar 14, 2006 4:16 pm

i don't know :(

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » Sat Mar 18, 2006 2:07 am

Ah...
Last edited by serur on Thu Oct 09, 2008 9:48 am, edited 1 time in total.

User avatar
Tanu
Learning poster
Posts: 70
Joined: Sun May 29, 2005 12:46 pm
Location: Mars

529 going runtime error,plz why

Post by Tanu » Wed Apr 26, 2006 12:14 pm

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
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia

what da ... is this?

Post by Experimenter » Sat Jun 03, 2006 8:01 pm

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;
	}
}


it would be great if you replied this post. really.

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 » Sun Jun 04, 2006 5:17 am

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
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia

Post by Experimenter » Sun Jun 04, 2006 8:14 am

ok, thanks very much. that might be the case. thanks, mate.
it would be great if you replied this post. really.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Tue Jun 06, 2006 2:06 am

The maximum limit of n can be 10000. I used IDA* search and got it Accepted.
Ami ekhono shopno dekhi...
HomePage

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia

Re: ids should work..

Post by Experimenter » Sat Jun 10, 2006 7:29 pm

sohel 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. :)
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
it would be great if you replied this post. really.

Post Reply

Return to “Volume 5 (500-599)”