CodeForces: Creating the Contest

Question

I wrote a solution to this question. The task is to take an input of n increasing positive integers (1 ≤ n ≤ 2∙10⁵), each entry as large as 10⁹, and find the length of the longest subsequence where each element is no more than double the previous element.

Example input

10
1 2 5 6 7 10 21 23 24 49

Example output

4

... because the longest subsequence is [5, 6, 7, 10].

---

My solution works for small numbers, but exceeds the time limit for big inputs.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{ 
 int n,a,c=1,max_count=1;
 cin>>n;
 vector<int>v;
 for(int i=0;i<n;i++)
 {
 cin>>a;
 v.push_back(a);
}
for(int i=0;i<n;i++)
{
 int l=i+1;
 while((l<n)&&(v[l]<=2*v[i]))
 {
 c++;
 l++;
 max_count=max(max_count,c);
 }
 c=1;
}
cout<<""<<max_count;
return 0;
}

Answer 1

There is no need to store the entries in a vector. There is also no need for a nested loop. This solution will run in O(n) time and O(1) space.

Technically, int is only guaranteed to hold up to 16 bits. Use long to ensure that you can accommodate the limits.

Also, please avoid using namespace std;. You can drop the useless cout<<"".

#include <algorithm>
#include <iostream>
int main() {
 long n, a, seq_len = 0, longest = 0;
 std::cin >> n;
 for (long prev_a = 0; n--; prev_a = a) {
 std::cin >> a;
 if (a <= 2 * prev_a) {
 seq_len++;
 } else {
 seq_len = 1;
 }
 longest = std::max(longest, seq_len);
 }
 std::cout << longest << '\n';
}

• user33306: A minor optimization, if you assign longest inside the else block before you re-assign seq_len, you only call max when a sequence ends, instead of at each iteration.