100 - The 3n + 1 problem

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

Moderator: Board moderators

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

Post by Hisoka »

hello I don't check your algo, but in your program, you must print input or output exactly same with the sample.

for this problem your input just like this

1 100
2 24

and your output:

1 100 X
2 24 X

X = answer.

vimalreddy
New poster
Posts: 1
Joined: Sat Apr 26, 2003 1:29 am
Contact:

problem 100 (insane timings) and general tricks

Post by vimalreddy »

Hi people,
I was just curious on knowing how people get such great speed ups on their problems. For eg. I just did prob. 100 and got a timing of 3.18 .
But the ranklist shows times as low 0 seconds. I was just wondering how this can be possible. See ranklist here for p100 : http://acm.uva.es/cgi-bin/OnlineJudge?ProblemStat:100

Some people have a cputime of 0!!! Is'nt that insane? Here is my piece of code:

#define IS_ODD(i) ((i)&((unsigned int)1))

int main() {
int i, j;
int num;
int cycle_length=1, max_cycle_length=1;
while((scanf("%d %d", &i, &j))==2) {
printf("%d %d ", i, j);
if(i>j) {
/*swap*/
i=i+j;
j=i-j;
i=i-j;
}
max_cycle_length=1;
for(; i<=j; i++) {
num=i;
cycle_length=1;
while(num!=1) {
if(IS_ODD(num))
/*num=3*num+1*/
num=(num<<1)+num+1;
else
/*num=num/2*/
num=num>>1;
cycle_length++;
}
if(cycle_length>max_cycle_length)
max_cycle_length=cycle_length;
}
printf("%d\n", max_cycle_length);
}
return 0;
} /* end of main*/


Is there a better way to do this? Do you code in assembly to get such high speedups?? Or is there a better algorithm. I am very interested in knowing.

Thanks,
Vimal

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

Post by Hisoka »

hello ........

before proses, store all value in array. you can calculate from 1 to 1000000. for calculate you can do like this:
sample:

Code: Select all

ans[1]=1;
ans[2]=2;
ans[3]=8;
ans[4]=3;

ans[5]= 5 16 8 (4) =3 + ans[4]= 6;
ans[6]= 6 (3) =1 + ans[3]= 9; 
but I don't know why they can got 0:00:000 s, I use this method and AC with 00:00.???. but you can modify this method.

codemonkey
New poster
Posts: 1
Joined: Sun Apr 27, 2003 7:15 am

Post by codemonkey »

I used memorization, but the CPU time was still not 00:00.00. Can anyone share his way to optimze the code? Did they simply compute most, if not all, of the cycles and then put them into a large array? By the way, did anyone notice that some particular input will produce very large number that a 32-bit int can't hold (unsigned int will be better)? For example, you can try 113383, 134379, or 138367. It seems the online judge didn't particularly test for such numbers.

Diskerr
New poster
Posts: 16
Joined: Sun Apr 06, 2003 8:43 am
Location: Korea, Republic of

It seems to ...

Post by Diskerr »

The high rankers seem that they know the judge's input, so they just send a table..

As you know, there are many 0 sec rankers in other problems.
They may know judge's input..
(I heard that we can get judge's input of some problems in some web sites.)
Sorry for my poor English.

bery olivier
Learning poster
Posts: 90
Joined: Sat Feb 15, 2003 1:39 am
Location: Paris, France
Contact:

Post by bery olivier »

It is possible to know the judge's input. see :
http://acm.uva.es/board/viewtopic.php?p ... ight=#8329
But it takes a lot of time.
however get Ac with 0:00.000 doesn't mean that the sender knew the input.
Not AC yet Image AC at last Image

matt80
New poster
Posts: 6
Joined: Thu May 01, 2003 9:49 am

Re: problem 100 (insane timings) and general tricks

Post by matt80 »

vimalreddy wrote:Hi people,
I was just curious on knowing how people get such great speed ups on their problems. For eg. I just did prob. 100 and got a timing of 3.18 .
....
Is there a better way to do this? Do you code in assembly to get such high speedups?? Or is there a better algorithm. I am very interested in knowing.
Vimal
Hi!

I even wonder how it is possible to reach a tiime 0.0.0. My algorithm spent 0.164 s and 508k and I can't find a way to improve it, except enlarging the array memory. I post it hoping someone could help me.
[cpp]
#include <iostream.h>
#include <stdio.h>

short memory[30000];

int run (unsigned long m){

int c=0;
short *i;
while(m!=1){

if (m%2){
if (m < 59999) {
i = (memory + m/2);
if (*i){
return c + *i;
}else{
*i = run((m*3)+1);
return ++(*i) + c;
}
}
m*=3;
m++;

}else{

m/=2;
}
c++;
}
return ++c;
}

int main(){

int i,j;
int c,max;

for (short *i=memoria+1; i<memoria+30000; i++){
*i = 0;
}

while (scanf("%d %d\n",&i,&j)==2){

cout << i << " " << j << " ";

if (j<i) {
int tmp = j;
j = i;
i = tmp;
}

if ((j/2)>i) i = j/2;

for(int n=j; n>=i; n--){
c = operazione(n);
if (max<c) max=c;
}

cout << max << endl;

}
return 0;
}
[/cpp]

Fayaz
New poster
Posts: 1
Joined: Wed May 07, 2003 10:29 am
Location: Bangladesh

WA in 100-java h-e-l-p

Post by Fayaz »

I don't know why i'm getting wa here!! This is my code.
Somebody help pls...

:o
[java]
/* @JUDGE_ID: 31009YN 100 java */

//"@begin_of_source_code"

import java.io.*;
import java.util.*;

class Main
{
static long[] memory;

public static void main(String[] args)
{

memory=new long[1000000];
String input="";
String in1;
while((in1=readLine(255))!=null)
{
input=input+in1;
}

StringTokenizer st=new StringTokenizer(input);
try
{
while(st.hasMoreTokens())
{
long n1=0,n2=0;
n1=Long.parseLong(st.nextToken());
n2=Long.parseLong(st.nextToken());

System.out.println(n1+" "+n2+" "+result(n1,n2));
}
}


catch(NumberFormatException ex)
{
}
}

static String readLine (int maxLength)
{
byte line[] = new byte [maxLength];
int length = 0, input = -1;

try
{
while (length < maxLength)
{
input = System.in.read();
if ((input < 0) || (input == '\n'))
break;
line [length++] += input;
}
}
catch (IOException ex)
{
return null;
}

if ((input < 0) && (length == 0))
return null;
return (new String (line, 0, length));
}

static long result(long x,long y)
{
long temp;
if(x>y)
{
temp=x;
x=y;
y=temp;
}
if(x<1 && y<1) return 0;
if(x>1000000 && y>1000000) return 0;
if(x<1) x=1;
if(y>1000000) y=1000000;
return maxLength(x,y);
}

static long maxLength(long x,long y)
{

long max=0,length;
for(long i=y; i>=x;i--)
{
if((length=cycleLength(i))>max) max=length;
}
return max;
}

static long cycleLength(long x)
{
if (x==1)
return 1;
else if(x<1000000)
{
if(memory[(int)x]!=0)
return memory[(int)x];
else
{
if ( x%2==0)
return (memory[(int)x]=cycleLength(x/2)+1);
else
return (memory[(int)x]=cycleLength(3*x+1)+1);
}
}
else
{
if ( x%2==0)
return cycleLength(x/2)+1;
else
{
return cycleLength(3*x+1)+1;
}
}
}


}


//"@end_of_source_code"
:( [/java]
fayaz

Diskerr
New poster
Posts: 16
Joined: Sun Apr 06, 2003 8:43 am
Location: Korea, Republic of

The problem is..

Post by Diskerr »

The reason you got WA is that you didn't handle the input correctly.

Use this code instead of yours :
[java]public static void main(String[] args)
{

memory=new long[1000000];
String input="";
String in1;
while((in1=readLine(255))!=null)
{
input = in1;

StringTokenizer st=new StringTokenizer(input);
try
{
long n1=0,n2=0;
n1=Long.parseLong(st.nextToken());
n2=Long.parseLong(st.nextToken());

System.out.println(n1+" "+n2+" "+result(n1,n2));
}

catch(NumberFormatException ex)
{
}
}
}
[/java]
Actually, you don't need 'in1' or 'input', but I didn't touch it.

And, you should not include your ID in posted source code.
(I mean @JUDGE_ID line)
Sorry for my poor English.

Russell
New poster
Posts: 1
Joined: Sun May 11, 2003 2:32 am

Re: problem 100 (insane timings) and general tricks

Post by Russell »

matt80 wrote: Hi!

I even wonder how it is possible to reach a tiime 0.0.0. My algorithm spent 0.164 s and 508k and I can't find a way to improve it, except enlarging the array memory. I post it hoping someone could help me.
I saw alot of things in your code. Non-dynamic arrays in C++ are automatically initialized to zero, so setting the array to 0 is redundant. m%2 is fine, but m & 1 is able to check for an odd number, only with a grand total of one instruction.

I'm not sure why you hardcoded your table to 30,000. You can store much more without going over the memory limits, and the increased memoization should speed it up alot..

m/=2 can be rewritten as m = m>>1, which is again less instructions.

There's some other little things like the fact that xor swapping would be faster if you want to get every ounce of performance. Also, look at the results of the program and notice the boundries. You should be able to answer about 50% of the possible values without cheating or doing more than a fine lines of calculating.

I wrote relatively sloppy code and got a time of .102 with 4352kb memory.

I have no idea how people got the code down to .040 and below. I'm completely new here and have never done ACM or anything. Can't wait to start learning! =)

pez
New poster
Posts: 1
Joined: Mon May 12, 2003 5:56 pm
Contact:

Some tricks

Post by pez »

Hi!

Maybe this help a little:
while N <> 1 do begin
if odd(N) then begin
{n := 3*n + 1; - result is not odd, so divide by 2}
N := N + ((N + 1) div 2);
cl := cl + 2;
continue;
end else N := N div 2;
cl := cl + 1;
end;

matt80
New poster
Posts: 6
Joined: Thu May 01, 2003 9:49 am

Re: problem 100 (insane timings) and general tricks

Post by matt80 »

Russell wrote: I saw alot of things in your code. Non-dynamic arrays in C++ are automatically initialized to zero, so setting the array to 0 is redundant. m%2 is fine, but m & 1 is able to check for an odd number, only with a grand total of one instruction.

I'm not sure why you hardcoded your table to 30,000. You can store much more without going over the memory limits, and the increased memoization should speed it up alot..

m/=2 can be rewritten as m = m>>1, which is again less instructions.
Hi!
I'm very glade for yuor tips, but I have already done them in the last version of my algorithm. They don't let to save more than 1 ms.
I used an array of 30.000 elements to reduce the recursive call. Actually if it is too large the algorithm will be slower. The best result I acheaved is 0,084 s with 64k of memory, using an array with 50.000 elements. You'll find me in the list (my name is Mattia Adami).
Russell wrote: There's some other little things like the fact that xor swapping would be faster if you want to get every ounce of performance. Also, look at the results of the program and notice the boundries. You should be able to answer about 50% of the possible values without cheating or doing more than a fine lines of calculating.
Sorry but I can't understand well what you mean. English is not my mother language... could you explain me please?

Thanks a lot!
Mattia

ChristopherH
New poster
Posts: 31
Joined: Sun Feb 23, 2003 9:18 pm
Location: Waterloo, Ontario, Canada

Post by ChristopherH »

If you are interested in getting fast times on UVA you are in for a bunch of work.

First, unless you're worried about your submission accuracy (a reasonably futile concern -- the large number of underspecified problems require some degree of trial and error), I suggest the following:

Submit a program which reads the input (using your preferred method), and then returns, without doing any computation or output.

This will give you a lower bound on your runtime. For instance, on problem 100, I believe that one can't even read the input (using scanf or cin >>) in 0.000 seconds, so it is pointless to try to submit a genuine solution in the hopes of getting 0.000 seconds runtime.

(Please correct me if somebody has discovered a method of I/O which is faster -- I also may be remembering incorrectly and problem 100 doesn't have this property, but certainly many others do).

Personally, I don't try to get high ranks on 'easy' problems (ie ones in which the fastest solutions are, say, < 0.100 s). It becomes too much of an exercise in peephole optimization and knowing the idiosyncrasies of the UVA compilers (e.g. since they don't compile with -O, recursion is often far faster than iteration, STL vector access is abysmal, C I/O is usually faster than C++, etc.). There are still many challenging problems out there on which you can get a top-10 position by finding an exceptional algorithm. It's incredibly satisfying when you beat the fastest time by some large factor without cheating.

See you at the top!

p.s. one point to keep in mind: it appears that the UVA judge can't register memory footprints of programs which run very quickly (around 0.050 s IIRC) so they show up as 64k regardless of their actual usage -- don't be fooled!

ChristopherH
New poster
Posts: 31
Joined: Sun Feb 23, 2003 9:18 pm
Location: Waterloo, Ontario, Canada

Post by ChristopherH »

Here's an example of what I/O timings can tell you:

I recently looked at problem 10011.

The top two times on the ranklist are 0:00.221 and 0:00.482.

Submitting an I/O shell which reads the input and outputs "0.000" gives me the following timings:

cin >> double: 1.113 s
scanf double: 0.484 s
scanf float: 0.342 s

Apparently the #1 submitter has some technique for performing I/O more quickly. So I wouldn't bother trying to get #1 on 10011 unless you have similar techniques in your toolkit.

felipe
New poster
Posts: 1
Joined: Thu May 15, 2003 2:34 pm
Location: Brasil
Contact:

100 => Allways wrong answer!

Post by felipe »

Hi all...

I would like to know why I have allways wrong answer when submiting the code bellow. In my machine, it works well with the given inputs.

Thanks.

[java]
import java.io.*;
import java.util.*;

class Main
{
static String readLn (int maxLg) /* utility function to read from stdin */
{
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";

try
{
while (lg < maxLg)
{
car = System.in.read();
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}
catch (IOException e)
{
return (null);
}

if ((car < 0) && (lg == 0)) return (null); /* eof */
return (new String (lin, 0, lg));
}

public static void main (String args[])
{
Problema problema = new Problema();
String l = "";
StringTokenizer temp0 = new StringTokenizer("");
String[] temp = new String[3];
int retorno;
l=readLn(20).trim();
while(l != null && !l.equals("")) {
temp0 = new StringTokenizer(l," ");
temp[0] = temp0.nextToken();
temp[1] = temp0.nextToken();
retorno = problema.run(Integer.parseInt(temp[0]),Integer.parseInt(temp[1]));;
System.out.println(temp[0] + " " + temp[1] + " " + retorno);
l=readLn(20).trim();
}
}

}

class Problema {
public int run(int inicio, int fim) {
int retorno = 0;
int temp=0;
int n=0;
for(int i=inicio;i<=fim;i++) {
temp = 1;
n = i;
while(n!=1) {
if((n%2)==0)
n = n/2;
else
n = 3*n + 1;
temp++;
}
if (temp > retorno)
retorno = temp;
}
return retorno;
}
}
[/java]
Felipe Augusto Pereira
Recife - PE - Brasil

Post Reply

Return to “Volume 1 (100-199)”