ZeroJudge D712: The 3n + 1 problem

Please consider the following:

1. Input N
2. Output N
3. If N = 1, then ends
4. If N is an odd number, then N = 3*N + 1
5. Else, N = N/2
6. GOTO 2

For example, given the input 22, the resulting sequence is 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1.

The algorithm is expected to terminate for any integer (when it prints 1). While this algorithm is simple, whether the conjecture holds true for all N (0 < N <= 1,000,000) cannot be known. However, it has been verified that the conjecture holds true for all N (0 < N <= 1,000,000).

Given an input N, through the above algorithm, we can obtain a sequence of numbers (ending with 1). The length of this sequence is called the Cycle Length of N. As mentioned above, for example: the Cycle Length of 22 is 16.

The question is: For any two integers i and j, we want to know the maximum Cycle Length generated by the numbers between i and j (inclusive).

Sample Inputs/Outputs

Thought Process

This problem can be approached by creating a table from 1 to 1,000,000, but running the 3N+1 function 1,000,000 times can still be time-consuming. However, it's noticeable that when N is divisible by 2, the return value of its 3N+1 function will be the return value of N/2 plus 1. Utilizing this fact, we only need to evaluate the "odd numbers" from 1 to 1,000,000.

To optimize further, besides creating a table for the return values of the 3N+1 function, we also need to construct a segment tree for the maximum values from i to j. Then, we can create a query function to compute the maximum value from i to j. This approach ensures that the solution won't result in Time Limit Exceeded (TLE). Additionally, i can be greater than j in the test cases, in which case we need to swap(i, j). However, when outputting the results, we still need to adhere to the original order. This detail needs attention.

Sample Code－ZeroJudge D712: The 3n + 1 problem

#include <iostream>
using namespace std;

int MAP[1000005] = {};
int a, b, maxx = -1;
int tree[3000000] = {};

void initial() {
    for(int i = 2; i < 1000001; i++)
    {
        long long int c = i;
        int count = 1;
        if(i % 2 == 0)
        {
            MAP[i] = MAP[i>>1]+1;
            continue;
        }
        while(c >= i)
        {
            if(c % 2)
            {
                c = c*3+1;
                c >>= 1;
                count+=2;
            }
            else
            {
                c = c>>1;
                count++;
            }
        }
        MAP[i] = count + MAP[c]-1;
    }
}

void build(int l, int r, int index)
{
    if (l == r)
    {
        tree[index] = MAP[l];
        return;
    }
    build(l, (l+r)/2, (2*index)+1);
    build(((l+r)/2)+1, r, (2*index)+2);
    tree[index] = max(tree[(index*2)+1], tree[(index*2)+2]);
    return;
}

void query (int l, int r, int index)
{
    if (a <= l && r <= b)
    {
        maxx = max(maxx, tree[index]);
        return;
    }
    if (l == r)
    {
        maxx = max(maxx, tree[index]);
        return;
    }
    int half = (l+r)/2;
    if (a <= half)
    {
        query(l, half, (index*2)+1);
    }
    if (b > half) query (half+1, r, (index*2)+2);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    cout.sync_with_stdio(0);
    cout.tie(0);
    MAP[1] = 1;
    initial();
    build(1, 1000000, 0);
    while (cin >> a >> b)
    {
        int c = a;
        int d = b;
        if (a > b) swap(a, b);
        maxx = -1;
        query(1, 1000000, 0);
        cout << c << " " << d << " " << maxx << "\n";
    }
}

//ZeroJudge D712
//Dr. SeanXD