Advertisement
ismaeil

Hi Raed :)

Aug 16th, 2021
1,429
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.00 KB | None | 0 0
  1. /*********************
  2. * My Solution Explane:
  3. *
  4. * 1) We can first preprocess all numbers [1 <-> 1000000]
  5. *
  6. * 2) We have an observation (By see the results of preprocessing):
  7. *       The maximum length between [1 <-> 1000000] = 525.
  8. *       So we can make a loop from 1 -> 1000000 and store the
  9. *       length of cycle that start with i in array caled "len[MaxInput]"
  10. *
  11. * 3) Now we have all lengths before reading any input.
  12. *
  13. * 4) We can using "Segment_Tree" or "Sparse Table" To get the
  14. *    Range Maximum Query (RMQ) between i and j (input numbers).
  15. *       Note:
  16. *           - I'm using segment tree because the number of test cases
  17. *             is unknown from the problem statement.
  18. *           - Maybe it can get accepted using brute force only ,
  19. *             if the number of test cases is less than 100.
  20. *           - using Segment tree can get the ans of query in O(logN)
  21. *
  22. * Thanks for the great competition AmesCom.
  23. *  
  24. * Author: Ismaeil Al-refaey.
  25. ***************************/
  26.  
  27. #include <bits/stdc++.h>
  28.  
  29. using namespace std;
  30.  
  31. const int N = 1e6 + 4e1;
  32.  
  33. /// Array that have in index i the
  34. /// length of cycle that start with i
  35. int len[N];
  36.  
  37. /// --- SegmentTree for RMQ (Range Maximum Query) --- ///
  38. class SegTree
  39. {
  40.     #define lf (p << 1) // left child
  41.     #define rg (lf | 1) // right child
  42.    
  43.     private:
  44.         vector< int > Seg;
  45.        
  46.         void compain(int &res ,int l , int r)
  47.         {
  48.             res = max(l ,r);
  49.         }
  50.        
  51.         void BLD(int p ,int L ,int R)
  52.         {
  53.             if( L == R )
  54.             {
  55.                 Seg[p] = len[L];
  56.                 return;
  57.             }
  58.            
  59.             int Mid = (L + R) >> 1;
  60.             BLD(lf ,L ,Mid);
  61.             BLD(rg ,Mid + 1 ,R);
  62.             compain(Seg[p] ,Seg[lf] ,Seg[rg]);
  63.         }
  64.        
  65.         int QRY(int i ,int j ,int p ,int L ,int R)
  66.         {
  67.             if( R <  i || L >  j ) return INT_MIN;
  68.             if( i <= L && R <= j ) return Seg[p];
  69.            
  70.             int Mid = (L + R) >> 1 ,res;
  71.             int LF = QRY(i ,j ,lf ,L ,Mid);
  72.             int RG = QRY(i ,j ,rg ,Mid + 1 ,R);
  73.             compain(res ,LF ,RG);
  74.             return res;
  75.         }
  76.        
  77.     public:
  78.         SegTree(int n)
  79.         {
  80.             Seg.assign(4 * n ,INT_MIN);
  81.         }
  82.    
  83.         void BLD()
  84.         {
  85.             BLD(1 ,1 ,N - 1);
  86.         }
  87.        
  88.         /// --- Function to get RMQ between (i ,j)
  89.         int QRY(int i ,int j)
  90.         {
  91.             return QRY(i ,j ,1 ,1 ,N - 1);
  92.         }
  93. };
  94.  
  95. /// --- This function calc the length of cycle that start with n --- ///
  96. int getLen(int64_t n)
  97. {
  98.     int lenOfSequence = 1;
  99.    
  100.     /// --- Implement the operations --- ///
  101.     while( n > 1 )
  102.     {
  103.         if( n <= 1 ) break;
  104.         if( n & 1 )
  105.         {
  106.             n *= 3;
  107.             n += 1;
  108.         }
  109.         else n /= 2;
  110.        
  111.         lenOfSequence += 1;
  112.     }
  113.    
  114.     return lenOfSequence;
  115. }
  116.  
  117. int main()
  118. {
  119.     /// --- PreProcessing lengths --- ///
  120.     for(int i = 1 ; i < N ; i++) len[i] = getLen(i);
  121.    
  122.     /// --- Maximum Segment Tree --- ///
  123.     SegTree st(N + 1);
  124.     st.BLD();
  125.    
  126.     int i ,j;
  127.     /// --- Querys processing --- ///
  128.     while( scanf("%d%d" ,&i ,&j) != EOF )
  129.     {
  130.         /// --- print the correct i,j --- ///
  131.         printf("%d %d " ,i ,j);
  132.        
  133.         if( i > j ) swap(i ,j);
  134.        
  135.         /// --- Get the max length between i and j using segment tree --- ///
  136.         int maxLen = st.QRY(i ,j);
  137.        
  138.         /// --- Output --- ///
  139.         printf("%d\n" ,maxLen);
  140.     }
  141. }
  142.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement