The given problem is: A multitude of natural numbers "N" is given. Operation half subtracts the largest element of the set, divides it into two equal parts and returns the two resulting numbers to the set. The task is to find the largest number in the set when the half operation is applied "n" times.
Input Format
For each example of the standard input are given: "N" the number of numbers in the set, and the elements of the multiple "n";
Constrains
0<= N <= 100 0<=n <= 2000000
Output: A fraction or a whole number.
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cassert>
using namespace std;
class Fraction{
public:
Fraction(int t) : top(t), bottom(1) {}
Fraction(int t, int b) : top(t), bottom(b)
{
normalize();
}
int numerator() const
{
return top;
}
int denominator() const
{
return bottom;
}
int compare(const Fraction& right) const
{
return numerator() * right.denominator() - denominator() * right.numerator();
}
private:
void normalize()
{
int sign = 1;
if(top < 0)
{
sign = -1;
top = -top;
}
if(bottom < 0)
{
sign = -1;
bottom = -bottom;
}
assert(bottom != 0);
int d = 1;
if(top > 0) d = gcd(top, bottom);
top = sign *(top / d);
bottom = bottom / d;
}
int gcd(int n, int m)
{
assert(n > 0 && m > 0);
while(n!=m)
{
if(n < m)
m -= n;
else
n -= m;
}
return n;
}
int top;
int bottom;
};
Fraction operator/(const Fraction& left, const Fraction& right)
{
Fraction result(left.numerator() * right.denominator(),
left.denominator() * right.numerator());
return result;
}
bool operator<(const Fraction& left, const Fraction& right)
{
return left.compare(right) < 0;
}
ostream& operator<<(ostream& out, const Fraction& value)
{
if(value.denominator() != 1)
out << value.numerator() << "/" << value.denominator();
else
out << value.numerator();
return out;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N,n;
while(cin >> N && cin >> n)
{
vector<Fraction> vec;
for(int i = 0; i < N; i )
{
int value;
cin >> value;
vec.push_back(value);
}
for(int i = 0; i < n; i )
{
Fraction temp = *max_element(vec.begin(), vec.end()) / 2;
int maxIndex = distance(vec.begin(), max_element(vec.begin(), vec.end()));
vec[maxIndex] = temp;
vec.push_back(temp);
}
cout << *max_element(vec.begin(), vec.end())<< endl;
}
return 0;
}
The code does work but my problem is its Terminated due to timeout in hackerrank I've also tried sorting it and tanking the last element but it's even slower than max_element. I am looking for a way to optimize my code or an idea for a completely different approach.
Here is implementation with make_heap as well but it goes through 800 iterations and it geves me timeout (should be able to handle 2000000)
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N,n;
while(cin >> N && cin >> n)
{
vector<Fraction> vec;
for(int i = 0; i < N; i )
{
int value;
cin >> value;
vec.push_back(value);
}
make_heap(vec.begin(),vec.end());
for(int i = 0; i < n; i )
{
cout << "was here: " << i << endl;
vec.push_back(vec.front() / 2); push_heap(vec.begin(),vec.end());
vec.push_back(vec.front() / 2); push_heap(vec.begin(),vec.end());
pop_heap(vec.begin(),vec.end()); vec.pop_back();
}
cout<< vec.front() << '\n';
}
return 0;
}
Tried it with priority_queue as well and it also has exactly 736 iterations before it terminates due to timeout
int main() {
int N,n;
while(cin >> N && cin >> n)
{
priority_queue<Fraction> frac;
for(int i = 0; i < N; i )
{
int value;
cin >> value;
frac.push(value);
}
for(int i = 0; i < n; i )
{
Fraction temp = frac.top() / 2;
frac.pop();
frac.push(temp);
frac.push(temp);
}
cout << frac.top() << endl;
}
return 0;
}
If anyone is wondering this is the solution:
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N,n;
while(cin >> N && cin >> n)
{
vector<pair<Fraction, int>> vec;
for(int i = 0; i < N; i )
{
int value;
cin >> value;
vec.push_back(make_pair(value,1));
}
sort(vec.begin(),vec.end());
while(vec.back().second <= n)
{
n -= vec.back().second;
pair<Fraction,int> temp(vec.back().first / 2, vec.back().second * 2);
vec.pop_back();
vec.push_back(temp);
sort(vec.begin(),vec.end());
}
cout << vec.back().first << endl;
}
return 0;
}
CodePudding user response：
The trick that you need is that you don't need to list all the numbers, you just need to have the number and count of how many there are.
That is instead of using a Fraction, use a std::pair<Fraction, int>. The key loop becomes the following pseudocode
while (count of top element < n)
{
n -= count of top element
temp = (value of top element / 2, count of top element * 2)
remove top element
push temp
}
Currently in each loop iteration you do one step and grow your data structure. But with this approach, each loop iteration does many steps and the data structure never changes size.
Your worst case situation is if N = 100 and n = 2000000. Then you wind up having to go through the loop 2000000 times and have a data structure with 2000100 Fraction objects in it.
With this improvement, your first 100 times through the loop you do 100 steps, your next 100 times you do 200 steps, your next 100 times you do 400 steps, and so on. As a result in 100k loops you do (2^k-1) * 100 steps. So in 1500 loops you have done over 2 million steps, and you still only have 100 pairs of data.