This is the second problem of Div.3. But I think it is not easy.↵
↵
Problem:[problem:1029B]↵
↵
Simple Meaning of Problem:↵
↵
There is a sequence $a$ and you should choose the longest sequence $b$ ${a_{i_1}, a_i_2, \dots, a_{i_p}}$ ($p$ is the length of $b$) such that:each $j∈[1,k)$ $a_{i_{j+1}} \le a_{i_j} \cdot 2$ should hold.↵
↵
print the maximum number of $p$ (the length of $b$)↵
↵
↵
First, you can enumerate which ones to choose. You will get a algorithm with $O(2^n)$. And you will get a Time Limit Exceed.(I didn't write it, because it is valueless.)↵
↵
Then, dp is another useful algorithm. So we can try to use dp.↵
↵
$f[i]$ means that if you choose the number $a_i$, you can get the maximum $p$ (only of $1$ to $i$).↵
↵
It is very easy to get the state transition equation:↵
↵
$f[i]=max{f[j]}+1$, $j$ satisfy that $a_i \le a_j \cdot 2$ and $j \le i$.↵
↵
And the answer is $max{f[i]}$ ($i$ is $1$ to $n$).↵
↵
code:[submission:42093398]↵
↵
~~~~~↵
#pragma comment (linker,"/STACK:1024000000") ↵
#pragma GCC optimize(2)↵
#pragma GCC target(arch=corie7-acx)↵
#include<bits/stdc++.h>↵
using namespace std;↵
int n,a[200001],f[200001];↵
deque <int> q;↵
int t,ans;↵
int main()↵
{↵
scanf("%d",&n);↵
for (int i=1;i<=n;i++)↵
scanf("%d",&a[i]);↵
f[1]=1;↵
for (int i=2;i<=n;i++)↵
{↵
for (int j=1;j<=i-1;j++)↵
if (a[j]*2>=a[i]) f[i]=max(f[i],f[j]);↵
f[i]++;↵
}↵
for (int i=1;i<=n;i++)↵
ans=max(ans,f[i]);↵
printf("%d",ans);↵
return 0;↵
}↵
~~~~~↵
↵
And this code does better:[submission:42095786](In fact, it also Time Limit Exceed on Test 4)↵
↵
~~~~~↵
#pragma comment (linker,"/STACK:1024000000") ↵
#pragma GCC optimize(2)↵
#pragma GCC target(arch=corie7-acx)↵
#include<bits/stdc++.h>↵
using namespace std;↵
int n,a[200001],f[200001];↵
deque <int> q;↵
int t,ans;↵
int main()↵
{↵
scanf("%d",&n);↵
for (int i=1;i<=n;i++)↵
scanf("%d",&a[i]);↵
f[1]=1;↵
for (int i=2;i<=n;i++)↵
{↵
for (int j=i-1;j>=1;j--)↵
if (a[j]*2>=a[i]) f[i]=max(f[i],f[j]);↵
else break;↵
f[i]++;↵
}↵
for (int i=1;i<=n;i++)↵
ans=max(ans,f[i]);↵
printf("%d",ans);↵
return 0;↵
}↵
~~~~~↵
↵
But, unfortunately, these two are both Time Limit Exceed. (Actually, it is inevitable.)↵
↵
Because when $a_n \le a_1 \cdot 2$, the time complexity of the code will come to $O(n^2)$ (`break` is useless).↵
↵
So it is inevitable that the code will TLE.↵
↵
Now, how can we optimize our algorithm?↵
↵
In the problem, notice that the numbers are increasing.↵
↵
So when $i$ is increasing, $a_i$ is increasing, too. And $\frac {a_i} {2}$ is increasing, so the number which is less than $\frac {a_i} {2}$ is also increasing.↵
↵
Because of this, for the increasing number $i$, the $j$ which is satisfy $a_i \le a_j \cdot 2$ is increasing as well.↵
↵
↵
So we can maintain a queue. The number of the queue means the number of $a$'s number.↵
↵
When we want to calculate $f[i]$, we check the numbers of queue from the front to the back. For each $x$, if $a_x \cdot 2 < a_i$, we can pop $x$. (Because for the after $j$, $a_j \ge a_i > a_x \cdot 2$).↵
↵
We can find the first $x$ which is satisfy $a_x \cdot 2 \ge a_i$. Then we use $f[x]$ to calculate $f[i]$. (It will be proven after).↵
↵
Finally, we get the back of $q$ $y$. If $f[y] \le f[i]$, we can pop $y$. That's because $y$ must be popped earlier than $i$, and $f[i]$ is greater than $f[y]$. So the following number choose $f[i]$ is greater than $f[y]$.↵
↵
And that's why the first number of the queue $x$ is the best choice to transfer $f[i]$ after popping. (In fact, it is a priority queue.)↵
↵
When we code it, we can use double-end-queue (deque).↵
↵
code:[submission:42036114]↵
↵
~~~~~↵
#pragma comment (linker,"/STACK:1024000000") ↵
#pragma GCC optimize(2)↵
#pragma GCC target(arch=corie7-acx)↵
#include<bits/stdc++.h>↵
using namespace std;↵
int n,a[200001],f[200001];↵
deque <int> q;↵
int t,ans;↵
int main()↵
{↵
scanf("%d",&n);↵
for (int i=1;i<=n;i++)↵
scanf("%d",&a[i]);↵
f[1]=1;↵
q.push_back(1);↵
for (int i=2;i<=n;i++)↵
{↵
while (!q.empty())↵
{↵
t=q.front();↵
if (a[t]*2<a[i]) q.pop_front();↵
else break;↵
}↵
if (q.empty()) t=0;↵
f[i]=f[t]+1;↵
while (!q.empty())↵
{↵
t=q.back();↵
if (f[t]<f[i]) q.pop_back();↵
else break;↵
}↵
q.push_back(i);↵
}↵
for (int i=1;i<=n;i++)↵
ans=max(ans,f[i]);↵
printf("%d",ans);↵
return 0;↵
}↵
~~~~~↵
↵
Thank you for reading my first entry. See you next time!↵
↵
postscripts:↵
↵
1. It is the first time of mine to write the solution (entry). So if there is any mistake, please specify ([user:PQF,2018-08-27]). Thanks.↵
1. Actually, I'm a Chinese. So please forgive my English level. Thanks.↵
1. Oh, writing an entry is so tiring!
↵
Problem:[problem:1029B]↵
↵
Simple Meaning of Problem:↵
↵
There is a sequence $a$ and you should choose the longest sequence $b$ ${a_{i_1}, a_i_2, \dots, a_{i_p}}$ ($p$ is the length of $b$) such that:each $j∈[1,k)$ $a_{i_{j+1}} \le a_{i_j} \cdot 2$ should hold.↵
↵
print the maximum number of $p$ (the length of $b$)↵
↵
↵
First, you can enumerate which ones to choose. You will get a algorithm with $O(2^n)$. And you will get a Time Limit Exceed.(I didn't write it, because it is valueless.)↵
↵
Then, dp is another useful algorithm. So we can try to use dp.↵
↵
$f[i]$ means that if you choose the number $a_i$, you can get the maximum $p$ (only of $1$ to $i$).↵
↵
It is very easy to get the state transition equation:↵
↵
$f[i]=max{f[j]}+1$, $j$ satisfy that $a_i \le a_j \cdot 2$ and $j \le i$.↵
↵
And the answer is $max{f[i]}$ ($i$ is $1$ to $n$).↵
↵
code:[submission:42093398]↵
↵
~~~~~↵
#pragma comment (linker,"/STACK:1024000000") ↵
#pragma GCC optimize(2)↵
#pragma GCC target(arch=corie7-acx)↵
#include<bits/stdc++.h>↵
using namespace std;↵
int n,a[200001],f[200001];↵
deque <int> q;↵
int t,ans;↵
int main()↵
{↵
scanf("%d",&n);↵
for (int i=1;i<=n;i++)↵
scanf("%d",&a[i]);↵
f[1]=1;↵
for (int i=2;i<=n;i++)↵
{↵
for (int j=1;j<=i-1;j++)↵
if (a[j]*2>=a[i]) f[i]=max(f[i],f[j]);↵
f[i]++;↵
}↵
for (int i=1;i<=n;i++)↵
ans=max(ans,f[i]);↵
printf("%d",ans);↵
return 0;↵
}↵
~~~~~↵
↵
And this code does better:[submission:42095786](In fact, it also Time Limit Exceed on Test 4)↵
↵
~~~~~↵
#pragma comment (linker,"/STACK:1024000000") ↵
#pragma GCC optimize(2)↵
#pragma GCC target(arch=corie7-acx)↵
#include<bits/stdc++.h>↵
using namespace std;↵
int n,a[200001],f[200001];↵
deque <int> q;↵
int t,ans;↵
int main()↵
{↵
scanf("%d",&n);↵
for (int i=1;i<=n;i++)↵
scanf("%d",&a[i]);↵
f[1]=1;↵
for (int i=2;i<=n;i++)↵
{↵
for (int j=i-1;j>=1;j--)↵
if (a[j]*2>=a[i]) f[i]=max(f[i],f[j]);↵
else break;↵
f[i]++;↵
}↵
for (int i=1;i<=n;i++)↵
ans=max(ans,f[i]);↵
printf("%d",ans);↵
return 0;↵
}↵
~~~~~↵
↵
But, unfortunately, these two are both Time Limit Exceed. (Actually, it is inevitable.)↵
↵
Because when $a_n \le a_1 \cdot 2$, the time complexity of the code will come to $O(n^2)$ (`break` is useless).↵
↵
So it is inevitable that the code will TLE.↵
↵
Now, how can we optimize our algorithm?↵
↵
In the problem, notice that the numbers are increasing.↵
↵
So when $i$ is increasing, $a_i$ is increasing, too. And $\frac {a_i} {2}$ is increasing, so the number which is less than $\frac {a_i} {2}$ is also increasing.↵
↵
Because of this, for the increasing number $i$, the $j$ which is satisfy $a_i \le a_j \cdot 2$ is increasing as well.↵
↵
↵
When we want to calculate $f[i]$, we check the numbers of queue from the front to the back. For each $x$, if $a_x \cdot 2 < a_i$, we can pop $x$. (Because for the after $j$, $a_j \ge a_i > a_x \cdot 2$).↵
↵
We can find the first $x$ which is satisfy $a_x \cdot 2 \ge a_i$. Then we use $f[x]$ to calculate $f[i]$. (It will be proven after).↵
↵
Finally, we get the back of $q$ $y$. If $f[y] \le f[i]$, we can pop $y$. That's because $y$ must be popped earlier than $i$, and $f[i]$ is greater than $f[y]$. So the following number choose $f[i]$ is greater than $f[y]$.↵
↵
And that's why the first number of the queue $x$ is the best choice to transfer $f[i]$ after popping. (In fact, it is a priority queue.)↵
↵
When we code it, we can use double-end-queue (deque).↵
↵
code:[submission:42036114]↵
↵
~~~~~↵
#pragma comment (linker,"/STACK:1024000000") ↵
#pragma GCC optimize(2)↵
#pragma GCC target(arch=corie7-acx)↵
#include<bits/stdc++.h>↵
using namespace std;↵
int n,a[200001],f[200001];↵
deque <int> q;↵
int t,ans;↵
int main()↵
{↵
scanf("%d",&n);↵
for (int i=1;i<=n;i++)↵
scanf("%d",&a[i]);↵
f[1]=1;↵
q.push_back(1);↵
for (int i=2;i<=n;i++)↵
{↵
while (!q.empty())↵
{↵
t=q.front();↵
if (a[t]*2<a[i]) q.pop_front();↵
else break;↵
}↵
if (q.empty()) t=0;↵
f[i]=f[t]+1;↵
while (!q.empty())↵
{↵
t=q.back();↵
if (f[t]<f[i]) q.pop_back();↵
else break;↵
}↵
q.push_back(i);↵
}↵
for (int i=1;i<=n;i++)↵
ans=max(ans,f[i]);↵
printf("%d",ans);↵
return 0;↵
}↵
~~~~~↵
↵
Thank you for reading my first entry. See you next time!↵
↵
postscripts:↵
↵
1. It is the first time of mine to write the solution (entry). So if there is any mistake, please specify ([user:PQF,2018-08-27]). Thanks.↵
1. Actually, I'm a Chinese. So please forgive my English level. Thanks.↵
1. Oh, writing an entry is so tiring!
