Hey everyone!
I'd like to invite you to participate in the JCPC 2022 contest on the gym on Jan/22/2023 13:00 (Moscow time)
The problems were created by me (Yes only me).
I'd like to thank IsaacMoris and El-Ged_Sevawy for helping me prepare the contest and also mahmoudbadawy for helping (can't remember what he did thou).
Also onsite participants might note that statements changed that's because someone I don't like changed my statements for the onsite contest so I decided to publish the original statements here.
Btw spoiler for the contest theme:
When will the editorial be released? If not, how to solve D, E, H, J?
Let the number of chips be $$$N$$$.
(I know, it's $$$N*K$$$, but bear with me).
If $$$K$$$ is odd, then the parity of chip count always change. You can work out the rest.
If $$$K$$$ is even, there is a pattern that takes shape once you write it down. E.g. for $$$K = 6$$$, the pattern is $$$LWLWLWW$$$ for $$$N = 0$$$ to $$$6$$$, repeats from $$$7$$$ to $$$13$$$, so on for every $$$7$$$ chips.
Let's solve the problem for each point in $$$O(N)$$$ or $$$O(NlogN)$$$ or something like that.
Suppose we want point $$$(0, 0)$$$ to be in the convex hull.
Then the condition is that there cannot be a point that lies on both sides of a green straight line passing through that point.
The idea goes like this: Sort the points by angle. Then do a two-pointer/binary search something to find the maximum number of points in any 180-degree interval.
It's fun to work out how to implement this, give this a try!
Ooooh this one is really good!
Now obviously if the distance is odd, then answer is $$$0$$$. With that outta the way....
Sample tree 1:
If the two green nodes are the query nodes, and the red node is their LCA/midpoint, then anything in the orange direction/subtree are bad. Everything else in the tree is good!
Sample tree 2:
If their midpoint is not the LCA, then you can find the midpoint by lifting the lower node up by dist/2. Then the two orange directions are bad, but everything else is good!
So it's a matter of subtree sizes and which part of the tree is good, which is bad.
This one is really difficult! You have to know xor basis to solve this problem, don't solve this if you haven't learned it yet.
Let's just turn all the cards side-up first. If we flip a card, then we actually xor-ed it by $$$A_i \oplus B_i$$$. So first let's build a basis on all of $$$A_i \oplus B_i$$$.
Let's take some random value $$$K$$$ and use a demonstration. Suppose $$$K = 1100101100$$$ in binary.
1100101100using the basis? If yes, that's the answer!11001010xxusing the basis? This is lower than $$$K$$$, we switched up the last $$$1$$$-bit, but the last two bits can now be anything. Try to make the x-s as large as possible.1100100xxx11000xxxxx10xxxxxxxx0xxxxxxxxxIf we ever find a number, that's our answer! Otherwise we have to output 0.
So that's the main idea. Try to construct a prefix of $$$K$$$ as much as possible, then for the rest, make it as large as possible.
Any idea for problem I?
Since $$$N * M \leq 500$$$, at least one of $$$N$$$ or $$$M$$$ must be smaller than or equal to $$$22$$$.
Brute force on the smaller side, then greedy on the other!
Any idea for problem G please
For question (u, v) we have 2 cases (u >= v) or (u < v).
Let maxVal is max_element in A.
but in the example we can see that - with u = 7 and v = 1, the output is "No" even though v <= maxVal, which was 10 in the initial array - with u = 6 and v = 3 the output is "Yes" since it matchs your idea
are you sure that the idea was right or it's the first hint of the problem
Sorry I got confused between u >= v and u < v, I corrected the above.
So how to solve C...?
Get any maximum matching for the graph then remove edge(1,match[1]) and run try_khun(1) on the rest of the nodes after that remove nodes 1 and new_match[1] from the graph
Do the same for all other i nodes from 2 to $$$N$$$.
Complexity $$$O(N^2)$$$
Isn't this $$$O(N^3)$$$? (One iteration of Kuhn is $$$O(N^2)$$$)
Well yes but no, it's $$$O(N^3)$$$ per say but under given constraints it should pass easily.
The problem asks for the lexicographically minimal perfect matching in a bipartite graph. Let's solve it in $$$O(N M)$$$, where $$$M$$$ is the number of edges in our graph (in our problem, $$$M = O(N^2)$$$.
First, find any matching. Denote the corresponding mate for vertex $$$i$$$ in the left side as $$$L(i)$$$ and the corresponding mate for vertex $$$i$$$ in the right side as $$$R(i)$$$. We will iteratively adapt this matching to be lexicographically minimal.
Let's consider vertex $$$i$$$ (in order from $$$1$$$ to $$$N$$$) and its match, $$$L(i)$$$. Let's suppose we want to match $$$i$$$ with some $$$j$$$. One correct approach would be to first unmatch $$$(i, L(i))$$$ and $$$(R(j), j)$$$, forcefully match $$$(i, j)$$$ and run one iteration of Kuhn's algorithm to match $$$R(j)$$$ without visiting $$$i$$$ in the left side; however, this would be too slow ($$$O(N^2 M)$$$), as we have to do this $$$O(N^2)$$$ times.
However, as stated above, we can match $$$i$$$ with $$$j$$$ if and only if there is an alternating path from $$$L(i)$$$ to $$$R(j)$$$ without visiting vertices $$$1, 2, \ldots, i$$$ in the left side. Then, for a given $$$i$$$, we can run a simple DFS starting from $$$L(i)$$$ to find all reachable vertices on the right hand side via an alternating path (starting with an unmatched edge). Notice that this is done on the transpose of the original graph, as non-matching edges flow from right to left and matching edges now flow from left to right. Then, we can connect $$$i$$$ with the minimum (yet-unassigned) $$$j$$$ such that there is an edge $$$(i, j)$$$ and $$$j$$$ is marked as reachable.
Complexity is $$$O(N M) = O(N^3)$$$.
Can it be done faster/easier?