Please fix the team for Asia Pacific, Vietnam, University of Science, VNU-HCM: Monarchuwu, SaoST, VHTung

My team goes to WF23, not WF22

Asia Pacific, Vietnam, University of Science, VNU-HCM: Yurushia, vinfat, hieplpvip

My bad. I didn't fully understand your comment so I wrote my own. Just reread yours and it's much clearer now.

I think the author meant we can always find $$$\left\lceil \frac{n}{k - 1} \right\rceil$$$ intervals with their right endpoints inside $$$[x_{i,j}, x_{i,j+1}]$$$. If it were not the case, at the time we considered $$$[x_{i,j}, x_{i,j+1}]$$$, we would have selected it.

Now for each of the $$$k-1$$$ intervals for color $$$i$$$, we have $$$\left\lceil \frac{n}{k - 1} \right\rceil$$$ distinct intervals. In total, we have $$$(k - 1)\left\lceil \frac{n}{k - 1} \right\rceil \ge n$$$ distinct intervals, leading to a contradiction since we can not have $$$n$$$ intervals for $$$n-1$$$ colors.

He was asking why $$$[x_{i,j}, x_{i,j+1}]$$$ must have been selected if it comes before $$$[a, b]$$$.

Can someone explain the intuition behind solution 1 of Div1 C? I don't know how to come up with that implicit graph.

The best implementation I know is that of Andrey Lopatin. It is surprisingly short and works with negative weights. You can find it on e-maxx: http://e-maxx.ru/algo/assignment_hungary#6

There is an English translation here: http://zafar.cc/2017/7/19/hungarian-algorithm/

Could someone explain problem Two Stacks Sorting? I can't understand its statement.

I think this one should be added too: Geometry shrink trick

2x-y is the reflection of y w.r.t x. You can do the following to get all multiple of x:

• Reflect 0 w.r.t to x and get 2x

• Reflect x w.r.t to 2x and get 3x

• Reflect 2x w.r.t 3x and get 4x

and so on

You don't need to created two version for maximum and minimum.

You can query minimum value from a maximum LiChao tree by adding line (-a, -b) instead of (a, b), and getting -query(x) instead of query(x). This applies to convex hull too.

The first returns an iterator to the k-th largest element (counting from zero)

Shouldn't it be the k-th smallest element? adamant

For me E is much easier than D, F or G... I stuck at D for 50mins, but I solved E in just 10mins.

Can you give me some hints on G?

Thank you! I didn't realize it until now.

Refer to problem C in this resource. It provides a O(n*m) $$$O(n^{3})$$$ algorithm for MDST on weighted graphs.

Similar problem on Codeforces: 266D — BerDonalds. Here is my implementation in C++: 72562015

Here how I solved Div 1 B - Aerodynamic (Div 2 D) in contest:

Step 1: Use GeoGebra to plot test 3 and realized that the opposite sides are parallel.

Step 2: Go back to the statement and realized that it's also true for test 1.

Step 3: "Coincidence? Nah, I don't think so. Let's code it"

My submission: 70663347.

I still don't know how to prove it. Could someone help me?

My submission using binary search: 67564167. Not sure if my idea is the same as those above.

My idea is to sort the goods by their prices, then fix the number of goods that we have to buy separately (obviously, it's in range $$$[0,k-1]$$$), and finally using binary search to find the number of group of k goods that we can buy.

If the numbers of good that we buy separately is i, it's optimal to buy the first i goods.

Overall complexity should be $$$O((n+k)logn)$$$.

Solution for F is so beautiful...

C++ submission

Could someone give me advice on how to solve problem G ?

EDIT: Solved using segment tree

Let's consider only the case when one point is at $$$(0,0)$$$. For other cases, you can always move to this case (by shifting the points).

We'll build a rectangle inside the rectangle $$$n \times m$$$, with area equal to $$$2*m*n/k$$$, and we'll split the rectangle to get the triangle.

• When $$$k$$$ is even ($$$k=2t$$$), we need to build a rectanble with area $$$m*n/t$$$. This number must be an integer, so $$$m*n$$$ must be divisible by t. This leads to the solution in the editorial. $$$g = gcd(t,n)$$$; $$$n = a * g$$$; $$$m = b * g'$$$ with $$$g' = t/g$$$ and $$$a,b$$$ is the sides of the rectangle

• When $$$k$$$ is odd, $$$m*n$$$ must be divisible by $$$k$$$. Similarly, we have: $$$g = gcd(k,n)$$$; $$$n = a * g$$$; $$$m = b * g'$$$ with $$$g' = k/g$$$. Note that at this time, $$$a$$$ and $$$b$$$ is the sides of the rectangle with area $$$n*m/k$$$. We need to double one side to get the desired rectangle.

If $$$a \lt n \rightarrow g \geq 3$$$ (because $$$g$$$ is neither 1 nor even) $$$\rightarrow a \leq n/3 \rightarrow 2a \lt n$$$

If $$$a = n \rightarrow g = 1 \rightarrow g' = k \geq 3$$$ (note that $$$k$$$ is odd). Similarly, we get $$$2b \lt m$$$

So we can always double $$$a$$$ or $$$b$$$.

Can you explain your code?

Could somebody explain this code? https://mirror.codeforces.com/contest/1200/submission/58594933

Where is the author's code for problem F???