We will hold UNICORN Programming Contest 2021(AtCoder Beginner Contest 225).
- Contest URL: https://atcoder.jp/contests/abc225
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20211030T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: Nyaan, penguinman, physics0523, sugarrr
- Tester: Kodaman, blackyuki
- Rated range: ~ 1999
The point values will be 100-200-300-400-500-500-600-600.
We are looking forward to your participation!
Codeforces Problem C
Got this Problem at tha last moment of Contest. i think it can help for problem F
Yup. That plus dynamic programming $$$dp_{i, k}$$$ where the states represent the possible lexicographically minimum string from choosing k strings from $$$a_i...a_n$$$ got me an AC.
The problem you mentioned is on GFG as well, but the exact solution dosen't work as stated in the editorial. The editorial of problem F is quite descriptive, listed out quite a few incorrect solutions :)
Hints for E? No editorial published for it.
That's basically just https://www.geeksforgeeks.org/minimum-removals-required-to-make-ranges-non-overlapping/
With the use of exact rational numbers (pairs of numerator and denominator) instead of ints. Floating points arithmetics may be not accurate enough. My submission: https://atcoder.jp/contests/abc225/submissions/26926488
I'm wondering why double gets WA and long double gets AC in problem E. Did anyone encounter the same case as I did?
I found the angles for each pair of (x,y-1) (x-1,y) and treated them as segments. Then I used greedy to find the max number of non overlapping segments.
There's good discussion on how to polar sort properly in https://codeforces.net/blog/entry/72815
For this problem, since all points were in the first quadrant, you can even think of it as sorting fractional slopes which had some short submissions in python: https://atcoder.jp/contests/abc225/submissions/26905587
Any hints for problem G? Thanks a lot.
Draw the lines from top to bottom ,and solve a min-cut problem to choose whether a grid is placed a "x".
The score is equal to the sum of $$$A[i][j]-2*C$$$ over all marked square $$$(i, j)$$$ plus $$$C$$$ times the number of pairs of marked squares whose center have distance $$$\sqrt{2}$$$.
Do max flow
Let $$$INF$$$ be some large constant.
Model flow network like this.
We have a node for each square, plus two additional nodes corresponding to source and sink.
For each pair of squares with distance $$$\sqrt{2}$$$, add an undirected edge of capacity $$$C$$$.
For each node $$$(i, j)$$$, add a directed edge $$$source \rightarrow (i, j)$$$ with capacity $$$INF$$$.
For each node $$$(i, j)$$$, add a directed edge $$$(i, j) \rightarrow sink$$$ with capacity $$$INF - deg((i, j))*C - 2*(A[i][j]-2*C)$$$, where $$$deg((i, j))$$$ is the number of squares whose distance to $$$(i, j)$$$ is $$$\sqrt2$$$
The answer is $$$(H * W * INF - (MaxFlow)) / 2$$$. Try to prove yourself why this works.
I don't get it. Why/how does this work?
Consider a $$$source$$$-$$$sink$$$ cut $$$(S, T)$$$. Let $$$U = S - \lbrace source \rbrace $$$ and $$$V = T - \lbrace sink \rbrace$$$. Also we'll denote the weight of an $$$u$$$-$$$v$$$ edge by $$$w(u,v)$$$(it is 0 if no such edge exists). Now the weight of the cut is
Note that
equals the number of edges whose both endpoints lie in $$$U$$$ times 2. Therefore, the last term is the score we'd get, multiplied by 2, if we were to pick $$$U$$$ as the answer. Since we want to maximize it, our goal turns into finding minimum weight $$$source$$$-$$$sink$$$ cut, which is equal to the maximum flow.
This is the construction I learned from the solution to the "maximum density subset problem". You might be able to find some resources on it if you google.
Here's another way to explain the same solution:
Let $$$\omega$$$ be a transfinite value, such that for integers $$$a, b, c, d,$$$ $$$a \omega + b > c \omega + d \Leftrightarrow a > c \vee (a = c \wedge b > d)$$$
(in other words, these numbers compare as lexicographic tuples $$$(a, b)$$$. In practice, $$$\omega$$$ can be represented with a constant large enough to dominate lesser values, but small enough not to overflow a machine integer type, e.g. $$$2^{48}$$$.)
The flow network should have:
The final answer is equal to $$$\large \frac{H \cdot W \cdot \omega - maxFlow} 2$$$.
Explanation: Let a cut be a partition of vertices in the network into sets $$$S$$$ and $$$T$$$, such that $$$s \in S$$$, $$$t \in T$$$. Let the cost of the cut be the sum of the capacity of edges going from vertices $$$u \in S$$$ to $$$v \in T$$$. By the max-flow-min-cut theorem, the minimum cost of a cut is equal to the maximum flow.
We wish to build the network in such a way such that $$$(i, j) \in S$$$ represents marking an X in that cell.
First, let's ignore the $$$(4 - deg(i, j)) \cdot C$$$ terms in the sink-edges. If $$$(i, j) \in S$$$, that means that if we followed the $$$C$$$-capacity edges until we reach a cell that's $$$\in T$$$, we cut the edge just before it. (Let's ignore the case where we reach the edge of the grid for now.) Also, we cut the edge from $$$(i, j)$$$ to $$$t$$$, Thus the cost of the cut is $$$2\cdot C$$$ for each line drawn, plus $$$\omega - 2 \cdot A_{i, j}$$$ for each chosen cell. If $$$(i, j) \in T$$$ instead, we just cut the $$$\omega$$$-capacity source-edge; any edges that may connect it to $$$s$$$ has already been cut.
Now we go back to the case where a drawn line reaches the edge of the grid. To model that cost correctly, we want to cut a $$$C$$$-capacity edge. Where should it go? Well, we can imagine it going to a fake node that's always $$$\in T$$$. But if we want to do that, we might as well connect it to $$$t$$$ directly. But since there's already an edge going there, we can simply add the capacities together, which is where the $$$(4 - deg(i, j)) \cdot C$$$ term comes from: there are $$$4 - deg(i, j)$$$ "missing" edges, each of cost $$$C$$$, that has been merged into the sink-edge.
If $$$x$$$ is the total number of lines drawn, we can thus see the total cost of the cut is $$$H \cdot W \cdot \omega - 2 \cdot (\sum_{(i, j) \in S} [A_{i, j}] - x \cdot C)$$$. Since $$$\sum_{(i, j) \in S} [A_{i, j}] - x \cdot C$$$ is our desired score, we can thus verify that the procedure is correct.
Lost stupid amounts of time on D due to output requiring a length descriptor. My fault for forgetting how to read again, but still annoying nonetheless... probably should've focused on E rather than continually trying wrong things on F in the time remaining... will have to find out in upsolve though.
how to solve problem D using DSU?
Graphs alone are enough for D. To perform the first and second types of queries efficiently, we can use multisets instead of vectors for the adjacency list. Then we can build 2 graphs(the second graph will be a reversed graph of the first graph), one contains edges from
y -> x
and the other one contains edges fromx -> y
. To answer the third query, we can run a DFS on the first graph to find the deepest reachable node(say 'root' node) from node x, then run another DFS on the second graph starting from the 'source' node and print all the nodes we visit one by one.Thnx for replying , but i solved using the graph only.i want to know can do u using dsu too?
My solution for C was based on the idea that all numbers in the same row would differ by 1 and all numbers in the same column would differ by 7... But I am getting WA on 5 test cases. Anyone got any idea why?
Link to my submission https://atcoder.jp/contests/abc225/submissions/26968319
You need to check the remainder when divided by 7 as well, the starting column of the original matrix is divisible by 7.
Sorry for necroposting, but I can't think of any better place to ask this.
In problem G, are there any solutions without max flows? I found a really neat idea that if we consider a chessboard coloring of the grid and rotate everything by 45 degrees we get 2 independent grids: one with black squares and the other with white squares (here new cells are adjacent if original cells were diagonally adjacent).
Now it is really easy to see that it is always optimal to only mark complete subrectangles in each grid, so one thing we can do is $$$O(n^5)$$$ subrectangle dp, which is too slow with long longs even after considering the low constant factor.
It's a cool idea and it's sad that it probably doesn't have a continuation.