371 - Ackermann Functions

[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]

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]

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

[CodeMaker]

easy.......isn't it?

[sunmoon]

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

I used memoization.

[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]

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.

[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]

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]

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.

[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]

Thank u very much, i got AC!

[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?:|

[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]

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