collatz_conjecture

/*********************
* My Solution Explane:
*
* 1) We can first preprocess all numbers [1 <-> 1000000]
*
* 2) We have an observation (By see the results of preprocessing):
*       The maximum length between [1 <-> 1000000] = 525.
*       So we can make a loop from 1 -> 1000000 and store the
*       length of cycle that start with i in array caled "len[MaxInput]"
*
* 3) Now we have all lengths before reading any input.
*
* 4) We can using "Segment_Tree" or "Sparse Table" To get the
*    Range Maximum Query (RMQ) between i and j (input numbers).
*       Note:
*           - I'm using segment tree because the number of test cases
*             is unknown from the problem statement.
*           - Maybe it can get accepted using brute force only ,
*             if the number of test cases is less than 100.
*           - using Segment tree can get the ans of query in O(logN)
*
* Thanks for the great competition AmesCom.
*
* Author: Ismaeil Al-refaey.
***************************/

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 4e1;

/// Array that have in index i the
/// length of cycle that start with i
int len[N];

/// --- SegmentTree for RMQ (Range Maximum Query) --- ///
class SegTree
{
    #define lf (p << 1) // left child
    #define rg (lf | 1) // right child

    private:
        vector< int > Seg;

        void compain(int &res ,int l , int r)
        {
            res = max(l ,r);
        }

        void BLD(int p ,int L ,int R)
        {
            if( L == R )
            {
                Seg[p] = len[L];
                return;
            }

            int Mid = (L + R) >> 1;
            BLD(lf ,L ,Mid);
            BLD(rg ,Mid + 1 ,R);
            compain(Seg[p] ,Seg[lf] ,Seg[rg]);
        }

        int QRY(int i ,int j ,int p ,int L ,int R)
        {
            if( R <  i || L >  j ) return INT_MIN;
            if( i <= L && R <= j ) return Seg[p];

            int Mid = (L + R) >> 1 ,res;
            int LF = QRY(i ,j ,lf ,L ,Mid);
            int RG = QRY(i ,j ,rg ,Mid + 1 ,R);
            compain(res ,LF ,RG);
            return res;
        }

    public:
        SegTree(int n)
        {
            Seg.assign(4 * n ,INT_MIN);
        }

        void BLD()
        {
            BLD(1 ,1 ,N - 1);
        }

        /// --- Function to get RMQ between (i ,j)
        int QRY(int i ,int j)
        {
            return QRY(i ,j ,1 ,1 ,N - 1);
        }
};

/// --- This function calc the length of cycle that start with n --- ///
int getLen(int64_t n)
{
    int lenOfSequence = 1;

    /// --- Implement the operations --- ///
    while( n > 1 )
    {
        if( n <= 1 ) break;
        if( n & 1 )
        {
            n *= 3;
            n += 1;
        }
        else n /= 2;

        lenOfSequence += 1;
    }

    return lenOfSequence;
}

int main()
{
    /// --- PreProcessing lengths --- ///
    for(int i = 1 ; i < N ; i++) len[i] = getLen(i);

    /// --- Maximum Segment Tree --- ///
    SegTree st(N + 1);
    st.BLD();

    int i ,j;
    /// --- Querys processing --- ///
    while( scanf("%d%d" ,&i ,&j) != EOF )
    {
        /// --- print the correct i,j --- ///
        printf("%d %d " ,i ,j);

        if( i > j ) swap(i ,j);

        /// --- Get the max length between i and j using segment tree --- ///
        int maxLen = st.QRY(i ,j);

        /// --- Output --- ///
        printf("%d\n" ,maxLen);
    }
}