Sir, I had seen live cast of ICPC world final which was casting SecondThread & ecnerwala . I am a man in bangladesh. Bangladesh is host for arranging the icpc world final 2022 as first time. I am so proud for this reason. Thank you so much all the members of icpc officials. #icpcwfdhaka

OMG, you are so crazy

Thank you. I was too lazy to find the appropriate word.

Isn't that equivalent to L: swap space from ICPC World Finals 2016? Looks exactly the same modulo a different story

a slightly harder version from PTZ-2009

Thank you! And thanks for the great website!

The point is, my prior knowledge of this problem reduced the time I needed to solve G to one (1) minute.

You only need log100 checks

Yeah, TL seems stupid. A lot of teams report TL -> AC with $$$O(NQ)$$$

Thanks for the answer. However, I'll just claim that I highly dislike the problems in which you have no idea whether your proposed complexity will pass or not (one might say that's a part of CP tho).

In case that you wanted to time out NQ and wanted to allow poly(N) + QlogN, can you kindly tell us what was the reasoning between not setting Q higher (1e6 order)? Thanks.

I looked at the constraints, thought "nq looks like it should pass", did not optimize anything and got AC with my first submit ¯\_(ツ)_/¯

If you wanted to time out nq at least make the constraints so that it looks like it shouldn't pass. I was convinced I wrote intended solution instead of thinking I cheated my way through with some optimized bruteforce

Have you thought about just precalculating all possible lcas in O(n^2) :p?

They updated it now, thx

I bet jiangly next year :)D

UPD: It will not pass time limit

Alternative solution for problem $$$G$$$ with $$$z-function$$$ $$$(z-algorithm)$$$.

Let's mosaic has $$$n$$$ rows and $$$m$$$ columns, and motif $$$n1$$$ rows, $$$m1$$$ columns. Let's make one-dimension array $$$a$$$ of size $$$n*m$$$ from mosaic concatenating it's rows and $$$c$$$ one-dimension array of size $$$n1*m$$$ from motif concatenating it's rows extended with $$$m-m1$$$ $$$0$$$. Now we need to find where $$$c$$$ is a substring of $$$a$$$ assuming $$$0$$$ can be any symbol — we can do it using slightly modified z-function.

the only change will be in $$$while$$$ condition.

s[z[i]] == s[i + z[i]] to s[z[i]] == 0 || s[z[i]] == s[i + z[i]]

the full while (you can compare it to e-maxx code, which i took to modify):

while (i + z[i] < n && (s[z[i]] == 0 || s[z[i]] == s[i + z[i]])) ++z[i];

I have made some tests and it works. Correct me please, if it is wrong.

For problem D, the guard first moves between the starting point and the vertices of the polygon and then heads to a location where half of the target can be seen.

In the first part, it needs to check whether the segment connecting two points is fully inside the polygon (Airport Construction helps), and find the shortest path from the starting point to each of the vertices.

In the second part, if the starting point or the vertices of the polygon can see the target, no more moves are needed from that point. Otherwise, it needs to straightly move to the closest point on the boundary of the target region, which consists of $$$O(n)$$$ segments. Some of the segments are on the boundary of the polygon and it is no need to consider such segments, and each of the others is on the ray from the target heading to a vertex of the polygon, which may be considered as connecting the target and the farthest intersection between each edge and the ray that can see the target. Checking whether a point can see the target is straightforward based on checking the segment inside the polygon. Don't forget to check whether the "straightly move" is fully inside the polygon.

The total complexity is $$$O(n^3)$$$, $$$O(n^3\log{n})$$$, or even $$$O(n^4)$$$, based on the complexity of checking whether each of the $$$O(n^2)$$$ segments is fully inside the polygon. The precision issue is just metaphysical. I have used long double for calculation, tried several values of $$$\epsilon$$$ (precision tolerance), and somehow made it pass.

For problem K, based on the strange(?) constraints, it turns out that the conclusion that the maximum size of the convex hull in $$$[-D, D]$$$ is $$$O(D^{2/3})$$$ helps in my analysis.

For each non-leaf tree node $$$u$$$, denoting the number of children of $$$u$$$ by $$$a_u$$$ and the number of leaves in the subtree of $$$u$$$ by $$$b_u$$$, we have $$$1 \le a_u \le 100$$$ and $$$\sum a_u \le n$$$, and $$$\sum b_u \le 10 \cdot n$$$ since the height of the tree is no more than $$$10$$$.

The range of coordinates in the convex hull of $$$u$$$ is $$$[-1\,000 \cdot b_u, 1\,000 \cdot b_u]$$$, then the "cost" of calculating some Minkowski sums and then take convex hulls of their unions for a non-leaf tree node $$$u$$$ is about $$$a_u \log_2{a_u} (1\,000 \cdot b_u)^{2/3}$$$.

A rough estimate of the maximum total "cost" is about $$$6.644 \times 10^8$$$ when $$$n=10\,000$$$ and $$$100$$$ of $$$a_u$$$ reach $$$100$$$ and the corresponding $$$b_u$$$ reach $$$1\,000$$$. Since the variables about the structure of the tree and the size of the convex hull on each tree node can hardly reach the maximum generally, I think even the order is overestimated.

I wonder if it is possible to analyze the total "cost" in a more precise way or without the range of the coordinates.

For problem H, what does "rotate all other strings by 180 degrees" mean exactly?

we did naive iteration (with vectors) for L. Now that I think about this, you could precompute the time needed to move $$$(dx, dy)$$$. This gives a simple $$$O(nmklogk)$$$ solution if you use sorting and $$$O(nmk)$$$ if you use bucketing.

Does have any discussion regarding to solution for problem E?

Yeah, I literally read my code 10 times and was so convinced that there can be nothing wrong. Even when my teammates, after a long debugging, told me that might be the problems, I first refused to believe as I don't know, they are consecutive. Of course, any stress tests that I have written aligned with my understanding of the task.

[My opinion only, as this is my first and last WF]: It's such a shame that literally places 8-30 or similar are majorly influenced by how much time you spent debugging J regarding this awfully written piece of description + deciding whether to go or not with O(QN) in B. A competition this prestigious should not be decided on this vague and semi-random behaviour -- why don't you just put that in the samples? Insane.

Yes, I fully agree that we should have handled it better. However, regarding the it is important to NOT let him know anything about this problem, what my first thought after getting a WA on a problem that I'm convinced it should pass is to ask my teammates to sanity-check my idea and take a look at my code for some silly mistakes.

I guess, given the difficulty of the problem, that probably the best way to deal with it is to ask to reimplement from zero. Thanks for the advice.

Bumping this with hope.

Thx!