### Aksenov239's blog

By Aksenov239, history, 2 months ago,

Hello, everybody!

We would like to invite you to participate in the Mirror of The ICPC World Finals Moscow Invitational Contest. The original contest was made for the teams who cannot come to The World Finals in Moscow. They were competing for the medals and glory. The Invitational contest has already passed and the results will be revealed on October 5th.

The mirror contest will be held by almost standard ICPC rules with 10 to 14 problems. The difference from the traditional ICPC format is that your team can use three computers instead of one. The problems are expected to be of The World Finals difficulty. Also, the round will be unrated!

The problemset was prepared by NERC Jury Team with the help of many other people. The chief judge is Roman elizarov Elizarov. The jury members are Pavel PavelKunyavskiy Kunyavskiy, Georgy kgeorgiy Korneev, Evgeny eatmore Kapun, Ilya izban Zban, Niyaz niyaznigmatul Nigmatullin, Vasiliy SirShokoladina Mokin, Daniil danilka.pro Sagunov, Gennady tourist Korotkevich, Oleg snarknews Hristenko, Egor Egor Kulikov, Borys qwerty787788 Minaev, Pavel pashka Mavrin, Mike MikeMirzayanov Mirzayanov, Anton Paramonov, Bruce bmerry Merry, Zachary Friggstad Friggstad, Jakub Wojtaszczyk, David Van Brackle, and myself. (I hope I haven't missed somebody. :P)

I hope you will like the contest! Good luck and have fun!

UPD: The editorial is available here.

• +300

 » 2 months ago, # |   -81 Will we get certificate of participation???
•  » » 2 months ago, # ^ |   +5 In the mirror you will not recieve any certificates, unfortunately.
 » 2 months ago, # |   +22 For the first time ICPC WF problems will get CF ratings (in problem-set page).
•  » » 2 months ago, # ^ |   +21 Which will probably be broken anyway, as the problem X-rated guy can solve in 5 hours is a bit harder than a problem X-rated guy can solve in 2...
•  » » » 2 months ago, # ^ |   -44 Most contestants participate in teams, which increases their rating by 100-200, which more or less takes care of the fact you pointed out. But for solo participants, it won't reflect that, it's true.
 » 2 months ago, # |   +177 Problems are cool, recommend to participate, but if you are not div1, it will be too hard and sad for you.
 » 2 months ago, # |   -9 Can anyone tell the maximum team size please? Thanks ;_;
•  » » 2 months ago, # ^ |   +3 Three people.
•  » » » 2 months ago, # ^ |   0 Thank you
 » 2 months ago, # |   +17 what does it mean?
•  » » 2 months ago, # ^ |   +40 I think Codeforces can find(guess) that they are dangerous teams.
•  » » » 2 months ago, # ^ |   0 i.e. cheaters? I checked one team, no cheaters are there
•  » » 2 months ago, # ^ |   +56 I think it means that someone of that team is already in another team
•  » » » 2 months ago, # ^ |   0 oh, nice, thank you
 » 2 months ago, # |   +2 Anyone wants to team up with me ?
 » 2 months ago, # |   +21 Where can I find the live leaderboard of ICPC WF?
•  » » 2 months ago, # ^ |   +19 It is not World Finals! It is World Finals Invitational.
•  » » » 2 months ago, # ^ |   +8 Oh, my bad, didn't read the blog properly
 » 2 months ago, # |   +43 How to solve L ?
•  » » 2 months ago, # ^ | ← Rev. 5 →   +58 Hint 1What if you are given a tree, not a graph, how do you solve it? Hint 2Building mst by the edges with a maximum width and considering the edges on this mst is enough. Hint 3What edges in the tree will be broken first? Hint 4Consider the edge with a minimum width in a tree, there are two approaches. You can either collect everything from one subtree and go to another subtree or vice versa. Think about how can you solve the case with the tree with this. Our Solution$O(N + M * log(M))$ due to sort // by paradox #include using namespace std; typedef long long ll; typedef long double ld; typedef pair pii; typedef vector vi; #define pb push_back #define mp make_pair #define fi first #define se second #define all(x) x.begin(), x.end() #define sz(x) (int)x.size() #define y1 y1234567890 #define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define file_io(s) freopen((s)".in", "r", stdin); freopen((s)".out", "w", stdout) const int N = 1e5; const int M = N + 7; const double EPS = 1e-10; const int MOD = 1e9 + 7; const ll INF = 2e13; int a[M]; vector> edges; int sz[M], p[M]; ll mx[M], sum[M]; int getParent(int v) { return p[v] = (p[v] == v ? v : getParent(p[v])); } void merge(int v, int u, int w) { v = getParent(v); u = getParent(u); if (v == u) return; if (sz[v] < sz[u]) swap(v, u); ll fromV = -INF, fromU = -INF; if (sum[v] <= mx[u]) { fromV = min(mx[u], 1LL * w) - sum[v]; } if (sum[u] <= mx[v]) { fromU = min(mx[v], 1LL * w) - sum[u]; } mx[v] = max(fromV, fromU); sum[v] += sum[u]; p[u] = v; sz[v] += sz[u]; } void solve() { int n, m; scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); p[i] = i; sz[i] = 1; mx[i] = INF; sum[i] = a[i]; } for (int i = 1; i <= m; i++) { int v, u, w; scanf("%d %d %d", &v, &u, &w); edges.pb({w, {v, u}}); } sort(all(edges)); reverse(all(edges)); for (auto &edge : edges) { merge(edge.se.fi, edge.se.se, edge.fi); } int v = getParent(1); if (sz[v] != n || mx[v] < 1) { printf("-1\n"); } else { printf("%lld\n", mx[v]); } } int main() { int tt = 1; // scanf("%d", &tt); while (tt--) { solve(); } return 0; } 
•  » » » 2 months ago, # ^ |   0 Thanks!
•  » » » 2 months ago, # ^ |   0 Can you explain how mx changes when we combine 2 sets U and V?
•  » » 2 months ago, # ^ |   +14 Here is a very overcomplicated (I have no idea if this indeed is the solution) and ugly (we managed to fit this in 1880ms) idea.We use binary search for the answer. For each $W$, we check if $W$ can be the width when we finish the run (hence answer will be $W - \sum c_i$)To check for each $W$, we use union-find and check the nodes in reverse order. We start with $W$, and subtract weight every time we eat candy. When we eat sufficiently many candies, width is reduced enough and new edges are now open (thus UF works). Although we don't know where to start (i.e, in the original problem, where to end), we can check as "if we started at $x$, can we reach $y$" with UF. To do this, we maintain for each component of UF, set of next-extendable vertices. When we eat a candy, we have information in the form of "by taking this component as a whole, we can decrease our width by $x$" and for all extendable vertices from this component, we can merge those vertices with current component, increasing $x$ and possibly opening new edges. When merging, this 'set of next extendable vertices' should also be merged. Here we use small-to-large trick. Also the set can be maintained as priority queues.Summary : Binary search with (DSU + priority queue extendable vertices + small to large). Time complexity is $O(n \alpha(n) \log^2 n \log 10^{9})$ which looks horrendous.
•  » » » 2 months ago, # ^ |   +11 This idea can be implemented without binary searching for the answer: at every step of your DSU process, just pick the edge that allows for the greatest initial width. Then, the minimum of these allowed initial widths is the final answer. This leads to an $\mathcal{O}(n \log^2 n)$ solution; my code passes in about 200ms.
•  » » » » 2 months ago, # ^ |   +3 Wow. Why weren't we able to think this in contest... This now makes a lot more sense. Thanks.
•  » » » » 2 months ago, # ^ |   0 Why log^2? Isn't it just single log?
•  » » » » » 2 months ago, # ^ |   0 In the worst case, my solution performs $\mathcal{O}(N \log N)$ priority queue insertions, leading to a second log factor.
•  » » » » 2 months ago, # ^ |   0 Excuse me, can I have a look at the code
•  » » » 2 months ago, # ^ |   0 Thanks!
 » 2 months ago, # |   +53 Will you make others' solutions visible?
•  » » 2 months ago, # ^ |   +26 and testcases
 » 2 months ago, # | ← Rev. 2 →   +36 Where can I upsolve the problems? Also, Is this the intended solution in M? (It passed) Spoilerint main() { int n; scanf("%lld",&n); for (int tc = 0; tc < n; tc++) { vector a(5); for (int i = 0 ; i < 5 ; i++) { scanf("%lld",&a[i]); hand[tc][i] = a[i]; } sort(all(a)); if (a[0] <= 3) strat[tc][0] = 1; else if(a[0] == 4) strat[tc][0] = 0.9, strat[tc][1] = 0.1; else if(a[0] <= 7) strat[tc][1] = 1; else if(a[0] == 8) strat[tc][1] = 0.9, strat[tc][0] = 0.1; else if(a[0] <= 13) strat[tc][2] = 1; else if(a[0] <= 19) strat[tc][3] = 1; else if(a[0] <= 29) strat[tc][4] = 1; for (int j = 0; j < 5; j++) { printf("%.01lf ",strat[tc][j]); } printf("\n"); fflush(stdout); } } 
•  » » 2 months ago, # ^ | ← Rev. 2 →   +8 In fact, only output 0 and 1 is enough to pass M. XD
•  » » » 2 months ago, # ^ |   0 How to find the proper 01 string ?
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   +10 I have used evolutionary algorithms and I got 86%: code#include #include #include #include #include #include #include #define rep(i, n) for (int i = 0; i < n; ++i) #define all(v) v.begin(), v.end() #define trav(e, v) for (auto e : v) #define pb push_back #define sz(v) ((int)v.size()) using namespace std; using vi = vector; using vvi = vector; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int random(int l, int r) { return uniform_int_distribution(l, r)(rng); } double prob() { return uniform_real_distribution(0, 1)(rng); } double comb(int n, int m) { if (n < m) return 0; double res = 1; for (int i = 0; i < m; ++i) { res *= n-i; res /= i+1; } return res; }; double get(int x, int y) { double temp = 0; for (int i = 0; i <= 4; ++i) { temp += comb(y-x-1, i) * comb(100-y, 8-i) * comb(8-i, 4-i); } return temp; } double func(vector x, bool ok = 0) { for (int i = 0; i < 5; ++i) { x[i] += x[i-1]; } if (ok) { rep(i, 5) cout << x[i] << " "; cout << endl; } auto f = [&](int t, vector &p) { if (t <= x[0]) p[0] = 1; else if (t <= x[1]) p[1] = 1; else if (t <= x[2]) p[2] = 1; else if (t <= x[3]) p[3] = 1; else if (t <= x[4]) p[4] = 1; }; double sum = 0.; double cnt = 0; for (int a = 1; a <= 100; ++a) { for (int b = a+1; b <= 100; ++b) { cnt += get(a, b); vector pra(6), prb(6); f(a, pra); f(b, prb); double temp = 0; for (int i = 0; i < 5; ++i) { temp += pra[i] * (1 - prb[i]); prb[i+1] += prb[i]; } sum += get(a, b) * temp; } } return sum * 100 / cnt; } const int CHROMOSOME_SIZE = 5; const int PCS = 1 << CHROMOSOME_SIZE; const int CHROMOSOME_N = 5; const float MUTATION_RATE = 0.10; const float CROSSOVER_RATE = 0.80; const int N_GENERATIONS = 1000; const int N_POPULATION = 40; //even vvi pop; vi new_individual() { vi individual(CHROMOSOME_N); trav(&x, individual) x = random(0, PCS - 1); return individual; } void crossover(vi &p, vi &q) { if (prob() > CROSSOVER_RATE) return; rep(i, CHROMOSOME_N) { int cut = random(0, PCS-1); int tp = p[i], tq = q[i]; p[i] = (tp & ~cut) | (tq & cut); q[i] = (tp & cut) | (tq & ~cut); } } void mutation(vvi &pop) { for (auto &p : pop) rep(i, CHROMOSOME_N) rep(j, CHROMOSOME_SIZE) if (prob() <= MUTATION_RATE) p[i] ^= 1 << j; } vector> B = {{1, 20}, {0, 20}, {0, 20}, {0, 20}, {0, 20}}; vector tics(vi p) { vector res(sz(p)); rep(i, sz(p)) res[i] = int((double)p[i] * (B[i][1] - B[i][0]) / PCS + B[i][0]); return res; } vector F(vvi pop) { vector res; trav(p, pop) res.push_back(func(tics(p))); return res; } const double eps = 1e-2; vvi select(vvi pop, vector fitness) { double min_fitness = *min_element(all(fitness)); for (auto &e : fitness) e -= min_fitness - eps; double sum = accumulate(all(fitness), (double)0.); for (auto &e : fitness) e /= sum; discrete_distribution distribution(all(fitness)); vvi res; rep(i, N_POPULATION) { int idx = distribution(rng); res.pb(pop[idx]); } return res; } int main() { rep(i, N_POPULATION) pop.pb(new_individual()); double ans = -1e18; vi p_best; while (ans < 90.001) { auto f = F(pop); int idx = max_element(all(f)) - f.begin(); if (ans < f[idx]) { ans = f[idx]; p_best = pop[idx]; cout << ans << endl; func(tics(p_best), 1); } pop = select(pop, f); for (int i = 0; i < N_POPULATION; i += 2) crossover(pop[i], pop[i + 1]); mutation(pop); } cout << setprecision(10) << fixed; cout << func(tics(p_best), 1) << endl; cout << ans << '\n'; return 0; } 
•  » » » » » 2 months ago, # ^ |   +10 these are the bins of some solutions: 4 9 14 19 29 4 9 15 21 31 3 7 12 19 31 4 8 13 21 32
 » 2 months ago, # |   0 How to solve H ?
 » 2 months ago, # |   +60 Will there are be a mirror of the ICPC WF on the 5th of October?
 » 2 months ago, # |   +13 How to solve B ?
•  » » 2 months ago, # ^ |   +10 Assume the ranges are $[l_i,r_i]$ where $l_i < r_i$. You can show that $[l_j,r_j]$ intersects this if ( $l_j \leq l_i$ and $l_i \leq r_j \leq r_i$ ) or ( $l_i \leq l_j \leq r_i$ and $r_i \leq r_j$ ).Now, we will draw these $[l_i,r_i]$ on the eucledian plane. We notice that those intervals that intersects $[l_i,r_i]$ actually form 2 rectangles on this plane. So we can just maintain some 2d data structure. Since one side of the rectangles extend to infinity, we can use a priority queue as one of the layers of this 2d data structure.code
 » 2 months ago, # |   0 H was so frustrating :( Tried doing it recursively but broke my own record of wrong submissions
 » 2 months ago, # |   +31 When the practice submission will be allowed?
 » 2 months ago, # | ← Rev. 2 →   +10 has someone solved L with offline queries of searching the narrowest edge on a path in mst? my approach with sqrt-decomposition is getting wa3 and I don't know whether it's bug or solution is wrong
 » 2 months ago, # |   +21 It is so funny that my team's solution for K is the fastest. We just did $N=61$ maximum independent set and copied the fastest solution for MIS from yosupo's judge. Surpringly, it ACs.code
 » 2 months ago, # | ← Rev. 2 →   +21 How to solve G?+Is there a scoreboard for official WF Invitational Contest?
•  » » 2 months ago, # ^ | ← Rev. 2 →   +10 It is still frozen. It should be revealed on October 5th as far as I understand.
•  » » 2 months ago, # ^ | ← Rev. 3 →   +36 For each subtree $x$ and for each leave $v$ in $x$, we want to compute the probability of $v$ to be the winner in that subtree. To do so, we simply need to merge two subtrees, which turns the problem into computing ($\sum_i \frac{b_i x_j}{y_i+x_j}$) for every $j$. For the part $y_i>x_j$, we divide the denominator and numerator both by $y_i$ (now $0<\frac{x_j}{y_i}<1$), then use the Taylor series of $1/(1+x)$ around $1/2$. For the part $y_i •  » » 2 months ago, # ^ | +18 Here is the official scoreboard :) •  » » 2 months ago, # ^ | 0 We updated the editorial with the editorial of G.Thanks for participating!  » 2 months ago, # | +95 A dragon curve related problem :PA2011 5A szlProblem D is much easier than this PA problem. Since you only need to locate the point here. During the contest, I just found the code I wrote about 10 years ago and passed.BTW, in this PA problem, you need to answer the number of consecutive lines in a strip. I tried hard and didn't solve it when I was young. And I didn't have another try these years, so I still don't know how to solve it yet.If anyone knows the solution to this problem, please let me know. Thanks. •  » » 2 months ago, # ^ | +20 I love how easily you said " I just found the code I wrote about 10 years ago and passed"I can't even find my code from last month.  » 2 months ago, # | +28 Sorry to ask, but is there any access to virtual participation?  » 2 months ago, # | +23 How to solve problem I(Interactive Rays)? •  » » 2 months ago, # ^ | ← Rev. 3 → +8 First we can rotate the plane to make sure the center is above the x-axis and the circle doesn't cross the third quadrant. Next I use binary search to find two rays$a:(0,0)\to (x_1,y_1)$and$b:(0,0)\to (x_2,y_2)$that are almost tangential to the circle.Then I enumerate all possible radius$r$（$r$is an integer not greater than$10^5$so it's ok to do so）。With the distance between$a$and the circle (let's call it$d_1$) and it's radius$r$we can work out the coordinate of the center$(x,y)$(with some senior high school geometry). I also make sure that$(x_1,y_1)$lies in the second quadrant and is as close to the circle as possible (so if the circle doesn't cross the second quadrant, what I will get is$x_1=-1$and$y_1=10^5$). Because of the constraints above (the bolded part) we can see that$d_1$is always useful information (which means that$d_1$is not$\mathrm{distance}((x,y),(0,0))-r$, this infomation is useless because it's too easy to get and we can't fix$(x,y)$simply with$r$and$\mathrm{distance}((x,y),(0,0))-r$: we need more infomation :$d_1$) pictureAfter fixing$(x,y)$we have the whole circle, so we can calculate the distance between the circle and$b$, and check whether it is equal to what the interactor outputs. If yes, then$(x,y,r)\$ is the answer, otherwise go through other radii until we find out the answer. the code#include #define db double #define ll long long #define ld long double #define ull unsigned long long #define vint vector #define vpii vector #define pii pair #define fi first #define se second #define pb emplace_back #define mem(x,v,s) memset(x,v,sizeof(x[0])*(s)) #define cpy(x,y,s) memcpy(x,y,sizeof(x[0])*(s)) inline int read(){ int x=0; char s=getchar(); while(!isdigit(s))s=getchar(); while(isdigit(s))x=x*10+s-'0',s=getchar(); return x; } const ld eps=1e-6; const ll N=2e5; ld max(ld x,ld y){return x>y?x:y;} ld min(ld x,ld y){return x>res; return res; } void answ(int x,int y,int r){ for(int j=1;j<=swp;j++)ref(x,y); std::cout<<"! "<>1; xx=-min(N,m),yy=N-max(0,m-N); (res=query(xx,yy))>1e-6?r=m:l=m+1; } xx=-min(N,l),yy=N-max(0,l-N); ld upl=query(tx,ty); ref(tx,ty),ref(tx,ty); ld downr=query(tx,ty),mdis=std::min(upl,downr); int xx2,yy2; l=1,r=N*3-1; while(l>1)+1; xx2=min(N,m),yy2=-N+max(0ll,m-N); (res=query(xx2,yy2)>1e-6)?l=m:r=m-1; } xx2=min(N,l),yy2=-N+max(0,l-N),res=query(xx2,yy2); for(int r=1;r<=1e5;r++){ ld y=mdis+r,x=sqrt((down+r)*(down+r)-y*y); ll d=1ll*xx*xx+1ll*yy+yy; ld sn=(ld)fabs(yy)/(ld)(sqrt(d)); // rotate the plane by some angle ld cs=(ld)fabs(xx)/(ld)(sqrt(d)); if(Eq(mdis,upl))x=-x; ld x0=x*cs+y*sn,y0=-x*sn+y*cs; x=x0,y=y0; if(Eq(res,dis(xx2,yy2,x,y,r)))answer(x,y,r); } return 0; } (I'm a Chinese student, sorry for my poor English.) I spent four hours on the problem (from 9:30 p.m. to 1:30 a.m!) so I don't have time to help my teammates lol
 » 2 months ago, # |   0 I am a beginner but I liked the problems very much — my attempt at problem B using DSU exceeds time limit on test case 15, can anybody suggest possible improvements? Code #include using namespace std; #define FOR(i, a, b) for(int i = (a); i < (b); i++) int main(){ int n, m; cin >> n >> m; struct DSU{ vector e; DSU(int N) {e = vector(N, -1);} int find(int a) {return (e[a] < 0)? a : e[a] = find(e[a]);} bool same_set(int a, int b) {return find(a) == find(b);} void merge(int a, int b){ int x = find(a), y = find(b); if(x == y) return; if(e[x] < e[y]) swap(x, y); e[x] += e[y]; e[y] = x; } }; string str = ""; DSU dsu(n); vector> adj(n); FOR(i, 0, m){ int e, v, u; cin >> e >> v >> u; v--; u--; if(e == 1){ if(v > u) swap(u, v); adj[v].push_back(u); adj[u].push_back(v); dsu.merge(v, u); //check which previous chords (j, z) intersect (v, u) and do dsu.merge(v, j) if(u - v < n - (u - v)){ FOR(j, v + 1, u){ for(auto z: adj[j]){ if(!(v < z && z < u)){ dsu.merge(v, j); break; } } } } else{ FOR(j, (u + 1)%n, n){ for(auto z: adj[j]){ if(v <= z && z <= u){ dsu.merge(v, j); break; } } } FOR(j, 0, v){ for(auto z: adj[j]){ if(v <= z && z <= u){ dsu.merge(v, j); break; } } } } } else if(e == 2){ bool ans = dsu.same_set(v, u); str += (ans)? '1' : '0'; } } cout << str; } 
 » 2 months ago, # | ← Rev. 4 →   +22 I almost solved M... I got like 99% of the way to an accepted solution... but couldn't make the final leap. I wasted 3 HOURS faffing about like an idiot. SpoilerI was only dividing my interval into 5 equal segments, when the editorial claims the task is solvable with 6.I even made the "it's better to never play your card if it's too big" insight, but instead of creating a sixth segment, I just split my fifth segment in two. Why the heck did I do that??I want to scream. I feel like a tremendous idiot. I think this will haunt me for the rest of my life...
•  » » 2 months ago, # ^ |   0 exactly the same xD
•  » » 2 months ago, # ^ |   -10 sameeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee
 » 2 months ago, # |   -18 Can the editorial be opened without Google?
•  » » 2 months ago, # ^ |   0 We will put the editorial to code forces at some point.
•  » » 2 months ago, # ^ |   +12 Now, it is published at codeforces.
 » 2 months ago, # |   +5 How to solve A?
 » 2 months ago, # |   +16 I have a question regarding the editorial for problem B. Otherwise, we are joining two components on the same depth. Let’s say A is to the left of B (so, R(A) < L(B)). There can be at most one component between them, which is on a smaller level. In this case, 3 and 6 have the same depth 2 but there are 2 components between them (14 and 58). Did I misunderstand something?
•  » » 2 months ago, # ^ |   +10 Well, seams there is bug in editorial. I'll try to fix it later,In fact, In that case, we can just join both of them with parent, and it's correct (solution do like that). Probably I was thinking this parent is same for them, but than find it's wrong during stressing, but forgot about it again, when writing editorial. Anyway, it will become same at some point, and they would be merged, and total number of merges still small. You can check my solution for details
•  » » » 2 months ago, # ^ |   0 Thanks for clarifying!
 » 2 months ago, # |   0 Anyone know the members of Peking University team? Peking U (Wang, Yang, Guo)
 » 2 months ago, # |   +26 Can you change settings to display (failed) tests after the contest? Like in any CF round. I still can't fix my WA on test 102 in 1578I - Interactive Rays.
 » 2 months ago, # | ← Rev. 2 →   0 could anyone help me with problem E please, I,ve written a code but I get TLE on test 3, this is my code: #include using namespace std; int main(){ int TC; cin>>TC; while(TC--){ int h, p, rem = 0; long long n, ans = 0; cin>>h>>p; int i = 0; while(i < h){ n = pow(2, i); if(n <= p){ ans++; } else{ n -= rem%p; ans += n/p; rem = p - n%p; if(n%p) ans++; } i++; } cout<
•  » » 2 months ago, # ^ |   0 First, you can replace pow(2, i) with a bitwise shift operation: 1 << i. Second, you don't have to go through each value of i. I hope this helps.