Mixing
CodeForces: Creating the Contest
Clash Royale CLAN TAG#URR8PPP
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0;
up vote
5
down vote
favorite
I wrote a solution to this question. The task is to take an input of n increasing positive integers (1 ≤ n ≤ 2∙105), each entry as large as 109, 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;
c++ algorithm programming-challenge time-limit-exceeded
edited Sep 1 at 14:19
200_success
124k14144401
asked Sep 1 at 13:57
Alphanerd
304
add a comment |Â
up vote
5
down vote
favorite
I wrote a solution to this question. The task is to take an input of n increasing positive integers (1 ≤ n ≤ 2∙105), each entry as large as 109, 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;
c++ algorithm programming-challenge time-limit-exceeded
edited Sep 1 at 14:19
200_success
124k14144401
asked Sep 1 at 13:57
Alphanerd
304
add a comment |Â
up vote
5
down vote
favorite
up vote
5
down vote
favorite
I wrote a solution to this question. The task is to take an input of n increasing positive integers (1 ≤ n ≤ 2∙105), each entry as large as 109, 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;
c++ algorithm programming-challenge time-limit-exceeded
edited Sep 1 at 14:19
200_success
124k14144401
asked Sep 1 at 13:57
Alphanerd
304
I wrote a solution to this question. The task is to take an input of n increasing positive integers (1 ≤ n ≤ 2∙105), each entry as large as 109, 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;
c++ algorithm programming-challenge time-limit-exceeded
edited Sep 1 at 14:19
200_success
124k14144401
asked Sep 1 at 13:57
Alphanerd
304
edited Sep 1 at 14:19
200_success
124k14144401
edited Sep 1 at 14:19
200_success
124k14144401
edited Sep 1 at 14:19
200_success
124k14144401
124k14144401
asked Sep 1 at 13:57
Alphanerd
304
asked Sep 1 at 13:57
Alphanerd
304
asked Sep 1 at 13:57
Alphanerd
304
304
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
8
down vote
accepted
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';
edited Sep 1 at 16:16
Alphanerd
304
answered Sep 1 at 15:06
200_success
124k14144401
A minor optimization, if you assignlongestinside theelseblock before you re-assignseq_len, you only callmaxwhen a sequence ends, instead of at each iteration.
– tinstaafl
Sep 2 at 14:55
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
8
down vote
accepted
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';
edited Sep 1 at 16:16
Alphanerd
304
answered Sep 1 at 15:06
200_success
124k14144401
A minor optimization, if you assignlongestinside theelseblock before you re-assignseq_len, you only callmaxwhen a sequence ends, instead of at each iteration.
– tinstaafl
Sep 2 at 14:55
add a comment |Â
up vote
8
down vote
accepted
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';
edited Sep 1 at 16:16
Alphanerd
304
answered Sep 1 at 15:06
200_success
124k14144401
A minor optimization, if you assignlongestinside theelseblock before you re-assignseq_len, you only callmaxwhen a sequence ends, instead of at each iteration.
– tinstaafl
Sep 2 at 14:55
add a comment |Â
up vote
8
down vote
accepted
up vote
8
down vote
accepted
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';
edited Sep 1 at 16:16
Alphanerd
304
answered Sep 1 at 15:06
200_success
124k14144401
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';
edited Sep 1 at 16:16
Alphanerd
304
answered Sep 1 at 15:06
200_success
124k14144401
edited Sep 1 at 16:16
Alphanerd
304
edited Sep 1 at 16:16
Alphanerd
304
edited Sep 1 at 16:16
Alphanerd
304
304
answered Sep 1 at 15:06
200_success
124k14144401
answered Sep 1 at 15:06
200_success
124k14144401
answered Sep 1 at 15:06
200_success
124k14144401
124k14144401
A minor optimization, if you assignlongestinside theelseblock before you re-assignseq_len, you only callmaxwhen a sequence ends, instead of at each iteration.
– tinstaafl
Sep 2 at 14:55
add a comment |Â
A minor optimization, if you assignlongestinside theelseblock before you re-assignseq_len, you only callmaxwhen a sequence ends, instead of at each iteration.
– tinstaafl
Sep 2 at 14:55
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.– tinstaafl
Sep 2 at 14:55
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.– tinstaafl
Sep 2 at 14:55
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f202926%2fcodeforces-creating-the-contest%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
