idea: Cocoly1990
Solution
Tutorial is loading...
Code
By Imakf
#include <iostream>
void solve(){
int n; std::cin >> n;
for(int i = 1 ,nouse ; i <= n ; ++i){
std::cin >> nouse;
}
std::cout << "1 " << n << std::endl;
}
int main(){
int t; std::cin >> t;
while(t--) solve();
return 0;
}
1764B - Doremy's Perfect Math Class
idea: waaitg
Solution
Tutorial is loading...
Code
By waaitg
#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
int a[maxn];
int gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}
int main(){
int t;scanf("%d",&t);
while(t--){
int n;scanf("%d",&n);
int tmp=0;
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
tmp=gcd(tmp,a[i]);
}
printf("%d\n",a[n]/tmp+(a[1]==0));
}
return 0;
}
1764C - Doremy's City Construction
idea: waaitg
Solution
Tutorial is loading...
Code
By waaitg
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ch() getchar()
#define pc(x) putchar(x)
using namespace std;
template<typename T>void read(T&x){
static char c;static int f;
for(f=1,c=ch();c<'0'||c>'9';c=ch())if(c=='-')f=-f;
for(x=0;c>='0'&&c<='9';c=ch()){x=x*10+(c&15);}x*=f;
}
template<typename T>void write(T x){
static char q[64];int cnt=0;
if(x==0)return pc('0'),void();
if(x<0)pc('-'),x=-x;
while(x)q[cnt++]=x%10+'0',x/=10;
while(cnt--)pc(q[cnt]);
}
const int maxn=200005;
int a[maxn];
int main(){
int t;read(t);
while(t--){
int n;read(n);
for(int i=1;i<=n;++i)
read(a[i]);
sort(a+1,a+n+1);
if(a[1]==a[n]){
write(n/2),pc('\n');
continue;
}
long long ans=0;
for(int l=1,r=1;l<=n;l=r=r+1){
while(r+1<=n&&a[r+1]==a[l])++r;
ans=max(ans,1ll*(n-r)*r);
}
write(ans),pc('\n');
}
return 0;
}
idea: Imakf
Solution
Tutorial is loading...
Code
By Imakf
#include <cstdio>
#include <iostream>
#define LL long long
const int MX = 5000 + 233;
LL C[MX][MX] ,n ,p ,fac[MX];
void init(){
for(int i = 0 ; i < MX ; ++i) C[i][0] = 1;
for(int i = 1 ; i < MX ; ++i)
for(int j = 1 ; j < MX ; ++j)
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % p;
fac[0] = fac[1] = 1 % p;
for(int i = 2 ; i < MX ; ++i) fac[i] = fac[i - 1] * i % p;
}
int main(){
std::cin >> n >> p;
init();
int t = n / 2;
LL Ans = 0;
for(int i = t ; i <= n - 1 ; ++i){
if((n & 1) && i == n - 1) break;
int upper = (i == n - 1) ? n - i - 1 : n - i - 2;
for(int j = 0 ; j <= upper ; ++j){
Ans = (Ans + n * (2 * t - i) * C[upper][j] % p * fac[j + i - 1]) % p;
}
}
std::cout << Ans << std::endl;
return 0;
}
idea: Imakf
Solution
Tutorial is loading...
Code
By Imakf
#include <bits/stdc++.h>
#define debug(...) fprintf(stderr ,__VA_ARGS__)
#define LL long long
const int MX = 2e5 + 5;
int n ,s;
struct Goat{
int x ,y ,id;
}A[MX];
bool cmp(Goat a ,Goat b){
return a.x < b.x;
}
int mx[MX];
int calc(int id){
if(id == 1) return A[id].x;
int far = std::max(calc(id - 1) ,mx[id - 2]);
return std::max(std::min(far ,A[id].x) + A[id].y ,A[id].x);
}
int ans[MX];
void solve(){
scanf("%d%d" ,&n ,&s);
for(int i = 1 ,x ,y ; i <= n ; ++i){
scanf("%d%d" ,&x ,&y);
A[i] = (Goat){x ,y ,i};
ans[i] = false;
}
std::sort(A + 1 ,A + 1 + n ,cmp);
for(int i = 1 ; i <= n ; ++i){
mx[i] = std::max(A[i].x + A[i].y ,mx[i - 1]);
}
for(int i = 1 ; i < n ; ++i){
if(A[i].x + A[i].y >= s){
ans[A[i].id] = true;
}
}
if(calc(n) >= s) ans[A[n].id] = true;
puts(ans[1] ? "YES" : "NO");
}
int main(){
int t; scanf("%d" ,&t);
while(t--) solve();
return 0;
}
1764F - Doremy's Experimental Tree
idea: Cocoly1990
Solution
Tutorial is loading...
Code
By Imakf
#include <bits/stdc++.h>
#define debug(...) fprintf(stderr ,__VA_ARGS__)
#define LL long long
const int MX = 3e3 + 5;
bool vis[MX];
LL w[MX][MX] ,dis[MX];
std::vector<int> e[MX];
int size[MX];
void dfs(int x ,int f){
size[x] = 1;
for(auto i : e[x]){
if(i == f) continue;
dfs(i ,x);
size[x] += size[i];
}
for(auto i : e[x]){
if(i == f) continue;
printf("%d %d %lld\n" ,x ,i ,(w[1][x] - w[1][i]) / size[i]);
}
}
int main(){
int n; scanf("%d" ,&n);
memset(w ,-0x3f ,sizeof w);
for(int i = 1 ; i <= n ; ++i){
for(int j = 1 ; j <= i ; ++j){
scanf("%lld" ,&w[i][j]);
w[j][i] = w[i][j];
}
}
memset(dis ,-0x3f ,sizeof dis);
dis[1] = 0;
for(int i = 1 ; i <= n ; ++i){
int x = 0;
for(int j = 1 ; j <= n ; ++j){
if(!vis[j] && (!x || dis[j] > dis[x])){
x = j;
}
}
//debug("x = %d " ,x);
//ans += dis[x];
if(i != 1) for(int j = 1 ; j <= n ; ++j){
if(w[j][x] == dis[x] && vis[j]){
e[x].push_back(j);
e[j].push_back(x);
//debug("%d %d\n" ,x ,j);
}
}
vis[x] = true;
for(int j = 1 ; j <= n ; ++j){
dis[j] = std::max(dis[j] ,w[x][j]);
}
}
//return 0;
dfs(1 ,1);
return 0;
}
1764G3 - Doremy's Perfect DS Class (Hard Version)
idea: waaitg
Solution
Tutorial is loading...
G1 Code
By Imakf
#include <bits/stdc++.h>
using namespace std;
#define debug(...) fprintf(stderr, __VA_ARGS__)
std::map<std::pair<int, int>, int> M;
int n;
int query(int l, int r, int k = 2) {
if (l == r) return 1;
if (l == 1 && r == n) {
return n / k + 1;
}
if (k == 2 && M.count(make_pair(l, r)))
return M[make_pair(l, r)];
printf("? %d %d %d\n",l ,r, k);
fflush(stdout);
int x;
scanf("%d", &x);
if (k == 2) {
M[make_pair(l, r)] = x;
}
return x;
}
void answer(int x) {
printf("! %d\n", x);
fflush(stdout);
exit(0);
}
int main() {
scanf("%d", &n);
int npos = 0;
if (n % 2 == 0) {
int l = 1, r = n, mid;
while (l <= r) {
mid = (l + r) >> 1;
if (query(1, mid, n) == 2) {
r = mid - 1;
} else {
l = mid + 1;
}
npos = r + 1;
}
if (npos == 1 || npos == 2) {
if (query(2, n, n) == 1) {
npos = 1;
} else {
npos = 2;
}
}
}
//answer(npos);
//if (n & 1) {
int l = 1, r = n - 1, mid;
while (l <= r) {
debug("[%d ,%d]\n",l ,r);
mid = (l + r) >> 1;
int lq = 2 * query(1, mid) - (mid - 1 + 1);
int rq = 2 * query(mid + 1, n) - (n - (mid + 1) + 1);
if (npos) {
if (npos <= mid) --lq;
else --rq;
}
if (lq > rq) {
r = mid - 1;
} else {
l = mid + 1;
}
}
// cut [r + 1, r + 2]
++r;
// now cut [r, r + 1]
answer(r);
// }
}
G3 Code
By waaitg
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n;
int query(int l,int r,int k){
printf("? %d %d %d\n",l,r,k);
fflush(stdout);int re;scanf("%d",&re);
return re;
}
void answer(int x){
printf("! %d\n",x);
fflush(stdout);
}
int rt=-1;
void divide(int l,int r,int l1,int l2,int r1,int r2){
if(l==r){
answer(l);
return;
}
if(l+1==r){
if(r1==r2+1){
if(query(r,n,2)==r2+1)answer(r);
else answer(l);
}
else if(l1==l2+1){
if(query(1,l,2)==l2+1)answer(l);
else answer(r);
}
else{
if(l>1){
if(query(1,l,n)==2)answer(r);
else answer(l);
}
else{
if(query(r,n,n)==2)answer(l);
else answer(r);
}
}
return;
}
int mid=(l+r)>>1;
int L=query(1,mid,2),R=query(mid+1,n,2);
if(L*2-mid>R*2-(n-mid))divide(l,mid,L,l2,r1,R);
else if(L*2-mid<R*2-(n-mid))divide(mid+1,r,l1,L,R,r2);
else{
if(~rt){
if(rt)divide(l,mid,L,l2,r1,R);
else divide(mid+1,r,l1,L,R,r2);
}
if(query(1,mid,n)==2)rt=0,divide(mid+1,r,l1,L,R,r2);
else rt=1,divide(l,mid,L,l2,r1,R);
}
}
int main(){
scanf("%d",&n);
divide(1,n,n/2+1,0,n/2+1,0);
return 0;
}
idea: Imakf, waaitg and errorgorn
Solution
Tutorial is loading...
Code
By errorgorn
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define fi first
#define se second
#define endl '\n'
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int n,m,k;
ii arr[600005];
int ans[400005];
vector<int> uni;
int nxt[200005];
int state[200005];
int state2[200005];
bool has(int l,int r,set<int> &s){
auto it=s.lb(l);
return *it<r;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin.exceptions(ios::badbit | ios::failbit);
cin>>n>>m>>k;
rep(x,0,m) cin>>arr[x].fi>>arr[x].se;
rep(x,0,m) arr[x].fi--,arr[x].se--;
rep(x,0,2*m) arr[x+m]=arr[x];
int l=0;
while (l<m){
uni={0,n};
rep(x,l,l+2*k) uni.pub(arr[x].fi),uni.pub(arr[x].se+1);
sort(all(uni)); uni.erase(unique(all(uni)),uni.end());
rep(x,0,sz(uni)-1) nxt[uni[x]]=uni[x+1];
set<ii> s; for (auto it:uni) s.insert({it,it}); //position, color
rep(x,0,sz(uni)) state[uni[x]]=state2[uni[x]]=1;
vector<iii> proc; //time, position, state
rep(x,l+k,l+2*k){
if (s.count({arr[x].fi,arr[x].fi}) && state[arr[x].fi]){
proc.pub({x,arr[x].fi,state[arr[x].fi]});
state[arr[x].fi]=0;
}
while (true){
auto it=s.ub(ii(arr[x].fi,1e9));
if ((*it).fi>arr[x].se) break;
if (arr[x].se+1<(*next(it)).fi) s.insert({arr[x].se+1,(*it).se});
else{
proc.pub({x,(*it).se,state[(*it).se]});
state[(*it).se]=0;
}
s.erase(it);
}
}
int curr=0;
set<int> pos={n};
for (auto [a,b]:s) if (b!=n){
curr++;
if (state[b]) curr+=nxt[b]-b-1;
pos.insert(b);
}
s.clear(); for (auto it:uni) s.insert({it,it}); //color, position
set<ii> ranges; rep(x,0,sz(uni)-1) ranges.insert({uni[x],uni[x+1]});
rep(x,l+k,l){
//merge things
auto it=s.lb({arr[x].fi,-1});
vector<int> v={(*it).se};
while ((*it).fi<=arr[x].se){
it=next(it);
s.erase(prev(it));
v.pub((*it).se);
}
if (sz(v)>1){
rep(x,0,sz(v)-1){
if (state[v[x]] && state2[v[x]]) curr-=v[x+1]-v[x]-1;
state2[v[x]]=0;
curr-=has(v[x],v[x+1],pos);
ranges.erase({v[x],v[x+1]});
}
curr+=has(v[0],v[sz(v)-1],pos);
s.insert({arr[x].fi,v[0]});
ranges.insert({v[0],v[sz(v)-1]});
}
while (!proc.empty() && get<0>(proc.back())==x+k){
int a,b,c; tie(a,b,c)=proc.back(); proc.pob();
if (c){
state[b]=c;
if (state[b] && state2[b]) curr+=nxt[b]-b-1;
}
if (!pos.count(b)){
auto it=prev(ranges.ub({b,1e9}));
int l,r; tie(l,r)=*it;
if (!has(l,r,pos)) curr++;
pos.insert(b);
}
}
ans[x]=curr;
}
l+=k;
}
rep(x,0,m) cout<<ans[x]<<" "; cout<<endl;
}
I hope you liked the GIF on problem D. I spent hours making it on manim.
Since the file size was very large even after making resolution and framerate very small, I was considering to only put images in the statement and host the GIF on an external website. Would this method of hosting the GIF be preferred, and if so, what site can be used that everyone can access?
I prefer using imgur for such purposes. As an alternative, Discord (yes, Discord) works as a good alternative as well, but using Discord as a CDN just sounds awkward, doesn't it?
I believe imgur is blocked in Indonesia and discord is blocked in China
Oh, that's too bad. I can't think of any good CDNs (excluding widely known paid ones such as Cloudflare) anymore. I hope MikeMirzayanov could help host the contest materials.
I believe imgur is blocked in Indonesia and discord is blocked in China
Yeah. I also spent hours watching the GIF.
same
Yeah it was really good for understanding the problem
As I enjoyed watching the GIF, I believe you must had fun of making the GIF
The GIF was pretty. I wish, at some time I would learn how to create such GIFs, they are very cute.
However, once I watched it, I understood the problem, so it became needless. If I solved the problem relatively fast, it would be ok; however, I stuck at it, and at some point the GIF on the second monitor (I kept the statement on one monitor, while coding on the other) became too distracting, that I even blocked it with AdBlock ;P
Probably it would be better to put it somewhere deep below, in the notes section.
ok
It was good. But I wish it was 2 separate gifs for n=8 and n=9, so I don't spend twice as much time waiting for the case I'm currently working on :)
Excuse me. How to prove the property in F?
Take the spanning tree made out of some edge that isnt in the original tree. Because of the property that "If path (x,y)⊂(X,Y), then f(x,y)>f(X,Y)", you can remove that edge and insert an edge from the original tree to connect the graph, making the weight bigger. Therefore, it cannot be a maximum spanning tree.
Can someone hack my 182692536, I think it might be cubic.
Guys, I tried solving the first problem in O(n^2). Can anyone share the Efficient approach ? Thanks in advance.
have you tried reading the blog you are commenting on?
Yes, @biggy_cheese. That's why I have asked for some approach after going through the pithy solution, and the incomprehensible code discussed above.
the best range is always $$$[1, n]$$$.
The answer is always the range 1 to n because if we consider a range say l to r, then increasing the range to left or right in the worst case give us a distinct element that is not already present which will decrease the score, but since size also increase by one, the effect is cancelled and score remains same, hence increasing subarray size will mean score might increase or remain the same, hence we should take the entire array for maximum score
I cannot see any correlation between these two sentences... Can anyone tell me how to conclude the second one?
Took me some time to parse this sentence as well
Only those pegs that make rubber band touch the blue peg can be the last move. And that is the number of such pegs
Imagine a long consecutive stretch of removed red pegs (i.e. $$$i>t$$$). There is a number of pegs in the beginning and in the end of this stretch that cannot be removed in the last move (e.g. consider the very first peg in the stretch, it cannot be removed in the last move because, in that case, there was already a consecutive stretch of $$$i-1\ge t$$$ removed pegs). Let's count the number of pegs that cannot be removed in the last move: there are $$$i-t$$$ pegs at the beginning and $$$i-t$$$ pegs at the end. So, the number of pegs that can be removed in the last move is $$$i-(i-t)-(i-t)=2t-i$$$.
is there's a way to solve Problem D by OEIS ?
i generated the first 4 elements (3,16,50,612) but got no results :(
no
You already answered your own question.
But you can always contribute a new sequence to OEIS, if you can rephrase this problem into something concise and general enough.
D can be solved in $$$O(n)$$$.
Let's call an array bad, if removing all pegs in the array results in the blue peg being touched. Bad arrays differ from "ending states" in that the blue peg may have been touched before removing the last peg in the array. "Ending states" are exactly those bad arrays whose proper prefixes are not bad.
Obviously, a bad array is still bad after adding any number to its end. Let $$$f(k)$$$ be the number of bad arrays of length $$$k$$$. Adding any number not yet in the array to the end of them creates $$$(n-k)f(k)$$$ bad arrays of length $$$k+1$$$ that have bad proper prefixes, and all bad arrays with bad proper prefixes can be generated in this way. Thus, there are exactly $$$f(k+1)-(n-k)f(k)$$$ "ending states" of length $$$k+1$$$. Thus the answer is $$$\sum_{k=0}^{n-1}(f(k+1)-(n-k)f(k))$$$, which can be computed in $$$O(n)$$$ once we know all $$$f(k)$$$'s.
Note that $$$f(k)=0$$$ for $$$k<t=\lfloor\frac{n}{2}\rfloor$$$, and $$$f(k)=n!$$$ for $$$k\geq n-1$$$. Otherwise, let $$$l\in[t,k]$$$ be the length of the longest continuous segment of removed pegs. There can only be one such segment, whose location has $$$n$$$ choices. The remaining removed pegs have $$$\binom{n-l-2}{k-l}$$$ choices, and all removed pegs' permutation have $$$k!$$$ choices. Thus $$$f(k)=nk!\sum_{l=t}^{k}\binom{n-l-2}{k-l}$$$. Using https://en.wikipedia.org/wiki/Hockey-stick_identity, the last summation simplifies to $$$\binom{n-t-1}{k-t}$$$. Thus $$$f(k)=nk!\binom{n-t-1}{k-t}$$$ can be computed in $$$O(1)$$$ each after precomputing factorials in $$$O(n)$$$.
Edit: Accepted $$$O(n)$$$ code: https://codeforces.me/contest/1764/submission/182702973
Does anyone know what the counting technique used on D is called? I don’t have a math background so I don’t really understand how the “choose” this many moves part works.
https://cp-algorithms.com/combinatorics/binomial-coefficients.html
Thanks!
deleted
hi tea dose
I have a totally different solution for E. My approach is this: if x1 + y1 is less than k then the answer is no. If x1 >= k then the answer is yes. Otherwise, let's notice that we have to determine if we can color any number between k — y1 and x1. Let's call it solving the problem for the segment [k — y1, x1] and the set of xi and yi where i > 1. We can notice that if any xi is greater than the left point of the segment, the answer is yes. Otherwise, if for all i xi + yi is less than the left point of the segment, the answer is no. If there is more than one i with xi + yi >= left point of the segment, then the answer is yes, because if there are at least two, say, j and k (let's say xj >= xk), then we can use the j-th position to color the point xk and then color the left side of the segment using the k-th position. If there is exactly one such i, we can consider the same problem for the segment [left position of current segment — yi, xi]. Also we have to remove the i-th position from consideration for the next checks. Thus we iterate through segments, and at every iteration we either prove that the answer is yes or no, or we need to solve the problem for a new segment with less positions in consideration. We need to keep a set for xi and xi + yi for all i that are still in consideration. Actually, now that I look at my solution, we never use the right points of the segments, so we can only consider the left points. Here is my submission: 182681261
Great contest. I really enjoyed the problems a lot especially D tho being hard and the most exciting is that I returned BLUE again! Wohhoo!
Here is another way to solve problem E.
Let $$$\text{goal} = K - b_1$$$ be the number we have to reach to paint $$$K$$$ with color $$$1$$$.
There are three cases:
If there exist unused $$$x$$$ and $$$y$$$ such that $$$a_x + b_x \ge \text{goal}$$$ and $$$a_y + b_y \ge \text{goal}$$$ (assume $$$a_x \le a_y$$$), then we can first paint position $$$a_x$$$ as color $$$y$$$, then paint position $$$\text{goal} \le a_x + b_x$$$ as color $$$x$$$.
The $$$\text{goal}$$$ is impossible to reach if there is no such $$$x$$$.
If there is only one such $$$x$$$, then $$$\text{goal}$$$ could only be painted with color $$$x$$$. Therefore $$$x$$$ is now set to "used" and $$$\text{goal} \leftarrow \text{goal} - b_x$$$.
So, we can first sort the pairs by $$$a_x + b_x$$$ descending and then update the value of $$$\text{goal}$$$ using a for-loop.
Code: 182685578
I think our solutions are similar, but your comment is much better :)
imagine wrt to a node.way to count .
Nice round, but I need more training, thank you
I had a very simple solution to F. We notice that "f" only decreases on extending the cycle. So if we look at $$$f(1, x)$$$ with least reduction from $$$f(1, 1)$$$, $$$x$$$ must be adjacent to 1, otherwise shortening the cycle could make the solution better. So we iterate over $$$x$$$ in increasing order of reduction. To check if $$$x$$$ isn't actually in some previous subtree, we can use the fact that $$$f(s,x)$$$ would be larger if $$$s$$$ is adjacent to $$$1$$$ and $$$x$$$ is in it's subtree. If it's smaller for all current found edges, it must be a new adjacent edge.
this is my soluion too.
Your approach is pretty intuitive and very intresting But it just only finds the structure of the tree. How did you actually come up with weights of each edge. I think it is also going to be pretty much intuitive.
I used the formula in this comment. You can deduce it by noticing that the contribution of each node $$$x$$$ in the $$$f(u, u) + f(v, v) - 2f(u, v)$$$ is $$$d(x, u) + d(x, v) - 2\min(d(x, u), d(x, v))$$$. Since $$$d(x, u) + w = d(x, v)$$$ or vice versa, its easy to see the value will be $$$w$$$, or the weight of the $$$(u, v)$$$ edge.
thanks for your valuable time and efforts to explain. I realized this comment some time after i wrote the comment.
Here is another way to think about problem D.
The pegs are numbered from $$$0$$$ to $$$n-1$$$ below.
First, we can assume that the rubber band is stretched around peg $$$0$$$, the blue peg, and maybe some peg $$$x$$$. By symmetry, we can calculate the answer for $$$x \in \left[0, \left\lceil \frac{n}{2} \right\rceil - 1 \right]$$$ and then multiply it by $$$n$$$.
If we fix peg $$$0$$$ and peg $$$x$$$, the other pegs can be classified into three types:
Must be removed ($$$M$$$): the pegs in $$$[x+1, n-1]$$$ must be removed to make the rubber touch the blue peg.
Last to remove ($$$L$$$): one of the pegs in $$$\left[\left\lceil \frac{n}{2} \right\rceil, \left\lfloor \frac{n}{2} + x \right\rfloor \right]$$$ should be the last to remove. Otherwise, the rubber will touch the blue peg too early.
Optional ($$$S$$$): pegs in $$$[1, x-1]$$$ are optional.
If we choose $$$s$$$ pegs in optional type, then there will be $$$(M+s)! \cdot \frac{L}{M+s}$$$ ways to remove them. Therefore, the total number of ways is
Code: 182682907
Wow. Great solution
Why we need divide for (M+s)?
Really nice solution.
Video Solution for Problem D explaining the same.
great explanation
x=0 not possible in case of odd no of pegs .prrof id the collinearity which is not attainable in case of odd no of pegs
Broo ! what a great solution.
There is a significant difficulty gap betw C and D (like ..1200-1800) . Nice round btw :)
Cool round, E and G broke my brain (in a good way), thanks!
and d broke my laptop in a bad way :).
In Problem D, having a real hard time trying to understand why there are 2t — i ways of choosing the last move, can anyone enlighten me?
Hope this answer helps.
Video Solution for Problem C.
Will probably create one for Problem D as well.
(for problem F) Actually, after finding the edges of the tree, their weights can be found even simpler than in editorial: If we have an edge between vertices $$$(x, y)$$$, it's weight is just $$$\frac{f(x, x) + f(y, y) - f(x, y) \cdot 2} {n}$$$. So no DFS needed!
I had a similar approach for F, no DFS and no need to first find the edges of the tree — for vertices $$$(x, y)$$$ the formula above gives the distance $$$D(x, y)$$$ between x and y on the tree. Then we simply sort all the distances and iterate through them in increasing order, using DSU — if our two vertices are in different components we merge them and print this edge, otherwise if they’re in the same component we ignore this distance and keep going. This works because every time we encounter a distance $$$D(i, j)$$$ that doesn’t correspond to an edge this only occurs after we’ve seen all the edges on the tree between $$$i$$$ and $$$j$$$.
182848636
F time limit is 2.5s, and the official editoral solution cost 2464ms(??????) in C++20 submission/182954105 (same code in c++17 982ms submission/182954544)
[[user:waaitg] g3 code in the editorial seems to be having bug. But it is giving accepted verdict on submitting.please correct me if iam unable to understand the below lines correctly. else{ if(){ if(rt)divide(l,mid,L,l2,r1,R); else divide(mid+1,r,l1,L,R,r2); } if(query(1,mid,n)==2)rt=0,divide(mid+1,r,l1,L,R,r2); else rt=1,divide(l,mid,L,l2,r1,R); } I suspect that multiple branches get created in the recursion and also the excess usage of queries when n is even.
For problem C, the following binary search gets TLE.
But the following one gets Accepted.
The difference is only 10^6 vs 2*10^5. Not sure whether this time limit is intended.
The second one does $$$O(n)$$$ binary searches per test case while the first does up to $$$10^6$$$ binary searches per test case. If you add over $$$10^4$$$ test cases, this leads to $$$10^{10}$$$ operations which is too slow.
Wow, I didn’t realize that even when n=2 the first one can still do 10^6 binary searches. Thank you!
Hey, in the c problem, we are coloring them based on their neighborhood, right (or is it just given as an example?)Cause I have colored them based on their neighborhood, I cannot find the correct answer. also why are we dividing the whole set into two parts? How will it ensure we get the answer without violating the condition mentioned in the question?
Problem C is essentially forming a bipartite graph. If you look at the 3-vertex-paths you will realize that it's going back and forth between the two vertex sets and thus the condition is satisfied.
I have a different solution to problem F:
consider building the tree from an connect component $$$CC$$$ which initially have only vertex $$$1$$$, then consider $$$f(u, v)$$$ where $$$u \in CC, v \notin CC$$$, if $$$u$$$ and $$$v$$$ are not adjacent, we can let one of the vertex approach another by one edge without breaking the rule $$$u \in CC, v \notin CC$$$, let say we move vertex $$$u$$$ to have a new vertex $$$u'$$$, then it is easy to see that $$$f(u', v) > f(u, v)$$$, thus if $$$f(x, y)$$$ is the $$$max(f(u, v))$$$ among all possible $$$(u, v)$$$, $$$x$$$ and $$$y$$$ must be adjacent, and we can span an edge between them.
And by doing this process $$$n - 1$$$ times, we can know the whole structure of the tree.
Regard to the implementation, just use a priority queue to maintain $$$f(u, v), u \in CC, v \notin CC$$$ in $$$O(n^2\lg n)$$$.
edit: I found out this is actually just what Prim's algorithm does, so it is actually the same as the editorial but with a prove.
The weights of edges in problem F look precisely like the result of keyboard mashing