Moderator: Board moderators

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

### 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?

-- N

Dominik Michniewski
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
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
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
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
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

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

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

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

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

i don't know

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
Ah...
Last edited by serur on Thu Oct 09, 2008 9:48 am, edited 1 time in total.

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

### 529 going runtime error,plz why

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?

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_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)
{
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);
}
{
//return m_test_count++ % (MAX_ITERATION + 1);
StringTokenizer strToken = GetTokens();
return Integer.parseInt(strToken.nextToken());
}
}

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)
{
if(n == 0)
{
break;
}
}
}
{
String strOutput = "";
for (int i = 0; i < firstAnswer.size();i++)
{
strOutput += element + " ";
}
return strOutput.trim();
}
{
{
// create a vector of vectors
}
}
/**
* 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
*/
{
{
for (int i = n - 1; i > 0 && calculateAnswer(i) == null; i--);
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);
for (int iterator1 = 0; iterator1 < calculatedAnswer.size(); iterator1++)
{
{
// ok this answer fits us
nMinSequenceLength = iter + 2;
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);
}
}
}
{
{
}
}
{
for (int iter = 0; iter < calculatedAnswer.size(); iter++)
{
{
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;
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();
}
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
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
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
Contact:
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..

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.