100 - The 3n + 1 problem

[Smeagol '_']

hi,
i just got my code accepted but i'm wasting too much memory... I don't know how to reduce it. I tried allocating memory for each case depending on the range given , but this increases cpu time.... can somebody help me out.
This is the code i have.

[cpp]
#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;

int main()
{
register unsigned int first =0;
register unsigned int last =0;
int* array = new int[1000000];

while(scanf("%d %d%*c",&first, &last)==2)
{

register int count=1;
register int max=1;

printf("%d %d",first, last);
if(first > last)
{
register unsigned int tmp=first;
first=last;
last=tmp;
}
for(register unsigned int i=first;i<=last;i++)
{

if(array == 0)
{
register unsigned int k=i;
count=1;
while(k!=1)
{
if(k%2 != 0) k=(3*k)+1;
else k/=2;
count++;
}
array=count;
}
else
count=array;

if(max<count)
max=count;
}
printf(" %d\n",max);

char c=getchar();
ungetc(c,stdin);
if(c=='\n')
printf("\n");

}
delete [] array;

return 0;
}
[/cpp]

[kenshin_kudo]

Can anybody see what's wrong with this code?


[java]
//@BEGIN_OF_SOURCE_CODE
// @JUDGE_ID: 28212NH 100 Java "Easy algorithm"
import java.io.*;
import java.util.*;


class Main {

static String readLine () // utility function to read from stdin
{
int maxLg=255;
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));
}

static void main(String args[]) throws Exception {
//BufferedReader in =new BufferedReader(new InputStreamReader(System.in));
String s="";
boolean first=true;
while((s=readLine())!=null) {
if (!first)
System.out.println();
first=false;
StringTokenizer st=new StringTokenizer(s);
long I= Long.parseLong(st.nextToken());
long J= Long.parseLong(st.nextToken());
long II=I,JJ=J;
if (II>JJ) {
long temp=II;
II=JJ;
JJ=temp;
}
long max=0;
for(long i=II;i<=JJ;i++) {
// System.out.println(i);
long tmp=getCycle(i);
if(tmp>max) {
max=tmp;
}
}
System.out.print(I+" "+J+" "+max);
}
}

static int getCycle(long n) {
int cycle=1;
while(n!=1) {
if(n%2==0) {
n/=2;
}
else {
n=3*n+1;
}
cycle++;
}
// System.out.println("Debug:"+n+" "+cycle);
return cycle;
}
}
//@END_OF_SOURCE_CODE[/java]

[Chamak]

I don't understand why it's telling wrong answer when i m submitting can anyone help me please ??????
here is the hole program :


#include<iostream.h>
int count=0,temp=0;
int cycle(long unsigned int n)
{
if (n==1) return ++count;
else
{
count++;
if((n%2)!=0)
return cycle((3*n)+1);
else
return cycle(n/2);
}
}
void main(void)
{
int mn,n,a[4],b[4],c[4];
for(mn=0;mn<4;mn++)
{
cin>>a[mn]>>b[mn];
for(n=a[mn];n<=b[mn];n++)
{
cycle(n);
if(temp<count) temp=count;
count=0;
}
c[mn]=temp;
temp=0;
}
for(mn=0;mn<4;mn++)
cout<<a[mn]<<" "<<b[mn]<<" "<<c[mn]<<"\n";
}

[Smeagol '_']

maybe it's because you're using signed integers and when it tests for large numbers it's not calculating right. I tested the program and it didn't work.
You should use unsigned ints and i believe the compiler complains when not using that
int main()
{
return 0;
}
format. I haven't looked at the whole code but you can check on that

[kenshin_kudo]

Oh well. I finally figured it out by my own.....
Here's some pointers for those who are trying to solve this problem!
If you are using java, make sure you see this points:
Your class has to be called Main and it must not be public!!!!
Your static class MUST be public! This is my bug.
You cannot use BufferedReader, you need to use the function provided(see the online submission using Java)
Don't forget that i and j can be swapped in occurence, so make sure you get that right! And also the loop should go from i to j (including j).

Hope u check these and got yours right!

[Larry]

Actually, at least for this problem, I don't think it matters.

However, keep in mind that a[mn] can be greater than b[mn].

[Adrian Kuegel]

I don't understand why it's telling wrong answer when i m submitting

And I don't understand how you could think that you will get another result with a program like that (no offence meant!).
First mistake: I think there is no word in the description that there are only 4 test cases. And you need not to store the results, you can print the result for each test case directly after reading it.
Second mistake: Larry said it already, a[mn] can be >b[mn]. But there are also some numbers between them in this case, and you should take the maximum cyclelength of all numbers between (and including) a[mn] and b[mn] (read description carefully).
Third mistake: A recursive solution might get Runtime Error on bigger test cases, try to do it with a while-loop.

[ichaoz]

hi,
i've just looked at your code and noticed that you don't need
your array. the else statement
[cpp]count=array;[/cpp]
will never be executed because you don't write into the array before you check it with the if-statement
[cpp]if(array == 0) [/cpp]
your count variable is sufficent

hope that helps

[Smeagol '_']

I gives me a wrong answer if i take off that line and doen't reduce de memory

[Chamak]

One thing I didn't mentioned that i m new in here ... i may do donkey like mistakes , whatever thnx for helping me but still 1 thing i can't get is till when i'll take the inputs ???? again thnx all of you.....good day

[ichaoz]

Hi again,
i meant that you have to remove all your array statements.
(including the if-statment)
you really don't need it.

[Smeagol '_']

i'm sorry, i'm new to this.... but , if i get rid of the array statements it's going to take a lot of cpu time this i used to store the already computed values... what should i use for caching then?
thank you for your comments

[ichaoz]

no problem
i don't think you need to cache anything. If you try just
the input 1 100000 then caching doesn't pay.
Another problem that may cause a WA is that you don't
initialize your array before using it. So discard your array,
send your code, and you'll be fine

[29145]

[c]#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main()
{
char *ch1,*temp,*ch2,*ch3 = " ";
unsigned long a,b,j,k,l,m;
char s[50];
int i = 0;
int no,maxi = 0;
short p;
while( (*temp = getchar()) != EOF )
{
if (*temp == '\n')
{
ch1 = s;
ch2 = strstr(ch1,ch3);
b = atol(ch2);
a = atol(ch1);
l = (a>b)?b:a;
m = (a>b)?a:b;
i = maxi = 0;
for(j = l; j<=m;j++)
{
k = j;
no = 1;
while(k != 1)
{
if ((k%2) == 0)
k /=2;
else
k = 3*k +1;
no++;
// printf("%d",no);
}
if(maxi < no)
maxi = no;

}

printf("%ld %ld %d \n",a,b,maxi);
for(p=0;p<50;p++)
s[p] = '\0';
}
else
s[i++] = *temp;


}
}


[/c][/c]

[Hisoka]

I think your algo to get answer is right, but I think your problem at your input. why you use string for this problem ? you can use this for input:
while(scanf("%ld %ld",&a,&b)==2)
{
...
}