By DeadlyPillow, history, 2 months ago,

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:

Announcement of JCPC 2022

• +118

 » 2 months ago, # | ← Rev. 4 →   +2 When will the editorial be released? If not, how to solve D, E, H, J?
•  » » 2 months ago, # ^ |   +23 Problem DLet 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. Problem ELet'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! Problem HOoooh 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. Problem JThis 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. Can we make exactly 1100101100 using the basis? If yes, that's the answer! If not, let's lower our expectations. Can we make 11001010xx using 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. If we still can't make any numbers, then lower our expectations again, and try making 1100100xxx Then 11000xxxxx Then 10xxxxxxxx Then 0xxxxxxxxx If 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.
•  » » » 2 months ago, # ^ |   0 Any idea for problem I?
•  » » » » 2 months ago, # ^ |   +11 Really fun problem!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!
•  » » » » » 7 weeks ago, # ^ |   0 Any idea for problem G please
•  » » » » » » 7 weeks ago, # ^ | ← Rev. 3 →   0 SpoilerFor question (u, v) we have 2 cases (u >= v) or (u < v).Let maxVal is max_element in A. If u <= v you just need to check v not bigger than max_element in A, because initially Omda is standing on point 0. If u > v, for let b[A[i]] is the smallest A[j] (j >= i) for any A[i] and check if exist any value from b[u] -> b[maxVal] which smaller or equal v.
•  » » » » » » » 7 weeks ago, # ^ |   0 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 ideaare you sure that the idea was right or it's the first hint of the problem
•  » » » » » » » » 7 weeks ago, # ^ |   0 Sorry I got confused between u >= v and u < v, I corrected the above.
 » 2 months ago, # |   +10 So how to solve C...?
•  » » 2 months ago, # ^ | ← Rev. 2 →   +10 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 graphDo the same for all other i nodes from 2 to $N$.Complexity $O(N^2)$
•  » » » 2 months ago, # ^ |   +10 Isn't this $O(N^3)$? (One iteration of Kuhn is $O(N^2)$)
•  » » » » 2 months ago, # ^ |   -10 Well yes but no, it's $O(N^3)$ per say but under given constraints it should pass easily.
•  » » 2 months ago, # ^ |   +10 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?