Uva Online Judge problem 100, 3n + 1

Question

I am having a tough time submitting this code to UVa Online judge and having it pass. I keep getting the message - Your program used more CPU time than what is allowed for this problem. That means that your algorithm is not fast enough or that it entered into an infinite loop.

The challenge: for each line of input, which contains two integers i and j, find the length of the longest collatz-sequence for all Collatz sequences starting with i, i + 1, i + 2, ..., j. You can assume that no operation overflows a 32-bit integer.

I have no idea where the problem is! Any help would be appreciated. Also, I am trying to analyze the algorithm, and I believe it should be O(n²).

 #include <iostream>
 using namespace std;
 int cycleLength(int n) {
 int i = 1; 
 while (n != 1) {
 if (n % 2 == 0) {
 n = n/2;
 } else {
 n = 3*n + 1;
 }
 i++;
 }
 return i;
 }
 int main() {
 int fOriginal, sOriginal;
 int first, second, max, temp;
 while (cin >> fOriginal >> sOriginal) {
 if (fOriginal > sOriginal) {
 temp = fOriginal;
 first = sOriginal;
 second = temp;
 }
 max = cycleLength(first); 
 for(int i = first + 1; i <= second; i++) {
 temp = cycleLength(i);
 if (temp > max) {
 max = temp;
 }
 }
 cout << fOriginal << " " << sOriginal << " " << max << endl;
 }
 return 0;
 }

Answer 1

For each number in a first, second range you count how long does the sequence take to reach 1. It is definitely too much of the work: you'd surely encounter same numbers over and over again. Instead of recalculating sequence tails for them, it is much faster to remember and reuse such intermediate results. Since it is a contest problem I am not going to share any code.

Also, I am very interested in how did you come up with \$O(n^2)\$.

• mitchr06: I figured out the mistake! I'll post the revision below. I am bit shaky on algorithm analysis. But my logic is that the while loop can take n arguments, and the for loop can occur m times. So actually I meant to say O(nm). Does that sound right?

Answer 2

My variables first and second where never initialized. They had garbage at the start the program, and only contained the correct values when the if statement was executed.

I am still unsure on the analysis of the algorithm. I think it should be O(nm), where n is the input for the while loop, and m is amount of iterations taking place in the for loop.

#include <sstream>
#include <iostream>
#include <string>
#include <stack>
#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <chrono>
#include <ratio>
#include <assert.h>
using namespace std;
int cycleLength(int n) {
 int i = 1; 
 while (n != 1) {
 if (n % 2 == 0) {
 n = n/2;
 } else {
 n = 3*n + 1;
 }
 i++;
 }
 return i;
}
int main() {
 int fOriginal, sOriginal;
 int first, second, max, temp;
 while (cin >> first >> second) {
 fOriginal = first;
 sOriginal = second;
 if (first > second) {
 temp = fOriginal;
 first = sOriginal;
 second = temp;
 }
 max = cycleLength(first); 
 for(int i = first + 1; i <= second; i++) {
 temp = cycleLength(i);
 if (temp > max) {
 max = temp;
 }
 }
 cout << fOriginal << " " << sOriginal << " " << max << endl;
 }
 return 0;
}