What is the necessary and sufficient condition?
The necessary and sufficient condition for a beautiful sequence is that there exist one $$$i$$$, such that $$$a_{i} \le i$$$. Just check the sequence for the condition.
#include<bits/stdc++.h>
using namespace std;
int a[100005];
void solve()
{
int n;
scanf("%d",&n);
for(int i =1;i <= n;i++) scanf("%d",&a[i]);
for(int i = 1;i <= n;i++) {
if(a[i] <= i) {
puts("YES");
return;
}
}
puts("NO");
}
int main()
{
int t;scanf("%d",&t);
while(t--) solve();
}
How the binary representation changes after an operation?
First, we notice that after each operation, the number of candies is always a odd number. So even numbers can not be achieved.
Then consider how the binary representation changes for a odd number $$$x$$$, after turn it into $$$2x+1$$$ or $$$2x-1$$$.
For the $$$2x + 1$$$ operation: $$$\overline{\dots 1}$$$ turns into $$$\overline{\dots 11}$$$.
For the $$$2x - 1$$$ operation: $$$\overline{\dots 1}$$$ turns into $$$\overline{\dots 01}$$$.
So, the operation is just insert a $$$0/1$$$ before the last digit. And the answer for an odd $$$n$$$ is just the binary representation of $$$n$$$, after removing the last digit.
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n;scanf("%d",&n);
if(n % 2 == 0) {
puts("-1");return;
}
vector<int> v;
int f = 0;
for(int i = 29;i >= 1;i--) {
if((n >> i) & 1) {
f = 1;
v.push_back(2);
}
else if(f) {
v.push_back(1);
}
}
printf("%d\n",v.size());
for(auto x : v) {
printf("%d ",x);
}
printf("\n");
}
int main()
{
int t;scanf("%d",&t);
while(t--) solve();
return 0;
}
Try the enumerate the length $$$n$$$ of permutation.
There're too many lengths to be checked. How to decrease the amount of $$$n$$$?
Firstly, we need to remove numbers such that each number appears at most once, this part of cost is unavoidable. Then, let's sort the array $$$a_{1},a_{2} \dots a_{m}$$$ ($$$1\le a_{i} < a_{2} < \dots < a_{m}$$$).
Secondly, assume we enumerate the length of the permutation $$$n$$$. We need to remove all the $$$a_{i}$$$ greater than $$$n$$$, and insert some numbers $$$x$$$ ($$$x \le n$$$) but does not appear in the array $$$a$$$. We can find some $$$i$$$ such that $$$a_{i} \le n < a_{i+1}$$$, the cost here is simply $$$(m-i)\cdot a + (n - i)\cdot b$$$. Here, $$$m$$$ is the length of array $$$a$$$, after removing the repeated numbers.
However, $$$n$$$ can up to $$$10^9$$$ and can not be enumerated. But for all the $$$n \in [a_{i} , a_{i+1})$$$, the smaller $$$n$$$ has a smaller cost. (see that $$$(m-i)\cdot a$$$ do not change, and $$$(n-i)\cdot b$$$ decreases). Thus, the possible $$$n$$$ can only be some $$$a_{i}$$$, and we can caculate the cost in $$$O(n)$$$ in total.
Don't forget the special case: remove all the numbers and add a $$$1$$$.
#include<bits/stdc++.h>
using namespace std;
int p[100005];
typedef long long ll;
void solve()
{
int n,a,b;scanf("%d%d%d",&n,&a,&b);
set<int> st;
ll sol = 0 , ans = 2e18;
for(int i = 1;i <= n;i++) {
int x;scanf("%d",&x);
if(st.find(x) == st.end()) st.insert(x);
else sol += a;
}
int c = 0;
for(auto x : st) p[++c] = x;
for(int i = 1;i <= c;i++) {
ans = min(ans , 1LL*(p[i] - i)*b + 1LL*(c-i)*a);
}
ans = min(ans , 1LL*c*a + b) ;
printf("%lld\n",ans+sol);
}
int main()
{
int t;scanf("%d",&t);
while(t--) solve();
}
The possible $$$L$$$ is always an interval. How to maintain it?
The main idea is to that for each $$$a,b,n$$$, the possible $$$L$$$ is a interval $$$[l,r]$$$. We will show how to calculate that.
In the first $$$n-1$$$ days, the snail will climb $$$(n-1)\cdot (a-b)$$$ meters. And in the daytime of the $$$n$$$-th day, the snail will climb $$$a$$$ meters. So after $$$n$$$ days, the snail climbs at most $$$(n-1)\cdot (a-b) + a$$$ meters, which means $$$L \le (n-1)\cdot (a-b) + a$$$. Also, the snail can not reach $$$L$$$ before $$$n$$$ days, which means $$$L > (n-2)\cdot (a-b) + a$$$. So $$$L \in [(n-2)\cdot (a-b) + a + 1 , (n-1)\cdot (a-b) + a]$$$. $$$n=1$$$ is a special case, where $$$L \in [1,a]$$$ .
Now after each operation $$$1$$$, we can maintain a possible interval $$$[L_{min} , L_{max}]$$$. When a snail comes, we let the new $$$[L_{min}',L_{max}']$$$ be $$$[L_{min},L_{max}] \cap [l,r]$$$, where $$$[l,r]$$$ is the possible interval for the new snail. If the new interval is empty, we ignore this information, otherwise adopt it.
Now let's focus on another problem: for a fixed $$$L,a,b$$$, how to calculate the number of days the snail needs to climb? We can solve the equation $$$(n-2)(a-b) + a < L \le (n-1)(a-b) + a$$$, and get $$$n - 2 < \frac{L - a}{a - b} \le n - 1$$$, which means $$$n$$$ equals to $$$\lceil \frac{L-a}{a-b} \rceil + 1$$$. Still, special judge for $$$L \le a$$$, where $$$n=1$$$ in this case.
Then, for each query of type $$$2$$$, we just calculate the number of days we need for $$$L_{min}$$$ and $$$L_{max}$$$. If they are the same, output that number. Otherwise output $$$-1$$$.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve()
{
int q;scanf("%d",&q);
ll L = 1 , R = 1e18;
while(q--) {
int op;scanf("%d",&op) ;
if(op == 1) {
int a,b,n;scanf("%d%d%d",&a,&b,&n);
ll ql = 1LL*(n - 2)*(a - b) + a + 1, qr = 1LL*(n - 1)*(a - b) + a;
if(n == 1) ql = 1 , qr = a;
if(ql > R || qr < L) {
puts("0");
}
else L = max(L , ql) , R = min(R , qr) , puts("1");
}
else {
int a,b;scanf("%d%d",&a,&b);
ll ans1 = max(1LL,(L - b - 1) / (a - b) + 1) , ans2 = max(1LL,(R - b - 1) / (a - b) + 1);
if(ans1 == ans2) printf("%lld\n",ans1);
else puts("-1");
}
}
return;
}
int main()
{
int t;scanf("%d",&t);
while(t--) solve();
}
How to check whether it is possible to defeat all the monsters, starting from a fixed vertex $$$u$$$?
Let $$$S(u)$$$ be the vertices set that can be reached, starting from vertex $$$u$$$. What's the relationship between $$$S(u)$$$ and $$$S(v)$$$, where $$$v\in S(u)$$$?
For some vertex set $$$T$$$, let's define $$$E(T)$$$ as the ''neighbours'' of vertex set $$$T$$$. Formally, $$$v \in E(T)$$$ if and only if $$$v \notin T$$$, but there exist some vertex $$$u$$$, such that there's an edge $$$(u,v)$$$ in the graph, and $$$u \in T$$$.
Now let's consider how to solve the problem for some fixed starting vertex $$$u$$$? Let's maintain the set $$$S(u)$$$ and $$$E(S(u))$$$. Initially, $$$S(u) = {u }$$$. We keep doing the procedure: choose a vertex $$$v \in E(S(u))$$$ with minimal value $$$a_{v}$$$. If $$$a_{v} \le |S(u)|$$$, we add $$$v$$$ into set $$$S(u)$$$, and update set $$$E(S(u))$$$ simultaneously. Since $$$S(u)$$$ is always connected during the procedure, we are actually doing such a thing: find a vertex $$$v$$$ that is ''reachable'' now with minimal value $$$a_{v}$$$, and try to defeat the monster on it. Our goal is to find some $$$u$$$ such that $$$|S(u)| = n$$$.
Then let's move to a lemma: if $$$v \in S(u)$$$, then $$$S(v) \subseteq S(u)$$$.
If it is not, consider the procedure above and the first time we add some vertex $$$x$$$ such that $$$x \notin S(u)$$$ into $$$S(v)$$$. At this moment, $$$|S(v)| \le |S(u)|$$$ must hold(since it's the first time we add some vertex not in $$$S(u)$$$). On the other side, $$$x \in E(S(u))$$$ must hold, and hence $$$a_{x} > |S(u)| \ge |S(v)|$$$. Thus, we can not add $$$x$$$ into $$$S(v)$$$.
Then we can tell, if $$$|S(u)| < n$$$, then for $$$v \in S(u)$$$, $$$|S(v)| < n$$$. So it's unnecessary to search starting from $$$v$$$. And we can construct such an algorithm: Search from $$$1,2,3,\dots n$$$ in order, if some $$$i$$$ has been included in some $$$S(j)$$$ before, do not search from it.
Surprisingly, this algorithm is correct. We can prove it's time complexity. For each vertex $$$v$$$, if $$$v \in S(u)$$$ now, and when searching from vertex $$$u'$$$, $$$v$$$ is add into $$$S(u')$$$ again, then $$$|S(u')| > 2|S(u)|$$$. Thus, one vertex can not be visited more than $$$log(n)$$$ times, which means the time complexity is $$$O(nlog^2(n))$$$.
This problem has many other methods to solve. This one I think is the easiest to implement.
#include<bits/stdc++.h>
using namespace std;
int vis[200005];
int n , m;
vector<int> E[200005];
int a[200005];
int T = 1;
bool span(int u)
{
set<pair<int,int> > st;
st.insert(pair<int,int>{a[u] , u});
int amt = 0 , df = 0;
while(st.size()) {
auto pa = (*st.begin()) ; vis[pa.second] = u;
if(pa.first > df) {return (amt == n);}
st.erase(st.begin());
amt++ ; df++ ;
for(auto v : E[pa.second]) {
if(vis[v] < u) {
st.insert(pair<int,int>{a[v] , v});
}
}
}
return (amt == n);
}
void solve()
{
scanf("%d%d",&n,&m);
for(int i= 1;i <= n;i++) scanf("%d",&a[i]) , vis[i] = 0, E[i].clear();
for(int i = 1;i <= m;i++) {
int u,v;scanf("%d%d",&u,&v);E[u].push_back(v) ; E[v].push_back(u);
}
for(int i = 1;i <= n;i++) {
if(a[i] == 0 && !vis[i]) {
if(span(i)){puts("YES");return;}
}
}
puts("NO");
}
int main()
{
int t;scanf("%d",&t);
while(t--) solve();
}
Can you solve a single query using binary search? How to check the answer?
Try to find a closed formula for this problem.
Let $$$num_{i}$$$ be the number of occurances of integer $$$i$$$ in the array $$$a$$$. To check whether the answer can be $$$\le x$$$ or not, we can do the following greedy: Starting with a single vertex written $$$x$$$, which is the root. For each $$$i$$$(from large ones to small ones), if the number of current leaves is smaller than $$$num_{i}$$$, then we can not make the answer $$$\le x$$$. Otherwise, let $$$num_{i}$$$ leaves stop, and other leaves ''grow'' $$$m$$$ children each(these vertices are no longer leaves, but their children are). We can discover that each round, the ''stopped'' vertices have $$$dep = x - i$$$, which represents their value is $$$x$$$.
We can use the following code to calculate it.
bool check(int x)
{
int d = 1;
for(int i = x;i >= 1;i--){
if(d < num[i]) return 0;
d = (d - num[i]) * m;
}
return 1;
}
Since a negtive number multiplies $$$m$$$ is still a negtive number, the code can be as following:
bool check(int x)
{
int d = 1;
for(int i = x;i >= 1;i--){
d = (d - num[i]) * m;
}
return d >= 0;
}
Find out something? The final $$$d$$$ is just $$$m^x - \sum_{i=1}^{x}{num_{i} \cdot m^i}$$$, which represents it's equivalent to checking $$$m^x \ge \sum_{i=1}^{n}{m^{a_{i}}}$$$! So now the answer is just $$$\lceil log_{m}{\sum_{i=1}^{n}{m^{a_{i}}}} \rceil$$$. This is the highest bit plus one of $$$\sum{m^{a_{i}}}$$$ in $$$m$$$-base representation(except for that it's just some $$$m^x$$$. In this case the answer is $$$x$$$ but not $$$x+1$$$). We can use a segment tree, supporting interval min/max query and interval covering to solve the question.
using namespace std;
int n , m , q;
const int N = 2e5 + 40;
int num[N];
int a[N];
int cov[N*4 + 5] , mx[N*4 + 5] , mn[N*4 + 5];
void rec(int u)
{
mx[u] = max(mx[u<<1|1] , mx[u<<1]) ; mn[u] = min(mn[u<<1|1] , mn[u<<1]);
}
void pd(int u)
{
if(cov[u] != -1) {
cov[u<<1] = mn[u<<1] = mx[u<<1] = cov[u];
cov[u<<1|1] = mn[u<<1|1] = mx[u<<1|1] = cov[u];
cov[u] = -1;
}
return;
}
void build(int u,int l,int r)
{
cov[u] = -1;
if(l == r) {mn[u] = mx[u] = num[l] ; return;}
build(u<<1 , l , (l + r >> 1)) ; build(u<<1|1 , (l + r >> 1) + 1 , r);
rec(u) ; return;
}
void modify(int u,int l,int r,int ql,int qr,int v)
{
if(ql <= l && qr >= r) {
cov[u] = mn[u] = mx[u] = v; return;
}
pd(u);
int md = (l + r>> 1);
if(ql <= md) modify(u<<1 , l , md , ql , qr ,v);
if(qr > md) modify(u<<1|1 , md +1 , r , ql , qr , v);
rec(u);
return;
}
int qumax(int u,int l,int r,int ql)
{
if(mn[u] == m - 1) return -1;
if(l == r) return l;
pd(u);
int md = (l + r>> 1);
if(ql > md) return qumax(u<<1|1 , md + 1 , r , ql);
if(ql == l) {
if(mn[u<<1] < m - 1) return qumax(u<<1 , l , md , ql);
return qumax(u<<1|1 , md + 1 , r , md + 1);
}
int w = qumax(u<<1 , l , md , ql) ;
if(w == -1) return qumax(u<<1|1 , md + 1 , r , md + 1);
return w;
}
int qumin(int u,int l,int r,int ql)
{
if(mx[u] == 0) return -1;
if(l == r) return l;
pd(u);
int md = (l + r>> 1) ;
if(ql > md) return qumin(u<<1|1 , md + 1 , r , ql);
if(ql == l) {
if(mx[u<<1] > 0) return qumin(u<<1 , l , md , ql);
return qumin(u<<1|1 , md + 1 , r , md + 1);
}
int w = qumin(u<<1 , l , md , ql);
if(w == -1) return qumin(u<<1|1 , md + 1 , r , md + 1);
return w;
}
int qmax(int u,int l,int r,int ql,int qr)
{
if(ql <= l && qr >= r) {
return mx[u];
}
pd(u);
int md = (l + r>> 1) , ans = 0;
if(ql <= md) ans = max(ans , qmax(u<<1 , l , md , ql , qr ));
if(qr > md) ans = max(ans , qmax(u<<1|1 , md +1 , r , ql , qr));
return ans;
}
int qmin(int u,int l,int r,int ql,int qr)
{
if(ql <= l && qr >= r) {
return mn[u];
}
pd(u);
int md = (l + r>> 1) , ans = 1e9;
if(ql <= md) ans = min(ans , qmin(u<<1 , l , md , ql , qr ));
if(qr > md) ans = min(ans , qmin(u<<1|1 , md +1 , r , ql , qr));
return ans;
}
int ask(int u,int l,int r)
{
if(l == r) return l;
int md = (l + r >> 1);
pd(u);
if(mx[u<<1|1] == 0) return ask(u<<1 , l , md);
return ask(u<<1|1 , md + 1 , r) ;
}
int get()
{
int highbit = ask(1 , 1 , n+35);
if(highbit == 1 || qmax(1 , 1 , n+35 , 1 , highbit - 1) == 0) return highbit;
return highbit + 1;
}
void add(int u)
{
int l = qumax(1 , 1 , n + 35 , u);
if(l > u) modify(1 , 1 , n+35 , u , l - 1 , 0) ;
modify(1 , 1 , n+35 , l , l , qmax(1 , 1 , n + 35 , l , l ) + 1);
return;
}
void sub(int u)
{
int l = qumin(1 , 1 , n + 35 , u);
if(l > u) modify(1 , 1 , n+35 , u , l - 1 , m - 1) ;
modify(1 , 1 , n+35 , l , l , qmax(1 , 1 , n + 35 , l , l ) - 1);
return;
}
void solve()
{
scanf("%d%d%d",&n,&m,&q);
for(int i = 1;i <= n + 35;i++) num[i] = 0;
for(int i = 1;i <= n;i++) {
scanf("%d",&a[i]);num[a[i]]++;
}
for(int i = 1;i <= n + 35;i++) {
num[i + 1] += num[i] / m;num[i] %= m;
}
build(1 , 1 , n + 35);
while(q--) {
int u , v;scanf("%d%d",&u,&v);
sub(a[u]) ; a[u] = v; add(a[u]) ;
printf("%d%c",get(), " \n"[q == 0]);
}
return;
}
int main()
{
int t;scanf("%d",&t);
while(t--) solve();
}
How to calculate the maximal prefix sum? One possible way is let $$$f_{n+1} = 0$$$ and $$$f_{i}=max(f_{i+1},0)+a_{i}$$$.
Consider this method to find maximal prefix sum: let $$$f_{n+1} = 0$$$ and $$$f_{i}=max(f_{i+1},0)+a_{i}$$$. We can discover that the only influence $$$[a_{i+1},a_{i+2} \dots a_{n}]$$$ has(to the whole array's maximal prefix sum) is its maximal prefix sum. Then we let $$$dp_{i,j}$$$ be : the expect score we can get, if we assume that the maximal prefix sum of $$$[a_{i+1},a_{i+2} \dots a_{n}]$$$ is $$$j$$$ (Read the definition carefully). The answer for each $$$k$$$ is $$$dp_{k,0}$$$, since if the maximal prefix sum for $$$[a_{k+1},a_{k+2} \dots a_{n}]$$$ is $$$0$$$, that is equivalent to removing them from the array. And also $$$dp_{0,j} = h_{j}$$$.
And we have $$$dp_{i,j} = p_{i}\cdot dp_{i-1,j+1} + (1 - p_{i})\cdot dp_{i-1,max(j-1,0)}$$$. The first section represents chosing $$$a_{i} = 1$$$ and the second one represents chosing $$$a_{i} = -1$$$.
We also have other solutions, using inclusion-exclusion or generate function. Actually all the testers' solutions differs from each other.
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int N = 5005;
int p[N] , q[N];
int n;
int f[N][N];
int h[N];
int fpow(int a,int b)
{
int ans = 1;
while(b){
if(b & 1) ans = 1LL*ans*a%mod;
a = 1LL*a*a%mod;b >>= 1;
}
return ans;
}
void solve()
{
scanf("%d",&n);
for(int i = 1;i <= n;i++) {
int a,b;scanf("%d%d",&a,&b);
p[i] = 1LL*a*fpow(b , mod - 2) % mod;
q[i] = (1 - p[i] + mod) % mod;
}
for(int i = 0;i <= n;i++) scanf("%d",&h[i]);
for(int i = 0;i <= n;i++) f[0][i] = h[i];
for(int i = 1;i <= n;i++) {
for(int j = 0;j <= n;j++) {
f[i][j] = (1LL*p[i]*f[i - 1][j + 1] + 1LL*q[i]*f[i - 1][max(0 , j - 1)] ) % mod;
}
printf("%d ",f[i][0]);
}
printf("\n");
return;
}
int main()
{
int t;scanf("%d",&t);
while(t--) solve();
return 0;
}
Actually I don't know how to hint. Try to find some rules related to $$$\frac{\sqrt{5}+1}{2}$$$, fibnacci or similar
Assume that the moment before the $$$x$$$-th operation(but after $$$x-1$$$-th), the first time we have $$$S_{max} \le 2S_{min}$$$. Let's divide the operation into two part: before $$$x$$$ and equal or after $$$x$$$.
Still, at the moment just before the $$$x$$$-th operation, let us sort the elements in the multiset in non-decreasing order, $$$S_{0},S_{1} \dots S_{k}$$$. We will show that the answer is $$$S_{0}\cdot (-1)^{k} + \sum_{i=1}^{k}{S_{i}\cdot (-1)^{i+1}}$$$.
This lemma is based on the fact that, after each operation(which is after $$$x$$$-th), $$$S_{1}$$$ to $$$S_{k-1}$$$ will not change, $$$S_{k}$$$ is removed, and $$$S_{0}$$$ turn to $$$S_{k}-S_{0}$$$. Which also means $$$S_{k} - S_{0} \le S_{1}$$$ always holds.
At the very beginning, $$$S_{k} - S_{0} \le S_{0} \le S_{1}$$$ obviously holds. And we can observe that either $$$S_{k} = S_{k-1}$$$ or $$$S_{k-1} = S_{k} - 1$$$. When $$$S_{k-1} = S_{k}$$$, the new $$$S_{0}$$$ after two operations is equal to the old $$$S_{0}$$$. When $$$S_{k-1} = S_{k} - 1$$$, the new $$$S_{0}$$$ after two operations is equal to the old $$$S_{0}$$$ minus one. So if we write the $$$S_{0}$$$ as an array $$$t_{0} , t_{1} \ldots t_{k}$$$ by time order, $$$t_{i+2} \le t_{i}$$$ always holds. Thus, $$$t_{i} \le S_{1}$$$ always holds.
Let $$$d_{i}$$$ be the $$$S_{max}$$$ value in the $$$i$$$-th operation. Let's prove that before the $$$x$$$-th operation, $$$d_{i} = n-\lceil \frac{i}{\phi} \rceil + 1$$$, where $$$\phi = \frac{\sqrt{5} + 1}{2}$$$.
We prove this by Mathematical induction. One fact should be known that during these operations, $$$S_{min} = i$$$ always holds for the $$$i$$$-th operation(since $$$S_{max} - S_{min} > S_{min}$$$).
For $$$i=1$$$, it is true because $$$d_{1} = n$$$ and $$$n - \lceil \frac{1}{\phi} \rceil + 1 = n$$$.
Assume for $$$i\le k$$$, it is true. Still use the fact that $$$d_{k+1} = d_{k}$$$ or $$$d_{k+1} = d_{k} + 1$$$. The necessary and sufficient condition for $$$d_{k+1} > d_{k}$$$ is all the numbers greater or equal to $$$d_{k}$$$ is ''used''. How many numbers are there? We have $$$n - d_{k} + 1$$$ numbers from the original multiset, and some numbers that occurs during the operations, which are the number of $$$j$$$ satisfying $$$d_{j} - j \ge d_{k}$$$. Thus, $$$d_{k+1} > d_{k}$$$ is equivalent to:
$$$ \space \space \space \space \sum_{j=1}^{k}{[d_{j} - j \ge d_{k}]} + n - d_{k} + 1 = k$$$
$$$ \Leftrightarrow \sum_{j=1}^{k}{[d_{j} - j \ge d_{k}]} = k - \lceil \frac{k}{\phi} \rceil$$$
$$$\Leftrightarrow \sum_{j=1}^{k}{[d_{j} - j \ge d_{k}]} = \lfloor \frac{k(\phi - 1)}{\phi} \rfloor$$$
$$$\Leftrightarrow \sum_{j=1}^{k}{[\lceil \frac{j}{\phi} + j \rceil \le \lceil \frac{k}{\phi} \rceil]} = \lfloor \frac{k(\phi - 1)}{\phi} \rfloor$$$
$$$\Leftrightarrow \sum_{j=1}^{k}{[\lceil \frac{j(\phi + 1)}{\phi} \rceil \le \lceil \frac{k}{\phi} \rceil]} = \lfloor \frac{k(\phi - 1)}{\phi} \rfloor$$$
Note that $$$\frac{j(\phi + 1)}{\phi}$$$ is always increasing, which means that formula $$$\lceil \frac{j(\phi + 1)}{\phi} \rceil \le \lceil \frac{k}{\phi} \rceil$$$ holds for $$$j = \lfloor \frac{k(\phi - 1)}{\phi} \rfloor$$$, but does not hold for $$$j = \lfloor \frac{k(\phi - 1)}{\phi} \rfloor + 1$$$.
The first equation, $$$\lceil \lfloor \frac{k(\phi - 1)}{\phi} \rfloor \cdot \frac{\phi + 1}{\phi} \rceil \le \lceil \frac{k}{\phi} \rceil$$$ always holds. Because $$$\frac{\phi - 1}{\phi}\cdot \frac{\phi + 1}{\phi} = \frac{1}{\phi}$$$, and ofcourse $$$\lfloor ka \rfloor b \le kab$$$.
Let's do the research when the second equation does not hold. Let $$$m_{1} = \lbrace \frac{i(\phi - 1)}{\phi} \rbrace$$$, and $$$m_{2} = \lbrace \frac{i}{\phi} \rbrace $$$ ($$$\lbrace x \rbrace = x - \lfloor x \rfloor$$$). Note that $$$m_{1} + m_{2} = 1$$$, since $$$\lbrace \frac{i(\phi - 1)}{\phi} \rbrace = \lbrace i - \frac{i}{\phi} \rbrace$$$. The topic we are going to research is when $$$\lceil (\lfloor \frac{k(\phi - 1)}{\phi} \rfloor + 1) \cdot \frac{\phi + 1}{\phi}\rceil > \lceil \frac{k}{\phi} \rceil$$$ hold(which also means, $$$d_{k+1} > d_{k}$$$).
$$$\Leftrightarrow \lceil (\frac{i(\phi - 1)}{\phi} - m_{1}) \cdot \frac{\phi+1}{\phi} + \frac{\phi + 1}{\phi} \rceil > \lceil \frac{i}{\phi} \rceil$$$
$$$\Leftrightarrow \lceil \frac{i}{\phi} - m_{1} \cdot \frac{\phi+1}{\phi} + \frac{\phi + 1}{\phi} \rceil > \lceil \frac{i}{\phi} \rceil$$$
$$$\Leftrightarrow \lceil \frac{i}{\phi} - (1 - m_{1}) \cdot \frac{\phi+1}{\phi} \rceil > \lceil \frac{i}{\phi} \rceil$$$
$$$\Leftrightarrow (1 - m_{1}) \cdot \frac{\phi+1}{\phi} > 1 - m_{2}$$$
$$$\Leftrightarrow \frac{\phi+1}{\phi} > \frac{1}{m_{2}} - 1$$$
$$$\Leftrightarrow m_{2} > \frac{\phi}{2\phi + 1}$$$
Then let's focus on, if $$$d_{k+1} = n - \lceil \frac{k+1}{\phi} \rceil + 1$$$, when will $$$d_{k + 1} > d_{k}$$$ hold? It's easy to find when $$$m_{2} > 1 - \frac{1}{\phi}$$$, $$$d_{k+1} > d_{k}$$$ holds. And since $$$\phi = \frac{\sqrt{5} + 1}{2}$$$, we can tell $$$ \frac{\phi}{2\phi + 1} = 1 - \frac{1}{\phi}$$$. Thus, we proved the topic, for all $$$k < x$$$(before the $$$x$$$-th operation), $$$d_{k} = n - \lceil \frac{k}{\phi} \rceil + 1$$$.
Then, by solve $$$n - \lceil \frac{x}{\phi} \rceil + 1 \le 2x$$$, we can get $$$x = \lceil (n+1)\frac{\phi - 1}{\phi} \rceil$$$. Now let's prove for $$$k \ge x$$$, $$$d_{k} = n - \lceil \frac{k}{\phi} \rceil + 1$$$ also holds !
Using the similar idea as lemma 2, find out when $$$d_{k + 1} > d_{k}$$$ holds. However, at this time, only $$$j \le x - 1$$$ will contribute(since for those $$$j > x - 1$$$, according to lemma 1, they become the minimal one and do not contribute to anything). Similarly, that is $$$\sum_{j=1}^{x - 1}{[d_{j} - j \ge d_{k}]} = \lfloor \frac{k(\phi - 1)}{\phi} \rfloor$$$.
Seems to be different this time, but actually they are the same, because $$$\lfloor \frac{k(\phi - 1)}{\phi} \rfloor \le x - 1$$$ holds(the proving is easy, leave it as a exercise). This condition holds means that we can use the same method in lemma 2 to prove it.
Till now, the lemmas told us the solving the problem is actually solving something like $$$\sum{(-1)^{i} \cdot (n- \lceil \frac{i}{\phi} \rceil + 1)}$$$. We can divide them into positive part and negtive part, and then solving $$$\sum{\lfloor C\cdot i \rfloor}$$$, where $$$i$$$ range from some $$$l$$$ to $$$r$$$, and $$$C$$$ is a irrational constant. Since $$$n$$$ is not very large, we can approximate $$$C$$$ by $$$\frac{a}{b}$$$, where $$$a,b$$$ are integers, and turn it into a traditional task. (Maybe it is called floor sum or something like, I'm not sure about the algorithm's english name).
The marvelous jiangly told me $$$a,b$$$ in long long range is enough. But the tester used int128.
We can dig more about the $$$\phi$$$. Let $$$b_{i} = S_{i+1} - S_{i}$$$ (sorted, before the $$$x$$$-th operation), and what we care is $$$b_{1} + b_{3} + b_{5}\dots$$$. We can find that array $$$b$$$ is actually a consecutive substring of fibonacci string. More over, let $$$F_{n}$$$ be the starting point of array $$$b$$$ in the fibonacci string when the initial size is $$$n$$$, we have the conclusion for $$$n \ge 5$$$:
$$$F[5 \dots inf] = [3,0],[4,1],[8,0],[12,1] \dots [f_{i+3} + (-1)^{i+1} , 1 + (-1)^{i}]$$$, where $$$f_{i} = f_{i-1} + f_{i-2} , f_{1} = f_{2} = 1$$$ . $$$[r,l]$$$ represents a list of numbers $$$[r,r-1,r-2 \dots l+1,l]$$$.
Now the only left problem is to find the prefix sum of fibonacci string(of even positions, or of odd positions). This is quite a simple task by using any $$$log(n)$$$ or $$$log^2(n)$$$ solution.
#include <bits/stdc++.h>
void solve(__int128 n, __int128 a, __int128 b, __int128 c, __int128 &f) {
if (n < 0) { f = 0; return; }
if (a >= c || b >= c) {
solve(n, a % c, b % c, c, f);
f += (a / c) * (n * (n + 1) / 2) + (b / c) * (n + 1);
} else if (a) {
__int128 m = (a * n + b) / c;
solve(m - 1, c, c - b - 1, a, f);
f = n * m - f;
}
}
const long double k = (1 + sqrt((long double) 5)) / 2;
int n;
long long ans;
__int128 a, b, c, d;
int main() {
int T;
scanf("%d", &T);
__int128 x = (__int128) 2000000000000000000ll * 1000000000;
__int128 y = (__int128) 1000000000000000000ll * 1000000000;
__int128 z = (__int128) 1618033988749894848ll * 1000000000 + 204586834;
for (; T; T--) {
scanf("%d", &n);
int i = 0;
for (int l = 0, r = n - 1, mid; l <= r; ) {
mid = l + r >> 1;
if (n - floor(mid / k) <= mid + mid) {
i = mid; r = mid - 1;
} else {
l = mid + 1;
}
}
solve((n - 1) / 2, x, 0, z, a);
solve((i - 1) / 2, x, 0, z, b);
solve((n - 2) / 2, x, y, z, c);
solve((i - 2) / 2, x, y, z, d);
ans = i + (i % 2 ? -1 : 1) * ((a - b) - (c - d));
if ((n - i) % 2) { ans = n - ans; }
printf("%lld\n", ans);
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int l[500];
int fib[500];
int evenfib[500];
int getsum(int i,int n) ///1-index
{
if(n == 0) return 0;
if(i <= 1) return fib[i];
if(n <= l[i - 2]) return getsum(i - 2, n);
return fib[i - 2] + getsum(i - 1 , n - l[i - 2]);
}
int getsum2(int i,int n,int p) ///n = 2*k+p, 0-index
{
if(i <= 0) return 0;
if(i <= 1) return 1^p;
if(n <= l[i - 2] - 1) return getsum2(i - 2 , n , p);
int L;
if(p) L = (l[i - 2] - !(l[i-2]&1));
else L = (l[i- 2] - (l[i - 2] & 1));
int ans ;
if(p) ans = fib[i - 2] - evenfib[i - 2];
else ans = evenfib[i - 2];
ans += getsum2(i - 1 , n - l[i - 2] , p ^ ((l[i - 2] & 1)));
return ans;
}
int getfib(int n) ///0-index
{
if(n <= 0) return 0;
n++;
int ans = 0;
int i;
for(i = 0;l[i] <= n;i++) {
ans += fib[i] ; n -= l[i];
}
return ans + getsum(i , n);
}
int get_even(int n) ///n = 2*k
{
n++;
int ans = 0;
int i , lbefore = 0;
for(i = 0;l[i] <= n;i++) {
if(lbefore) ans += fib[i] - evenfib[i];
else ans += evenfib[i];
lbefore ^= (l[i]&1);
n -= l[i];
}
if(n) ans += getsum2(i , n - 1, lbefore);
return ans;
}
const double phi = (3 - sqrt(5)) / 2;
const double eps = 1e-6;
int getstart(int n)
{
if(n == 3) return 0;
if(n == 4) return 1;
n -= 4;
int i;
for(i = 1;1;i++) {
int lft ;
if(i & 1) lft = fib[i + 3] + 1;
else lft = fib[i + 3] - 1;
if(n <= lft) break;
n -= lft;
}
int start ;
if(i & 1) start = fib[i + 3] - n + 1;
else start = fib[i + 3] - n;
return start;
}
typedef long long ll;
const int L = 95;
int a[120] = {8,0,6,0,1,8,5,9,7,2,9,7,2,9,2,0,5,5,7,9,0,1,8,1,7,3,5,9,3,7,4,9,2,7,7,3,1,5,5,4,6,8,7,3,1,7,3,2,4,9,1,0,2,8,0,9,6,9,7,2,2,8,8,1,6,3,4,3,6,5,6,1,3,1,4,5,9,7,1,5,1,5,0,1,0,5,2,1,1,0,6,6,9,1,8,3};
ll b[120];
double cal(int n)
{
memset(b,0,sizeof(b));
for(int i = 0;i <= L;i++) b[i] = 1LL*n*a[i];
for(int i = 0;i <= L + 15;i++) {
b[i + 1] += (b[i] / 10) ; b[i] %= 10;
}
int ans = 0;
for(int i = L + 11;i >= L + 1;i--) ans = (ans * 10 + b[i]) ;
return ans;
}
void solve(int n)
{
if(n <= 2) {puts("1");return;}
int v = cal(n);
int len = n - v;v++;
int start = getstart(n);
int ans = 0;
if(len & 1) {
ans = v; ///[start + 1 , start + 3...start + len - 2]
if(start & 1) ans -= (get_even(start + len - 2) - get_even(start - 1));
else ans -= (getfib(start + len - 1) - get_even(start + len - 1) - getfib(start) + get_even(start));
}
else {
ans = getfib(start + len - 2) - getfib(start - 1);
///[start + 1 , start + len - 3]
if(start & 1) ans -= (get_even(start + len - 3) - get_even(start - 1));
else ans -= (getfib(start + len - 2) - get_even(start + len - 2) - getfib(start) + get_even(start));
}
printf("%d\n",ans);return;
}
int main()
{
l[0] = l[1] = 1;
fib[0] = 0 , fib[1] = 1;
evenfib[1] = 1;
for(int i = 2;l[i-1] <= 1000000000;i++) {
l[i] = l[i - 1] + l[i - 2];
fib[i] = fib[i - 1] + fib[i - 2];
if(l[i - 2] & 1) evenfib[i] = evenfib[i - 2] + fib[i - 1] - evenfib[i - 1];
else evenfib[i] = evenfib[i - 2] + evenfib[i - 1];
}
int t;scanf("%d",&t);
while(t--) {
int n;scanf("%d",&n);solve(n);
}
return 0;
}
Wow. Tutorial was released even before system testing was over. Nice contest overall <3
well prepared !
Wow! . Very Fast . Excellent Contest . Jiangly is new No. 1 :)
OMG!Jiangly rk 1!
Yeah! He might cross 4000 soon
The announcement has disappeared?
https://codeforces.net/blog/entry/114473
Problem F is basically a generalization of 1705E - Mark and Professor Koro. I described a segment tree-free solution here that can easily be generalized to this problem.
Thanks for sharing the solution. It is really elegant.
https://codeforces.net/contest/1810/submission/200562761
generalized map implementation for F of this round just in case someone wants to take a look
Can someone please help me with problem C My approach was to find the upper bound for each value and calculating values required to be removed and added using it Code
work with lower bound
Could you please help me with a tc where this might fail. Or why does this fail.Thank you for your time
Thank you so much bro. I multiplied insert twice :((
Nice problems and fast editorial.
In problem E, how do they come to conclusion that
|S(u′)|>2|S(u)|
?If $$$u'$$$ can reach any vertex in $$$S(u)$$$ then it can reach all vertices $$$v$$$ in $$$S(u)$$$. Before reaching $$$v$$$, $$$|S(u')| > |S(u)|$$$ and after visiting all of $$$S(u)$$$, $$$|S(u')| > 2|S(u)|$$$
It has to visit all of $$$S(u)$$$ angin, why eventually one vertex can not be visited more than $$$log(n)$$$ times
Lets say $$$v$$$ is visited by $$$u_1,u_2,...,u_i$$$, then $$$|S(u_i)|>2^i|S(v)|$$$.
Also, the reason why $$$|S(u')| > |S(u)|$$$ before reaching $$$v$$$ is because there must be some $$$x$$$ which we could not reach from $$$u$$$ (because $$$a_x > |S(u)|$$$) and $$$x$$$ was in $$$E(S(u))$$$ i.e $$$x$$$ was one of the neighbour of $$$S(u)$$$.
Are you saying that $$$ |S(u')| > |S(u)| $$$ because we reach this $$$x$$$ that is not in $$$S(u)$$$ before we reach any vertex of $$$S(u)$$$? And reaching such an $$$x$$$ would require the above condition.
But is it not possible that $$$x$$$ could only be reached after visiting some vertices in $$$S(u)$$$. Or am I understanding it wrong? Could you please explain
To clear up your confusion, I will list two lemmas, which would help you understand my above claim if you put them together.
Right, I understand these two lemmas. Now from what I get, you can get to $$$x$$$ from $$$u'$$$ before touching any vertices of $$$S(u)$$$, which gives you $$$|S(u')| > |S(u)|$$$ by Lemma-2
Then you touch all the vertices of $$$S(u)$$$ by Lemma-1 since you can reach $$$v$$$ from $$$u$$$ and this gives you the extra $$$|S(u)|$$$ in $$$|S(u')|$$$.
However I still don't get why we can reach $$$x$$$ before touching any of the vertices in $$$S(u)$$$ necessarily. Could you explain that?
Oh, now I get what your confusion is. We will always reach x before reaching any vertices in $$$S(u)$$$ because these vertices form the boundary of $$$S(u)$$$. We cannot reach an internal vertex without going through the boundary.
Example:- let's say the minimum $$$a_x$$$ value of a vertex $$$x$$$ which is not reachable from $$$u$$$ is $$$10$$$ and assume that $$$|S(u)|$$$ is $$$6$$$. Then it is impossible to reach any vertex in $$$|S(u)|$$$ without passing through a vertex with $$$a_i$$$ less than $$$10$$$.
Also, we assume that the answer exists. Meaning that we can defeat all the monsters.
Thanks!!
In problem B, "Then consider how the binary representation changes..." — I mean, all of a sudden people have to consider binary representation of a number? :) I find this kind of problem a bit weird. I know that the idea and solution is nice and neat but when you solve it you kind of expect more general approaches to work here like backtracking or some easy calculations but this kind of reasoning seem to be not suitable for problem B. I solved it exactly the way it is described in the solution, but it was just kind of a luck.
When $$$n$$$ is odd, either one of $$$\frac{n + 1}{2}$$$ or $$$\frac{n - 1}{2}$$$ is odd. You can perform the operation that makes $$$n$$$ remain in odd, eventually $$$n$$$ will end at $$$1$$$.
yeah, that's how I did it too
is there any reason as to why we do not consider the 40 spell limit in the 2nd question?
Each operation you might want to do increases the number of significant bits in the number's binary representation. As the maximum value of $$$n$$$ we might want is $$$10^9$$$ which has only $$$31$$$ bits, we would need at most $$$31$$$ operations (+/-1 if my logic has some off-by-one error) which is clearly less than $$$40$$$.
Can anyone help me in my solution for C. https://codeforces.net/contest/1810/submission/200018474.
sort the input array first
Cheers to authors. Overall Great round. I wanted to share my opinion on problem D.
Problem D is the little bit bad for C++ users compared to python.
There is a formula to find number of days require to reach height 'h'.
But instead of using formula, if we use BINARY SEARCH , then there is very stupid long long overflow.
Sincere request to authors to avoid these kind of problems which are language specific. In this problem, using binary search in c++ is 10x more difficult than using python. RDDCCD
Below is my implementation in c++, EVEN AFTER USING LONG LONG, I am getting overflow. is there any way to overcome this ?
One possible way is to set $$$r = \lceil \frac{h}{a-b} \rceil$$$ I think. Or using int128. You can also detect whether overflow occurs, like checking (climb > (8e18/(a-b)). If it occurs, just set r = m.
sure, thanks, will give it try.
There exists 128-bit integer in C++ which is big enough since you aren't crossing ~$$$10^{27}$$$ and 128-bit integer can hold numbers up to ~$$$10^{38}$$$.
You can also use the thing I used to get AC : 200027884. This prevents overflow. I got this idea from ' binary search — edu section ' of codeforces.
I faced a similar problem, so I just decided to use math to compute the #of days and it got AC. Not until I had like 10 WA's tho lol (mostly b/c i kept changing the bounds of my binary search)
Great round, thank you problemsetters!
The proof of the time complexity of E is quite an impressive part of this problem. I like it very much. (I came up with this solution in the last 20 minutes, but I thought that was $$$O(n^2log\ n)$$$ and lost the chance for a nice rating change. T_T)
ABCD are a little too easy, considering the difficulty difference between D and E. I was somehow slower on ABCD than usual, and then my rank fell down a lot.
Anyway, a nice contest. Really enjoyed it.
the proof is similar to tree-dsu, basically we can merge sets from small to large and our complexity will stay nlogn, something like that.
Right. In this problem it's easy to find we're merging sets, but the fact that $$$\vert S(u') \vert \gt \vert S(u) \vert$$$ before adding vertex $$$v$$$ , is not that obvious, I think.
200033270 I am getting the wrong answer in test case 7. I think there is some overflow error, but I cannot get it. I am using long long everywhere still. It will be helpful if somebody can find out what I am doing wrong. Thanks in advance.
Today's Codeforces contest crossed the mark of 200 million submissions, what a coincidence! Congratulations!
May be 200 million submissions?
In problem D, the tutorial and the solution use different formulas to compute
n
, givenh, a and b
. When I tried, the tutorial formula givesWrong Answer
on Test Case 7 or something. Can someone please help me understand how to arrive at the formula given in the solution code? Also, please confirm if the tutorial formula is wrong. Thanks in advance :)It is correct,see my code there.
They are actually the same, based on the fact that $$$\lceil \frac{x}{y} \rceil = \lfloor \frac{x+y-1}{y} \rfloor$$$.
Thank you so much for the proof RDDCCD, and the confirmation HELLO2024. After a lot of struggle, I finally figured out that the issue was with Python's floating point precision in the division of large numbers using the division
/
operator. The integer division//
operation somehow doesn't suffer from the same precision problem. And hence getsAccepted
! My Wild guess: " Perhaps the//
operator knows ahead of time that the return value is going to be an integer, and hence can allocate all the precision to the integer part of the answer". Usingfloor
orceil
after a/
operation is simply not foolproof, because the first division operation will give us imprecise results. Conclusion: UseC++
, or just learn more about the limitations and features of your language better.with c++ also you can get the same thing , may be one case better than yours haha,
You can check my simple solution 200085618. I hope it helps.
Thanks mate. The issue was not with the formula but with the precision of my programming language(Python).
just submitted it using c++ 17, the same code was not getting accepted in c++20 282393808
Problem B is exactly the same as problem D from yesterday's Constructor University contest.
D. Mana
in problem B , why loop started from 29
oohh , 10 to the power 9 has 29 bits
In Problem C, if we take c = 1, d = 1 and a = [3, 5, 6, 7, 4, 5]. The algorithm in tutorial gives answer 3 while according to me, the answer should be 5 calculated manually. Can someone explain how the minimum cost is 3?
If you add $$$1$$$ and $$$2$$$ and remove $$$5$$$ the array will be $$$[1,2,3,5,6,7,4]$$$, which is a permutation. You added two numbers and removed one number so the total cost is $$$3$$$.
First time ever editorial released this fast. Thanks RDDCCD
Anyone solved problem C using DP ? If yes please provide the solution.
solution I didn't name the arrays (
rm
-- cost to remove all the elements behind, andis
-- cost to insert to the current element)dp
, but I guess it could be expressed as a dp methodFor Problem D why is it
ll ans1 = max(1LL, (L - b - 1) / (a - b) + 1) , ans2 = max(1LL, (R - b - 1) / (a - b) + 1);
`and not
ll ans1 = max(1LL, ceil((double)(L - a) / (a - b)) + 1) , ans2 = max(1LL, ceil((double)(R - a) / (a - b)) + 1);
These two could mean the same thing, but we always prefer to process integers only, because double (float number) has error from its essence.
P.S. In my submission 200018265 I used
ll nl = max(0LL,l-a)/(a-b) + (max(0LL,l-a)%(a-b)!=0) + 1;
ll nh = max(0LL,h-a)/(a-b) + (max(0LL,h-a)%(a-b)!=0) + 1;
which might seem more natural
Here's my solution to E, which I find pretty beautiful too :
We'll add vertices one by one by danger increasing, keeping connected components with a dsu. For each component, we remember if we can visit all of it starting from one vertex (say it is good).
Initially, all vertices of danger 0 are marked as good.
When we add a new vertex, for each of its neighbors (smaller than him), if its component is smaller than the current danger, it becomes bad, since all of its neighbors are stronger than its size. Then we merge, the new component being good if one of the two was.
At the end, we just check if only one component is left and if it is good.
This gives a $$$O(nlog(n))$$$ solution, which is little more to implement than a dsu.
Thank you for the solution. Much easier to understand.
What is $$$mdash$$$ doing in code for F?
That's a format error. Fixed now.
Hello I am here to solve problem C using Binary Search. 1. First Step of Binary Search to choose minimum and a maximum of the answer:-
we know that we have two operations:- 1. remove an element from array a of length n (c cost per remove) 2. insert from array a of length n (d cost per insert at any position)
So, if the array is initially in the permutation form then we need zero operation but if not then we need a maximum operation to convert the array into permutation form by removing all the elements and inserting only one element which is 1 i.e** n*c+d **.
This means we need minimum operation zero(0) and maximum operation n*c+d.
parameter for bool function -> (array->a,c,d,k) this function will return that is it possible to convert an array 'a' into permutation array in 'k' cost.
first, we have to check that many different elements are present in the array because, in the permutation array, no duplicate elements are allowed.
let array 'x' contain a different element of the array 'a' in sorted order.
So we have to remove the (n-x.size()) element from an array 'a' because no duplicate elements are allowed, which takes cost c*(n-x.size()).
and array 'x' must contain 1 element because without one permutation array is not possible. therefore, if x does not contain 1 then we have to insert 1 in the first place which takes cost 'd'.
Finally, we come to the last operation of this problem where we have to convert the 'x' array into a permutation array:-
Code for bool function :- bool helper(ll n,ll cost,set&s,ll c,ll d){ cost -= (n-s.size())*c; std::vectorans; for(auto i : s){ ans.push_back(i); } if(ans[0] != 1){ ans.insert(ans.begin(),1); cost -= d; }
}
My Code for this Solution using Binary Search:- https://codeforces.net/contest/1810/submission/200121687
Is it possible to solve problem E with the algorithm for finding bridges online?
I am getting WA in TC 4, I don't know why? Can somebody help me? Solution:https://codeforces.net/contest/1810/submission/200348409
My codes Why will it overflow?And I don't no what's wrong will my solution.
Can anyone explain in problem H, how the formula $$$d_i = n - \lceil\frac{i}{\phi}\rceil + 1$$$ pops out from $$$\sum_{j=1}^k{[d_j-j \ge d_k]} + n - d_k + 1 = k$$$ in the second lemma proof? Is this a known fact and does it have any name on it? You have to at least come up with shape of the formula in order to proceed through the proof further anyway...
Actually it's: find the rule by making observation, then try to prove it.
Alright. Thanks for you reply.
Can we solve problem F using Huffman Tree? Although they seems similar I still have no idea about that. I can only do it in $$$O(qnlogn)$$$.
In editorial of problem E,
v is add into S(u′) again
. We are considering only the case when v is add. We would be processing v also when we add it to some E(S(u')). In this case, the condition|S(u′)|>2|S(u)|
might fail.What am I missing?
Ah, you can try to think in another way: if we only consider adding v to some $$$S(u)$$$, it will not exceed $$$log(n)$$$ times per vertex. And what happened when we add v to some $$$S(u)$$$? We visit all it's neighbors and (possibly) add them to $$$E(S(u))$$$. That would not exceed $$$deg(v)$$$ times. Overall, it will not exceed $$$log(n) \cdot \sum{deg(v)} = m log(n)$$$.
Note that in H, $$$O(N_{max}+T)$$$ time and space works as well. We sort the queries and simulate the part before $$$x$$$. Since the part after $$$x$$$ is just an alternating-sign sum and we're adding/removing elements from the sum in 2-pointers style, it's easy to maintain the current sum until the last duplicate element and extend it to all required elements for each query. The only tricky part is implementation since there's some casework based on parity and $$$O(N_{max})$$$ space is a lot, I used bitset to denote which elements are duplicated.
What kind of test is testcase 4 : [5189th token] in problem E? (wrong answer expected YES, found NO)
Nice Explanations