I have a Time limit exceeded issue in problem 100 from UVa.
the question is here: https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=36
Here is my code. Please help me find a solution. How can I avoid such problems? I don't know if it is the problem with cin and cout or the while loops? this program works well in my terminal when I run it.
#include <iostream>
using namespace std;
int main()
{
int i , j, temp, n;
while (cin >> i >> j) //asking for user input
{
int x, y;
x = i;
y = j;
if (i > j) //sorting i and j to fix the order of numbers
{
temp = j;
j = i;
i = temp;
}
int answer = 0;
int counter;
while (i <= j)
{
n = i;
counter = 1; // make the value of counter to 1 because it increases if i is 1
while (1)
{
if(n == 1) { //if n = 1 then stop
break;
} else if (n % 2 == 0) //cheak if i is odd
{
n = (3 % n) 1;
} else {
n = n / 2; //cheak if i is even
}
counter ; //increase by one for every number that is not 1
}
if (counter > answer)
{
answer = counter;
}
i ;
}
cout << x << " " << y << " " << answer << "\n";
}
return 0;
}
Thanks in advance
CodePudding user response：
In this line n = (3 % n) 1;, (3 % n) means that you take the remainder of 3 divided by n, which is probably not what you want. Change that to 3 * n
CodePudding user response：
In my humble opinion this problem is not about calculating the resulting values using the given algorithm. Because of the simplicity this is just some noise. So,maybe we are talking about a XY Problem here.
Maybe I am wrong, but the main problem here seems to be memoization.
It maybe that values need to be calculated over and over again, because they are in some overlapped range. And this is not necessary.
So, we could memorize already calculated values, for example in a std::unordered_map (or std::map). So, something like in the below:
unsigned int getSteps(size_t index) noexcept {
unsigned counter{};
while (index != 1) {
if (index % 2) index = index * 3 1;
else index /= 2;
counter;
}
return counter 1;
}
unsigned int getStepsMemo(size_t index) {
// Here we will memorize whatever we calculated before
static std::unordered_map<unsigned int, unsigned int> memo{};
// Resulting value
unsigned int result{};
// Look, if we did calculate the value in the past
auto iter = memo.find(index);
if (iter != memo.end())
// If yes, then reuse old value
result = iter->second;
else {
// If no, then calculate new and memorize it
result = getSteps(index);
memo[index] = result;
}
return result;
}
This will help with many given input pairs. It will avoid recalculating steps for already calculated values.
But having thought in this direction, we can also calculate all values at compile time and store them in a constexpr std::array. Then no calculation will be done during runtime. All steps for any number up to 10000 will be precalculated. So, the algorithm will never be called during runtime.
It should be clear that this is the fastest possible algorithm, because we do nothing. Just get the value from a lookup table.
And if we want to make things nice, then we pack everything in a class and let the class encapsulate the problem. Even input and output operatores will be overwritten and used for our own purposes.
And in the end, we will have an ultra fast one liner in our function main. Please see:
#include <iostream>
#include <utility>
#include <sstream>
#include <array>
#include <algorithm>
#include <iterator>
#include <unordered_map>
// All done during compile time -------------------------------------------------------------------
constexpr unsigned int getSteps(size_t index) noexcept {
unsigned counter{};
while (index != 1) {
if (index % 2) index = index * 3 1;
else index /= 2;
counter;
}
return counter 1;
}
// Some helper to create a constexpr std::array initilized by a generator function
template <typename Generator, size_t ... Indices>
constexpr auto generateArrayHelper(Generator generator, std::index_sequence<Indices...>) {
return std::array<decltype(std::declval<Generator>()(size_t{})), sizeof...(Indices) > { generator(Indices 1)... };
}
template <size_t Size, typename Generator>
constexpr auto generateArray(Generator generator) {
return generateArrayHelper(generator, std::make_index_sequence<Size>());
}
constexpr size_t MaxIndex = 10000;
// This is the definition of a std::array<unsigned long long, 10000> with all step counts
constexpr auto steps = generateArray<MaxIndex>(getSteps);
// End of: All done during compile time -----------------------------------------------------------
// Some very simple helper class for easier handling of the functionality
struct StepsForPair {
// A pair with special functionality
unsigned int first{};
unsigned int second{};
// Simple extraction operator. Read 2 values
friend std::istream& operator >> (std::istream& is, StepsForPair& sfp) {
return is >> sfp.first >> sfp.second;
}
// Simple inserter. Sort first and second value and show result
friend std::ostream& operator << (std::ostream& os, const StepsForPair& sfp) {
unsigned int f{ sfp.first }, s{ sfp.second };
if (f > s) std::swap(f, s);
return os << sfp.first << ' ' << sfp.second << ' ' << *std::max_element(&steps[f], &steps[s]);
}
};
// Some test data. I will not use std::cin, but read from this std::istringstream here
std::istringstream testData{ R"(1 10
100 200
201 210
900 1000
22 22)" };
int main() {
// Read all input data and generate output
std::copy(std::istream_iterator<StepsForPair>(testData), {}, std::ostream_iterator<StepsForPair>(std::cout,"\n"));
}
Please note, since I do not have std::cin here on SO, I read the test values from a std::istringstream. Because of the overwritten extractor operator, this is easily possible.
If you want to read from std::cin then please replace in the std::copy statement in main "testData" eith "std::cin".
If you want to read from a file, then put a fileStream variable in there.