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
Rocky
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:

Post by Rocky »

YAAAA.. , GOOD ANSWER MATHICS

Take a Large Data Type That The Result Value During Runtime,That is (3*n+1,When n is a odd number of more than 8 digit) Can Store in it.

Thanks

GOOD LUCK

QulinXao
New poster
Posts: 29
Joined: Mon Apr 05, 2004 11:12 am

hint for 371

Post by QulinXao »

Only one hint need for this problem
if l>h then swap(l,h)

{code for find longest seq}
out (l,h,minnumberwhenseqlongest,seqlong)

ONLY ONE HINT. NOT MORE
the type wich need simple signed 32 bit (read carefuly problem:
"The largest value in the sequence will not be larger than can be accomodated in a 32-bit Pascal LongInt or C long"
so not only l & h in longint but all!!! number in seg in longint(<2^31-1)

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

Post by Antonio Ocampo »

Hi QulinXao.

According to the statement
L = the lower boundary value in the sequence
H = the upper boundary value in the sequence
Therefore H>=L always , so isn
Last edited by Antonio Ocampo on Thu Jan 06, 2005 9:36 pm, edited 1 time in total.

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker »

:lol: easy.......isn't it? :wink:
Jalal : AIUB SPARKS

sunmoon
New poster
Posts: 4
Joined: Tue Jun 29, 2004 12:50 pm
Contact:

371 in 0.693 s

Post by sunmoon »

Hey! If anyone wants to know how to get 371 AC in .7 s feel free to bug me.

I used memoization.
All

ravi,IITM.

Andrey
New poster
Posts: 16
Joined: Sat Mar 05, 2005 8:25 pm
Location: Ukraine,Vinnitsa

Please HELP! 371 WA

Post by Andrey »

What's wrong in my code?

Code: Select all

#include <iostream.h>

void main()
{
  long long i,j,n,max,v,c,t,tmp;
  cin>>i>>j;
  while(i!=0)
  {
     v=-1;
     max=0;
     if(i>j) {tmp=j;j=i;i=tmp;}
     for(t=i;t<=j;t++)
     {
	c=0;
	n=t;
	while(n!=1)
	{
	   c++;
	   if(n%2==1) n=3*n+1;else n/=2;
	}
	if(c>max||v==-1) {max=c;v=t;}
     }
     cout<<"Between "<<i<<" and "<<j<<", "<<v<<" generates the longest sequence of "<<max<<" values."<<endl;
     cin>>i>>j;
  }
}

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba

Post by neno_uci »

Hi Andrey, the length of the sequence generated by 1 is 1, there is your mistake, replace your

while (n != 1) { ... } loop by

do { ... } while (n != 1);

and the work is done...

best wishes,

Yandry. :D

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho »

The values for L and H can not be negative, right ? Or do we
have to consider negative values too ?

( Don't bother to answer now ! There're no
negative values for L and H in the input )

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho »

Hi, neno_uci, Andrei,

If the sequence length for N=1 is 1 then what is the sequence
length for N=2 ? Should be 2, if we follow your logic.

On the contrary, if we follow the logic of their example the
sequence length for N=2 should be 1.

They have this example:
[10] 5 16 8 4 2 1 {6}
10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 7
We have 7 numbers in this chain but the answer for N=10
is 6 ( according to this example they give ).
So for N=2 we have:
[2] 1 {1}
because
2 --> 1

What do you think ?

I am personally a little bit confused.

I get WA for the moment and
I am trying to get at least TLE and then to try to
optimize my algorithm.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho »

Sample I/O for anyone who is attacking this quite tricky
( in my opinion ) problem.

INPUT

Code: Select all

  2147483647 2147483647
  1 20
 35 55
 1 1
 20 1
 1000001  1200000
 1000000 1000000
 2000000 2000000
 4000000 4000000
 2147483647 2147483647
 1000003  5000005
 16 16 
 1 2
 58 58
 19 19
 1 3
 1 2
 2 2
  0 0

OUTPUT

Code: Select all

Between 2147483647 and 2147483647, 2147483647 generates the longest sequence of 450 values.
Between 1 and 20, 18 generates the longest sequence of 20 values.
Between 35 and 55, 54 generates the longest sequence of 112 values.
Between 1 and 1, 1 generates the longest sequence of 3 values.
Between 1 and 20, 18 generates the longest sequence of 20 values.
Between 1000001 and 1200000, 1117065 generates the longest sequence of 527 values.
Between 1000000 and 1000000, 1000000 generates the longest sequence of 152 values.
Between 2000000 and 2000000, 2000000 generates the longest sequence of 153 values.
Between 4000000 and 4000000, 4000000 generates the longest sequence of 154 values.
Between 2147483647 and 2147483647, 2147483647 generates the longest sequence of 450 values.
Between 1000003 and 5000005, 3732423 generates the longest sequence of 596 values.
Between 16 and 16, 16 generates the longest sequence of 4 values.
Between 1 and 2, 1 generates the longest sequence of 3 values.
Between 58 and 58, 58 generates the longest sequence of 19 values.
Between 19 and 19, 19 generates the longest sequence of 20 values.
Between 1 and 3, 3 generates the longest sequence of 7 values.
Between 1 and 2, 1 generates the longest sequence of 3 values.
Between 2 and 2, 2 generates the longest sequence of 1 values.
Last edited by Sedefcho on Sat Mar 12, 2005 6:33 pm, edited 1 time in total.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho »

I have found what my problems were.

Quite quite unpleasant tricky stuff.


1) They have test cases where L > H. Anyway, no problem about
that, OK, we swap them. So now we have L < H. But when we print
our answer we have to print L and H in increasing order ( in the order
they are after they are swapped ). So in these cases we
actually do not print " Between L ... H ... "but we print
"Between H ... L ... ".
And I was previously printing them in the order in which they
appear in the INPUT. So for input

Code: Select all

20 1
the correct output is :

Code: Select all

Between 1 and 20, 18 generates the longest sequence of 20 values.
and not :

Code: Select all

Between 20 and 1, 18 generates the longest sequence of 20 values.
That is the first thing I wanted to mention.

2) The answer ( the sequence length ) for 1 is THREE ( 3 ). So we
should really comply with
what they show in their samples. And it is NOT TRUE that the
answer ( the sequence length ) for 1 is ONE ( 1 ). So for instance
for the input

Code: Select all

1 2
the correct output is:

Code: Select all

Between 1 and 2, 1 generates the longest sequence of 3 values.
That is the second thing that is worth mentioning in my opinion.

Andrey
New poster
Posts: 16
Joined: Sat Mar 05, 2005 8:25 pm
Location: Ukraine,Vinnitsa

Post by Andrey »

Thank u very much, i got AC!

jaracz
Learning poster
Posts: 79
Joined: Sun Sep 05, 2004 3:54 pm
Location: Poland

Post by jaracz »

I wonder 'cause i got TLE using <stdio.h> library but AC using <iostream> algo in both was the same, this's strange isn't it?:|
keep it real!

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho »

Most probably you enter in some endless loop
when you are using the stdio.h.

I mean the TLE does not occur
because stdio.h is slower.

The fact that your Input Handling ( using stdio.h ) works on
your machine does not mean it will work on the Judge machine.
I mean sometimes there are some minor compatibility/portability
issues which lead to problems similar to the one you describe.

Rocky
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:

About 371

Post by Rocky »

What Do You Mean By ENDLESS LOOP When Using <stdio.h> Sedefcho.
I Get Acc Using <stdio.h> And It Look's To Me Very Strange TO jaracz
That Ac When <iostream.h> But TLE When <stdio.h>
Can You Explaine Me More.

Thank's In Advance
Rocky

Post Reply

Return to “Volume 3 (300-399)”