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.

Will we get certificate of participation???

In the mirror you will not recieve any certificates, unfortunately.

For the first time ICPC WF problems will get CF ratings (in problem-set page).

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...

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.

Problems are cool, recommend to participate, but if you are not div1, it will be too hard and sad for you.

Can anyone tell the maximum team size please? Thanks ;_;

Three people.

Thank you

what does it mean?I think Codeforces can find(guess) that they are dangerous teams.

i.e. cheaters? I checked one team, no cheaters are there

I think it means that someone of that team is already in another team

oh, nice, thank you

Anyone wants to team up with me ?

Where can I find the live leaderboard of ICPC WF?

It is not World Finals! It is World Finals Invitational.

Oh, my bad, didn't read the blog properly

How to solve L ?

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

Thanks!

Can you explain how mx changes when we combine 2 sets U and V?

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.

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.

Wow. Why weren't we able to think this in contest... This now makes a lot more sense. Thanks.

Why log^2? Isn't it just single log?

In the worst case, my solution performs $$$\mathcal{O}(N \log N)$$$ priority queue insertions, leading to a second log factor.

Excuse me, can I have a look at the code

Thanks!

Will you make others' solutions visible?

and testcases

Where can I upsolve the problems?

Also, Is this the intended solution in M? (It passed)

SpoilerIn fact, only output 0 and 1 is enough to pass M. XD

How to find the proper 01 string ?

I have used evolutionary algorithms and I got 86%:

codethese are the bins of some solutions:

How to solve H ?

Pair up brackets using a stack and build such tree:

SpoilerNote: 0 is root there.

How can it be done? When you meet '(', add its ID to stack, When you meet ')' pop the top of the stack and add this ID to its parent. When you meet '-' just ignore it and the next character.

Now let's write recursive function int get_order(int ID). It works lazily. If order is already computed return it. Otherwise if there are no children of this vertex then the order is $$$0$$$. Otherwise let's merge all the children into parent's order.

The answer is get_order(0).

Code: 130485662

CodeI'm sorry, I accidentally pressed the wrong.Actually ,I want to click the other.Your answer give me a great help.

Will there are be a mirror of the ICPC WF on the 5th of October?

How to solve B ?

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

H was so frustrating :( Tried doing it recursively but broke my own record of wrong submissions

When the practice submission will be allowed?

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

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

How to solve G?

+Is there a scoreboard for official WF Invitational Contest?

It is still frozen. It should be revealed on October 5th as far as I understand.

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<x_j$$$, we could divide denominator and numerator both by $$$x_j$$$ and do similarly.

Here is the official scoreboard :)

We updated the editorial with the editorial of G.

Thanks for participating!

A dragon curve related problem :PA2011 5A szl

Problem 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.

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.

Sorry to ask, but is there any access to virtual participation?

How to solve problem I(Interactive Rays)?

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(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

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?

CodeI 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...

exactly the same xD

sameeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee

Can the editorial be opened without Google?

We will put the editorial to code forces at some point.

Now, it is published at codeforces.

How to solve A?

I have a question regarding the editorial for problem B.

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?

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

Thanks for clarifying!

Anyone know the members of Peking University team? Peking U (Wang, Yang, Guo)

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.

could anyone help me with problem E please, I,ve written a code but I get TLE on test 3, this is my code:

thnx in advance.

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.