From: Echo_
But if k is constant, wouldn't the list just contain a bunch of duplicates after k? Like the example:
m = { 2, 3, 0 }
m[3] = 1
Since k didn't change, and you don't consider the addition of 1 to the list for computing the next value, m[4] would just be 1 again. and etc.
After K elements, it begins to repeat itself.. but, they wanted the array to be of size N. I was so confused because the question was worded weird.
Example (Posted by some guy):
if k=10
and the 10 first values are = 1,2,3,1,2,3,1,2,3,1
the next will be : 0,4,5,6,7,8,9,10,2,3,1,…..
"1,2,3,1,2,3,1,2,3,1" => lowest not used value : 0
"2,3,1,2,3,1,2,3,1,0" => lowest not used value : 4
"3,1,2,3,1,2,3,1,0,4" => lowest not used value : 5
….
"2,3,1,0,4,5,6,7,8,9" => lowest not used value : 10
"3,1,0,4,5,6,7,8,9,10" => lowest not used value : 2
"1,0,4,5,6,7,8,9,10,2" => lowest not used value : 3
"0,4,5,6,7,8,9,10,2,3" => lowest not used value : 1
after, it will repeat at " 0,4,5,6,7,8,9,10,2,3,1,….." again and again
Here's the thing.. When I read the file, I saw a number like:
1000000000 100000
999999999 1 999999999 1000000000
Thus your array has to be 1000000000 elements in size and you must calculate the first 100000 elements..
There are 20 cases like this in the file.. It took 14 minutes for my Computer to calculate it.. Thus I was not able to upload it within the 6 minute timeframe.. Instead, I just uploaded the source which worked on the Example input rather than the actual file..
Hopefully, they accepted that.. I read somewhere that they expected us to do 3 with hash tables inorder to reach the 6 minute mark.. Still.. I'm sure it'd have taken almost as long.
I used stack allocated arrays.. I'm pretty sure it'd take just as long with Heap arrays. Some guys got blue screens, out of memory errors, stack overflows, Kernel Panics.. Some attempted to use recursion ahahaha.
Here is my final source which worked:
#include <iostream>
#include <fstream>
#include <vector>
#include <sstream>
#include <algorithm>
#include <stdexcept>
template<typename T>
std::string ToString(T Type)
{
std::stringstream SS;
SS<<Type;
return SS.str();
}
template <typename T>
T ToNumber(const std::string &Text)
{
std::istringstream SS(Text);
T Result;
return (SS >> Result ? Result : 0);
}
std::ostream& operator << (std::ostream& Str, const std::vector<int>& IA)
{
if (!IA.empty())
{
Str<<"[";
for (std::size_t I = 0; I < IA.size() - 1; ++I)
{
Str<<IA[I]<<", ";
}
Str<<IA[IA.size() - 1]<<"]";
}
else
{
Str<<"[]";
}
return Str;
}
std::vector<std::string> ReadFileEx(const std::string& FileName, bool BinaryMode)
{
std::string Line;
std::vector<std::string> Result;
std::_Ios_Openmode OpenMode;
if (BinaryMode)
OpenMode = std::ios::in | std::ios::binary;
else
OpenMode = std::ios::in;
std::ifstream File(FileName.c_str(), OpenMode);
if (File.is_open())
{
while (std::getline(File, Line))
{
Result.push_back(Line);
}
File.close();
}
return Result;
}
std::vector<std::string> SplitString(std::string StringToSplit, std::string Delimiter)
{
std::vector<std::string> Result;
std::size_t Pos = StringToSplit.find_first_of(Delimiter);
while(Pos != std::string::npos)
{
if(Pos > 0)
{
Result.push_back(StringToSplit.substr(0, Pos));
}
StringToSplit = StringToSplit.substr(Pos + 1);
Pos = StringToSplit.find_first_of(Delimiter);
}
if(StringToSplit.length() > 0)
{
Result.push_back(StringToSplit);
}
return Result;
}
std::vector<int> StringsToIntegers(std::vector<std::string> Strings)
{
std::vector<int> Result;
for (unsigned I = 0; I < Strings.size(); ++I)
{
Result.push_back(ToNumber<int>(Strings[I]));
}
return Result;
}
std::vector<int> GetKnownValues(std::vector<int> Numbers, std::vector<int> GeneratedNumbers, int &N, int &K)
{
N = Numbers[0];
K = Numbers[1];
std::vector<int> M(K);
int A = GeneratedNumbers[0];
int B = GeneratedNumbers[1];
int C = GeneratedNumbers[2];
int R = GeneratedNumbers[3];
M[0] = A;
for (int I = 1; I < K; ++I)
{
M[I] = (B * M[I - 1] + C) % R;
}
return M;
}
void Process(std::vector<int> &KnownValues, int K, unsigned N)
{
std::vector<int> Numbers(K);
std::copy(KnownValues.end() - K, KnownValues.end(), Numbers.begin());
std::sort(Numbers.begin(), Numbers.end());
int MinValue = 0;
for (unsigned I = 0; I < Numbers.size(); ++I)
{
if (Numbers[I] == MinValue)
{
++MinValue;
I = -1;
continue;
}
}
KnownValues.push_back(MinValue);
}
int main()
{
std::stringstream Output;
std::vector<std::string> Lines = ReadFileEx("find_the_mintxt.txt", false);
int LineCount = ToNumber<int>(Lines[0]);
if (LineCount < 1 || LineCount > 50)
throw std::invalid_argument("ERROR! Invalid contraint. Required: 1 <= T <= 50. Got: " + Lines[0]);
int N = 0, K = 0;
for (int I = 1, J = 1; I < LineCount * 2; I += 2, ++J)
{
std::vector<int> Known = GetKnownValues(StringsToIntegers(SplitString(Lines[I], " ")), StringsToIntegers(SplitString(Lines[I + 1], " ")), N, K);
for (int L = K; L < N; ++L)
Process(Known, K, N);
Output<<"Case #"<<J<<": "<<Known[N - 1]<<"\n\n";
}
std::cout<<Output.str();
std::fstream File("Output.txt", std::ios::out);
if (File.is_open())
{
File<<Output.str();
}
return 0;
}