TLE in 3n+1 Problem. Why?

Write here if you have problems with your C++ source code

Moderator: Board moderators

TLE in 3n+1 Problem. Why?

Postby Pete_Aye » Tue Feb 19, 2013 9:49 am

Please can anyone tell me why this code is giving me TLE, and how I can make it Accepted?

Code: Select all
#include <iostream>

using namespace std;

int main(){
   int start, stop, stopHold;
   while(true){
      std::cin >> start  >> stop;
      if(start > 1000000 || start <= 0 || stop > 1000000 || stop <= 0){
         break;
      }
      stopHold = stop;
      int max = 0;
      int counter = 1;
      int i;
      int temp = stop;
      do{
         i = temp;
         counter = 1;
         while(i > 1){
            counter++;
            if(i%2 == 0){
               i /= 2;
            }else{
               i = i * 3 + 1;
            }
         }
         if(max < counter){
            max = counter;
         }
         temp--;
      }while(temp > start);
      std::cout << start << " " << stopHold << " " << max << std::endl;
   }
   return 0;
}
Pete_Aye
New poster
 
Posts: 2
Joined: Tue Feb 19, 2013 9:28 am
Location: Jos, Nigeria

Re: TLE in 3n+1 Problem. Why?

Postby Darko » Tue Feb 19, 2013 10:40 pm

There is a sticky thread in Volume I but one of the problems you have is that you assume start <= stop.
Darko
Guru
 
Posts: 579
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Re: TLE in 3n+1 Problem. Why?

Postby Pete_Aye » Wed Feb 20, 2013 1:36 am

Darko wrote:There is a sticky thread in Volume I but one of the problems you have is that you assume start <= stop.

Yes, I noticed that from reading other threads, and I have corrected that error. The issue is that now the code is working, and I tested it with the n =1000000 case and there was no 'TLE'. So why am I gettting that on the judge?
Pete_Aye
New poster
 
Posts: 2
Joined: Tue Feb 19, 2013 9:28 am
Location: Jos, Nigeria

Re: TLE in 3n+1 Problem. Why?

Postby Darko » Wed Feb 20, 2013 4:45 am

I am not sure how you think you fixed the start>stop issue but it is not fixed in the code you posted.
Try
999999 1

I am not familiar with C++ that much but I am not sure that is how you determine that you reached the end of file.

There is a link to a C solution (if you click around the site):
http://online-judge.uva.es/problemset/data/p100.c.html
Darko
Guru
 
Posts: 579
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada


Return to C++

Who is online

Users browsing this forum: No registered users and 1 guest