371 - Ackermann Functions

[mohiul alam prince]

hi
i am getting TLE again & again can any body explain a good algorithm
mohiul alam prince

[osan]

ya i have seen that u are using double.
but stupid buddy i told about m & n.(where u r getting input)
they told input range will 32 bit integer.
so i told u to use unsigned long substitute of long.
like that->>>
scanf("%lu%lu", &m ,&n);

& mr sohel i can use unsigned long, which supports Turbo C++ && Visual C++.

so i'm not interested to use long long. long long only support in GCC.

[osan]

i used same algo in 371 & 100.
different
special case 1. cycle length 3.
data type
for 100 int
for 371 unsigned long.
(cause input range is 32 bit integer)

hope u will get AC now

[alu_mathics]

Three mistakes in a single program.

Mind it this is like 100 but not 100.

1. max = cycle(m);
x=m;
for(i=m+1;i<=n;i++) {
temp = cycle(i);
if (temp > max){
max = temp;
x=m; //No excuse.
}
}

2. The largest value in the sequence will not be larger than can be accomodated in a 32-bit Pascal .
so u can use long long(%lld) or unsigned long(%lu) both for input
&& output && also temp.(or, change all data to lld or lu)

3.Between L and H, V generates the longest sequence of S values.
Where:
L = the lower boundary value in the sequence
H = the upper boundary value in the sequence

so print m && n even after swapping, not mOriginal,nOriginal.(does not match with 100)

Hope i am clear 2 u.

And don't forget to remove the code after u get AC

[mohiul alam prince]

Osan
Why don't u understand
i have used unsigned long for all variable and submitted but getting WA
also use double for all variable but still getting WA
prince

[osan]

prince u told u were getting TLE
so i told abt that.
well u r getting WA cos
for input
1 20
Between 1 and 20, 18 generates the longest sequence of 20 values.
20 1
Between 1 and 20, 18 generates the longest sequence of 20 values.

got it?
i hope u will AC now.

take care

[Md. Azam Khan]

Hi,
You solved 100 and 694, but TLE in 371! You can use same algorithm and code of 100, but think what will be output if input is 1 and 1. For this input loop will continue.

int cycle(long long m)
{
int i=0;
while(m!=1||i==0) // see this condition
{
.........
}
return i;
}


in main():
if(temp>max_cycle)
{
max_value=i; //update this value, i from for loop
max_cycle=temp;
}

Another trick in this problem is- smaller input alway first output:
input: 55 35 then output 35 55
input: 35 55 then the output also 35 55

Hope this will help u and soon it will be added in your solved problem.

I born to code

[Guest]

In the problem statement, it says:
"V = the first value that generates the longest sequence, (if two or more values generate the longest sequence then only show the lower value) S = the length of the generated sequence. "

In the next line: "In the event that two numbers in the interval should both produce equally long sequences, report the first."

Don't these two statements create a contradiction?
If the given range is like 55-35, then should i report 55, or 54, as both generate the longest sequence.

Thank you!

[Md. Azam Khan]

Hi,
Please read the two statements again that u write and also the whole problem . The both statements saying that from a given range u should print the lower one if two or more values generates same (longest) sequence. Suppose u are given to generate the range 55 35 then u proceed from 35 to 55 and again if u are given 35 55 then u also proceed from 35 to 55. So the lower or the first value is 54 not 55, isn't it?
Anyway don't think that u will not proceed from 55 to 35. But u should always think the value according to mathematical order to consider lower of first one: 0,1,2,3,.....,54,55,56,...............................

I hope this can help u if u need.

I born to code

[Guest]

Finally, I got accepted by testing my exe with an accepted exe.

The trick is:

Input: 35 55

Output: "Between 35 and 55, ....."

Input: 55 35

Output: "Between 35 and 55,...."

and not "Between 55 and 35,...."

[efr_shovo]

371 gives T.L.E . How Can I solve This Problem?Please Help

#include<stdio.h>
#include<stdlib.h>

long int max,m,d;

long int ALGORITHOM(long int n)
{
long int k=0;
m=n;
if(m==1)
d=1;
while(n!=1)
{
if ((n%2)!=0)
n=(3*n+1);
else
n=n/2;
k++;
}

if(max<k)
{
max=k;
d=m;
}
return 0;
}

int main ()
{
long int j,w,y,i,a,b;
while(1)
{
scanf("%ld %ld",&i,&j);
if(i==0&&j==0)
break;
if((i>0&&i<=2147483647)&&(j>0&&j<=2147483647))
{
a=i;
b=j;
w=(j-i);
if(w<0)
w=abs(w);
for(y=0;y<=w;y++)
{
if(i<j)
{
ALGORITHOM(i);
i++;
}
else
{
ALGORITHOM(j);
j++;
}
}
printf("Between %ld and %ld, %ld generates the longest sequence of %d values\n",a,b,d,max);
max=0;
d=0;
}
else return 0 ;
}
return 0;
}

[jagadish]

i used long long for this problem.. now your code gets WA

[jhonny_yang]

your method is too slow .............and "TIMELIMITEXCEEDED" is happened

OH! CRAP~~~~~~

I'm using ... method

typedef struct{
int low,high;
int Number,Sequence;
} Data;

Data Buff[1000];

I save all in buff and the counting it. It's more fast.

Another trick : 3*n+1 -> but the limit is integer so you must use long long or long double in this case.

Hope my solution acceptable. and yours too

[sumanali]

I am a student Of Jinnah University Pakistan I have been
trying to solve the Problem "Akerman" prob#371
I have been getting time limit execede Error
Plz Tell Me the error In MY code

Thanks in advance for your help.. and plz reply





Problem Akerman
# 371
TLE


#include<iostream>
using namespace std;

int AckermennFunction(int val);
//8589934591
void main()
{
int x=0;int y=0;
cin>>x;cin>>y;
while(x!=0 && y!=0) {
int MAX=-1;int i=0;
for(int t=x;t<=y;t++)
{
int temp=AckermennFunction(t);
if(temp>MAX){MAX=temp;i=t;}
}
cout<<"Between "<<x<<" and "<< y<<", "<<i<<" generates the longest sequence of "<<MAX <<" values.\n";
cin>>x;cin>>y;
}
}
int AckermennFunction(int val)
{
// All the Odd Numbers Have Least Significient Bit==1
int count=0;
do
{ count++;
if(val%2==0){ val = val/2;}
else{val = 3*val+1;}
}while(val!=1);
return count;
}

[alu_mathics]

i hope you have change ur datatype to unsigned long or long long or __int64.

consider the case
2147483647 2147483647
then you can get overflow.
coz 2147483647*3+1 is out of range of int(long) indeed.

input can be
12 10
so swap them and thus you can avoid tle.
remember the word "between" all the time.atleast i do.