We will hold AtCoder Regular Contest 119.
- Contest URL: https://atcoder.jp/contests/arc119
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20210516T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: E869120, square1001
- Tester: maspy
- Rated range: — 2799
The point values will be 300-500-500-700-800-800.
We are looking forward to your participation!
E was quite similar to 1513F - Swapping Problem.
Is the solution similar? Cause in the CF problem two diff arrays are used.
Yes, you just have to pay attention to the fact that you mustn't overlap an interval with itself, which isn't too hard to take care of.
You can assume $$$b_i = a_{i+1}$$$.
Then, you have to maximize $$$|a_i - a_j| + |b_i - b_j| - |a_i - b_i| - |a_j - b_j|$$$ instead of $$$|a_i - b_j| + |b_i - a_j| - |a_i - b_i| - |a_j - b_j|$$$.
Hence, the two segments should be both in $$$X$$$ or both in $$$Y$$$ instead of one of them in $$$X$$$ and the other one in $$$Y$$$. The rest of the solution is identical.
A was a complete search on $$$b$$$.
C was really neat, a subarray can be chosen if the alternating sum of heights is 0.
What was the approach for B?
If you visualize the 1s as empty cells and 0s as people/pieces on the array, the problem becomes: move each person to the correct spot in the final string, one person cannot walk past another. Answer is number of people that need to move.
That's pretty neat, thanks!
Oh! So instead of working with "people" you work with "empty chairs" and that makes the solution straight-forward! Thats fantastic!
I did some complicated counting and moving according to the rules and keeping track of how much people have been pushed and I needed to iterate forwards once and backwards once: Submission
But this is so much simpler!
How does this work?
Consider the beginning of s and t in Sample 4, these are
Here, the first '0' (in position 2) can and must be swapped with the 1 in position 4. After that first swap s looks like:
And same pattern repeats until we have.
But for that we needed more than 4 operations (it is 13 I think).
Where am I wrong?
You can move a $$$0$$$ to any position between the $$$0$$$ on its left and the $$$0$$$ on its right, using only $$$1$$$ move.
Well, it isn't optimal to make that first swap between position 2 and 4 in the first place. For sample 4, if you go backwards instead it'll work.
There always has to be a corresponding pair of 0s on positions
fromin $$$S$$$ and positiontoin $$$T$$$ such that in $$$S$$$ the elements(from, to]only contain ones. Then we can apply the operation to move the zero fromfromtotoin $$$S$$$. Repeat until all zeroes are sorted.We prove with contradiction with extremal principle. Assume such a pair does not exist.
We search the zero in $$$S$$$ on
fromwith following properties:tois to the right offromto(as far to the right as possible)If such a
fromdoes not exist, we reverse both strings $$$S$$$ and $$$T$$$. If suchfromstill does not exist, then $$$S=T$$$ and the answer is $$$0$$$. Suppose there is a zero in $$$S$$$ in(from,to]. Then its correspondingtowill be to the right of our maximumto. Contradiction.So our assumption was wrong, and such a pair does always exist.
How is this true? Any proof?
It's useful in this problem to find an invariant. If we add a $$$1$$$ to two adjacent elements, notice that the alternating sum of the entire array does not change. The same if we subtract $$$1$$$. Thus, the alternating sum is an invariant. And we want all zeros, so the alternating sum of our array must be the same as all zeros, which is zero.
In-contest though, I just did a few examples and it reminded me of multiples of $$$11$$$, like $$$352$$$, and one easy way to check for divisibility by $$$11$$$ is to take the alternating sum mod $$$11$$$ and check that it's $$$0$$$.
Yes I agree! This was a very fantastic problem! The idea was to consider the sum $$$\sum_{i=1}^n (-1)^i a_i$$$ which is invariant under any such move(this is essentially the alternating sum) Originally I thought of $$$\left( \sum_{i=1}^n a_i \right) \pmod 2$$$ which unfortunately didn't work. You play around with it more and you realize the above invariant. By the way to those who are unclear how a solution after this would work, here are a couple of ideas:(I consider $$$1$$$-based indexing, just to be clear)
You can store $$$pref[i][j]$$$ where $$$0 \leqslant i \leqslant n$$$ and $$$j = 0$$$ or $$$1$$$, that denotes the sum of all elements $$$h_i$$$ with indices not exceeding $$$i$$$ and congruent to $$$j$$$ modulo $$$2$$$. This is computable in $$$\mathcal O(n)$$$ time. Now checking whether the subarray $$$(l, r)$$$ can be destroyed or not is the same as
This is equivalent to checking
If we write $$$x[i]=pref[i][1]-pref[i][0]$$$, then we have to find all pairs of equal elements in the array $$$x$$$. Use maps/sorting to solve this in $$$\mathcal O(n \log n)$$$
Solve this without ever storing $$$pref$$$ or $$$x$$$. Note: you may have to use a map.
Solve it if instead of being allowed to change $$$2$$$ consecutive elements you were allowed to change $$$3$$$ consecutive elements. How about $$$p$$$ consecutive elements for a prime $$$p$$$?
Bonus 1 was almost what I did in-contest, although I didn't need to store $$$x$$$
I have literally no idea if this will work but it's really cool if it does.
We want $$$z^j$$$ to be periodic with a period of exactly $$$p$$$. One possible $$$z$$$ is $$$1^{1/p} = (e^{2\pi i})^{1/p} = cos(2 \pi i / p) + i sin(2 \pi i / p)$$$
I thought of this because I watched something on the FFT yesterday lol
Umm I did say you don't have to store $$$pref$$$ or $$$x$$$
Yes! For bonus $$$2$$$ your idea is exactly like mine, but I guess these ideas will be implementation heavy. I think a simpler solution would exist if you made use of the fact that
where the $a_i$ are all integers(actually even rational is fine, but not needed here) and $$$z$$$ is a primitive root of order $$$p$$$(which is pretty much any root because $$$p$$$ is prime) iff all the $$$a_i$$$'s are equal. This thing works only if $$$p$$$ is prime. I am aware of a solution of the case $$$p = 3$$$ but I don't know a very clean way of generalising it to arbitrary primes.
In my solution, I didn't store $$$pref$$$. I meant that it's trivial to remove $$$x$$$.
I am getting +ve deltas in ABCs and CF D2s, I must be improving.
ARC/SRM div 1-You what?
How to solve B?
a[i] means the distance between i-th 0 and (i+1)-th 0.
And a operation is a[i]+=x and a[i+1]-=x (x is not necessary be positive), and s equal to t iff (a[i] of s) = (a[i] of t).
This can be done by greedy.
Can you elaborate on the greedy part?
How do you prove that you can always find a zero that you can move without hitting another zero. Implementation-wise, is this problem harder if you also have to output the moves?
For example S=00111100 and T=11000011, the innermost zeroes have to move first so you can't just do left to right.
A[i] need to be modified if and only if :
$$$\sum_{j\leq i} A[j]=\sum_{j\leq i} B[j]$$$
$$$A[i]=B[i]$$$
How to solve C?
The intuition I had was the following: any operation will either increase or decrease the sum of odd-indexed values and even-indexed values by exactly 1. This means that the sum of odd-indexed and even-indexed values being equal is a necessary condition for (L, R) to be valid. One can notice that this is also sufficient (to see why, imagine doing operations to set values to 0 from the left to the right). This means that if you multiply all odd-indexed values by -1, the answer is simply the number of non-empty subarrays with a sum of 0.
Wow. That's really nice! Thanks!
The gap between C and {D, E} is too large :(
During the contest, TL (link):
After the contest, AC (link):
Nice problems anyway :) Thanks for the contest!
Did a problem similar to C appear on codeforces before?
I can't remember where I remember the parity trick from.
Someone have AC on E with $$$O(nlog^2n)$$$?
Editorial still not available? Currently I only see problem A's solution.
AtCoder Regular Editorial
I'd only competed in ABC before and I had never seen such a late editorial, sad.
Editorial for D.
For all $$$c[i][j]='R'$$$ ,connect an edge between node $$$i$$$ and $$$j+n$$$,and we will determine the direction of this edge latter.
It's obvious that it forms an binary graph: left part represents row and right part represents column.
If an edge is "Left" to "Right", means an operations "x Left Right".Otherwise , "y Left Right".
And you will erase some edge ,and in the remaining graph every node have at most one out edge.
Also there can't be a cycle , otherwise you can't find an order to achieve it.
So you can find any spanning tree of a connected component , and let the direction be "son to father".
It's can be proved that there is exactly one node without any out edge in a connected component ,(but you can choose which part it is from by choosing the root).
The solution only needs to be output in topological order
code https://atcoder.jp/contests/arc119/submissions/22676280
In A why the possible values of b is 0 to 59?
Once A becomes 0 increasing B would just increase sum since C remains N.
Can someone share a hint for Problem D? I've tried playing with bipartite graph constructions, but am not able to progress beyond that.
The edges you choose to use mustn't form any cycles.
Going to build off your hint in the previous spoiler. Let the left side of the bipartite graph represent rows and the right side of the bipartite graph represent columns. Then we denote left to right edges be coloring in rows, and right to left edges be coloring in columns, considering cycles to be made of directed edges.
In addition to obeying the no-cycle constraint, we also want to make sure that we choose edges such that each vertex has outdegree 1 (representing that a row or column is filled in exactly once).
One possible sequence of operations can be found through generating spanning trees of each connected component in the directed graph, but I'm not sure how to root these trees in a manner that maximizes the coloring.
If we use R operations of type X on distinct rows and C operations of type Y on distinct columns, our end goal can be stated as the minimization of (H-R)(W-C).
Note that each connected component of size 1 represents a row/column that has no red squares in it. For each connected component of size greater than 1, we can treat its spanning tree as a topological sort for "destroying" the possibility of activating an X or Y operation on a row/column, and we want to activate operations from bottom to top (the root) in order to yield the most operations. The only untouched node is the root of the connected component, which represents either activating all columns in a row (but not the row) or all rows in a column (but not the column).
If there are A size 1 components in the rows and B size 1 components in the columns, we can try to minimize (A+K_1)(B+K_2), where K_1 is the number of non-activated rows, K_2 is the number of non-activated columns, and K_1+K_2 is the total number of components larger than size 1. It turns out that (A+K_1)(B+K_2) is minimized when either K_1 = 0 or K_2 = 0, so we just try both possibilities to see which yields a better answer.
Thanks to dorijanlendvaj for helping me finish this off!
My approach to D is slightly different — I also make a bipartite graph but one partition has red cells and the other has rows/columns. If we pick the last row/column (w.l.o.g. column), then we know that all red cells in this column can only be used with their rows, and we don't need to pick any other cells for these rows; this frees up all other red cells in these rows to be used with their columns, and so on. Notice that this way, we traverse the whole connected component of this row/column and find an ordering for all rows/columns in it except one. For every component with $$$r$$$ rows and $$$c$$$ columns, we can thus use $$$(r-1, c)$$$ or $$$(r, c-1)$$$. To combine it over components, a simple DP tells us the maximum number of columns we can use for each number of rows, and then we pick the pair ($$$r$$$ used rows, $$$c$$$ used columns) that gives the maximum answer. The rest is implementation of construction.
Firstly for every red cell (i,j) connect row i with column j(make a graph with h + w vertices each depicting a row and a column). Now the operation is like, we can remove any vertex(equivalent to painting a row or column as white) which has at least one edge and disconnect all the edges involving this vertex. Lets say for a component C having V vertices, it can be seen that we can never remove all vertices as the last one will not have any edge for sure and infact it can be proved that we just need to leave only one vertex and remove rest of those. To do so just make dfs tree assuming the node to be removed as root. Now remove nodes leaf by leaf as every node is surely going to have that one edge going to its parent. Rest part remains to determine how many columns nodes or row nodes we can leave(each component is always having one row and one column option to be left, discarding those with size = 1) and remove others which can be easily checked by some dp or brute force or maybe some maths. Suppose we decide to remove R row nodes and C column nodes, then for first R components we will start dfs with some row labelled node and for other C we will start with some column labelled node.
How to solve F?
Dp of Dp
dp[i][j][k] : consider the first i stations, the ways of "The distance to the last A is j,and the distance to the last B is k".
And answer is $$$\sum_{\min(j,k)<K} dp_{n,j,k}$$$.
You can do this dp in $$$O(N^3)$$$ .
But you can find that if $$$j>k+2$$$, you can go to the next B and back to the previous A in 2 steps , so you can think j = k+2.
This also works for $$$k>j+2$$$.
So it is $$$O(N^2)$$$.
my solution: https://atcoder.jp/contests/arc119/submissions/22690514
Editorial to Problem D:
The problem is quite similar to the following template.
Bombs in the Grid
Problem Statement: Given a grid $$$G[n][m]$$$, $$$1<=n, m<=10^3$$$, some cells have a bomb that can destroy either the row containing the cell or the column. Find an order in which to use the bomb to maximize the number of destroyed cells.
Tutorial: This genre of problems can be solved by building a bipartite graph with $$$n+m$$$ nodes. Node $$$i$$$ and $$$j+n$$$ are connected by an edge if a bomb exists in the cell $$$G[i][j]$$$. Suppose, we choose to destroy $$$r$$$ rows and $$$c$$$ columns. Then, the number of cells not destroyed is given as $$$(n-r)(m-c)$$$. So, we have to minimize this objective function. Find the number of connected components in the constructed bipartite graph. Let there be $$$p$$$ components of size $$$1$$$ comprising of row nodes only and $$$q$$$ components of size $$$1$$$ comprising of column nodes only. Let there be $$$k$$$ components with a size greater than $$$1$$$. We know that we will not be able to use $$$p$$$ rows and $$$q$$$ columns (as they don’t have any cell with the bomb). How to deal with the components of size greater than $$$1$$$? Consider one such component. Pick any node arbitrarily, (it may be a row node or a column node, without loss of generality, let’s assume we pick a column node), then we know that all bomb cells in this column can only be used with their rows, and we don't need to pick any other cells for these rows; this frees up all other bomb cells in these rows to be used with their columns, and so on. Notice that this way, we traverse the whole connected component of this row/column and find an ordering for all rows/columns in it except one. Now, for each of the $$$k$$$ components, we need to decide whether to root that component with a row node or a column node. Suppose we choose $$$x$$$ components that are to be rooted with row node, and for other components, column node is chosen to be the root. Then, the number of cells not destroyed will be $$$F(x)=(p+x)(q+k-x)$$$ where $$$p, q$$$ are fixed and $$$x$$$ can be varied. From mathematical analysis, if $$$p>q$$$, choose $$$x=k$$$ else $$$x=0$$$ for optimal value.
Implementation: Construct a graph with $$$n+m$$$ nodes, representing rows and columns, with node $$$i$$$ and $$$j+n$$$ having an edge if a bomb exists in cell $$$G[i][j]$$$. Let $$$p$$$ be the number of row nodes having no edge and $$$q$$$ be the number of column nodes having no edge. Let the number of connected components of size greater than 1 be $$$k$$$. If we only want to know the maximum number of cells destroyed, it is given as $$$nm-pq-k*max(p, q)$$$. If $$$p>q$$$, run multi-dfs considering row nodes only as root, else consider the column nodes as root. In the dfs call, suppose you are at vertex $$$u$$$, after calling dfs from its child $$$v$$$, add pair $$$<v, u>$$$ to the result. This will provide the ordering of using bombs. While processing the pairs in answer, let the current pair be $$$<v, u>$$$, if $$$v<n$$$, this means bomb in the cell $$$G[v][u-n]$$$ is used to destroy row $$$v$$$, otherwise bomb in the cell $$$G[u][v-n]$$$ is used to destroy column $$$v-n$$$.
Submission: https://atcoder.jp/contests/arc119/submissions/22699042