371 - Ackermann Functions

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

Moderator: Board moderators

Post Reply
User avatar
mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

371 can any body explain a good algorithm

Post by mohiul alam prince » Wed Mar 10, 2004 3:29 pm

hi
i am getting TLE again & again can any body explain a good algorithm
mohiul alam prince
Last edited by mohiul alam prince on Thu Feb 17, 2005 3:04 pm, edited 1 time in total.

osan
New poster
Posts: 47
Joined: Tue Jul 29, 2003 12:03 pm
Location: Bangladesh,Dhaka.
Contact:

mohiul alam prince

Post by osan » Wed Mar 10, 2004 6:15 pm

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.
this time WA
what next...............?

osan
New poster
Posts: 47
Joined: Tue Jul 29, 2003 12:03 pm
Location: Bangladesh,Dhaka.
Contact:

algo of 371

Post by osan » Wed Mar 10, 2004 6:22 pm

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
this time WA
what next...............?

User avatar
alu_mathics
Learning poster
Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong
Contact:

Post by alu_mathics » Wed Mar 10, 2004 7:46 pm

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 :wink:
Last edited by alu_mathics on Thu Apr 01, 2004 7:39 pm, edited 1 time in total.
cuii e

User avatar
mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Post by mohiul alam prince » Wed Mar 31, 2004 8:55 am

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
New poster
Posts: 47
Joined: Tue Jul 29, 2003 12:03 pm
Location: Bangladesh,Dhaka.
Contact:

prince

Post by osan » Wed Mar 31, 2004 7:53 pm

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
this time WA
what next...............?

Md. Azam Khan
New poster
Posts: 8
Joined: Tue Jun 15, 2004 7:16 pm
Location: Chittagong, Bangladesh
Contact:

Post by Md. Azam Khan » Sun Jun 27, 2004 10:38 pm

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

Guest
New poster
Posts: 39
Joined: Wed May 19, 2004 5:52 pm
Location: Dhaka, Bangladesh
Contact:

371:Ackermann Functions, Confusion

Post by Guest » Mon Jun 28, 2004 7:59 pm

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
New poster
Posts: 8
Joined: Tue Jun 15, 2004 7:16 pm
Location: Chittagong, Bangladesh
Contact:

Post by Md. Azam Khan » Tue Jun 29, 2004 8:09 pm

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

Guest
New poster
Posts: 39
Joined: Wed May 19, 2004 5:52 pm
Location: Dhaka, Bangladesh
Contact:

Post by Guest » Thu Jul 01, 2004 7:23 am

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
New poster
Posts: 38
Joined: Wed Sep 22, 2004 9:09 am

371 gives T.L.E .Help me.

Post by efr_shovo » Wed Sep 29, 2004 10:00 am

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
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

Post by jagadish » Wed Sep 29, 2004 6:04 pm

i used long long for this problem.. now your code gets WA
if u can think of it .. u can do it in software.

jhonny_yang
New poster
Posts: 22
Joined: Fri Jan 17, 2003 8:24 am

Re: OH CRAP!

Post by jhonny_yang » Fri Nov 12, 2004 6:40 pm

MAXX^FACTOR wrote:your method is too slow .............and "TIMELIMITEXCEEDED" is happened :x :x :x

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
New poster
Posts: 1
Joined: Thu Dec 16, 2004 9:52 am

371 Akerman TLE is denied now why WA

Post by sumanali » Thu Dec 16, 2004 10:14 am

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

User avatar
alu_mathics
Learning poster
Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong
Contact:

Post by alu_mathics » Sat Dec 18, 2004 5:33 am

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. :wink:
cuii e

Post Reply

Return to “Volume 3 (300-399)”