Codeforces Round #743 Editorial

3 years ago, # |

← Rev. 5 →

+94

I just wrote the following Hinted solution to Div1C/Div2E in response to this comment by Penguin07, since this editorial didn't seem to be published when I started. Since I know many people like hinted editorials, I will post it here now anyway.

Hint 1

Hint 2

Hint 3

Hint 4

Hint 5

Hint 6

Solution

changelog

→ Reply

Colette

3 years ago, # ^ |

Thanks a lot for the explanation. I really didn`t understood anything in editorial, but your solution is nice and clear.

→ Reply

3 years ago, # ^ |

+10

looking for proof of first hint.

My issue

→ Reply

3 years ago, # ^ |

I'm not sure I understand. As I don't make or use any claims anywhere about how to calculate the values I suggest in hint 1, there's nothing to prove.

I was very careful about the repaint-before-joining concern, because I shared that concern. Off the top of my head, I'm not sure of a better way to prove that these aren't necessary than "This solution is optimal. Oh, look, it doesn't actually perform any non-joining repaints." (That's not to say that no easier proof exists!) Please let me know of any step where you think I may have inadvertently used this assumption, or any other.

→ Reply

3 years ago, # ^ |

← Rev. 2 →

"This solution is optimal. Oh, look, it doesn't actually perform any non-joining repaints."

This doesn't look valid argument to me. How can you look? As far as I understand, that dp calculation assume that you combine two or three subintervals. You can't claim that it's always two subintervals, because this thing should be proven. Then, in order to paint whole segment, you have to claim that you can paint first subinterval into first color, then second subinterval into second color, and if there is third subinterval, then color it into third color. Suppose you successfully painted first subinterval into first color. Why would we successfully color second subinterval into second color? It could possibly already have been messed by all previous actions over first subinterval? Because I think they could overflow bounds of first subinterval, and thus its coloring sequence now meaningless.

→ Reply

3 years ago, # ^ |

← Rev. 3 →

It's pretty trivial: You repaint the second interval first. No recomposition step on interval $$$[i..j]$$$ will ever mess with pixel $$$i$$$ or any lower-numbered pixel. This can be seen as a slightly stronger version of Hint 4.

EDIT: But I agree in hindsight that I should have provided more detail in the proof of hint 4, since there are a few ways to go wrong. I will add this to my original comment.

EDIT2: This is done.

→ Reply

3 years ago, # ^ |

I tried to make induction, but I stuck

This can be proven by induction, considering the last operation in any sequence that makes [i..j] monochromatic.

Hypothesis of induction: color $$$a_l$$$ is among colors in which [l,r] can be paint into single color in minimum steps. And, also, we can paint into $$$a_l$$$ color whole [l,r] segment never painting position $$$l$$$. Base of induction: length of interval is 1. Obviously minimum required steps = 0 and it already has color $$$a_l$$$. Step of induction: We know that for length of interval n — 1 is proven. We have to prove for interval of length n.

Let's pick optimal sequence that paint [l,r] into single color. Let's say its length is M. Look at last operation. Let say before it [l,r] would look like [l,i] of color $$$c_1$$$ and [i+1,j] of color $$$c_2$$$ and [j+1,r] of color $$$c_1$$$. Then we paint $$$c_2$$$ into $$$c_1$$$, so this whole thing becomes color $$$c_1$$$. Even though there is only 2 colors, their relationship with corresponding $$$S_{l,i}, S_{i+1,j}, S_{j+1,r}$$$ may take 9 options.

I stuck in following case:

$$$c_1 \in S_{l,i},\;c_2 \in S_{i+1,j},\;c_1 \in S_{j+1,r}$$$

In this case, length of sequence $$$M \geq k_{l,i} + k_{i+1,j} + k_{j+1,r} + 1$$$. Prove this inequality by contradiction. Suppose length of sequence is smaller. Then each step of sequence change at most one of intervals [l,i] or [i+1, j] or [j+1, r]. Let total changes of interval [l,i] to be A, and total changes of interval [i+1, j] to be B, and total changes of interval [j+1, r] to be C, not taking into account their join. Then $$$A + B + C + 1 \leq M$$$. But if we concentrate our look at corresponding intervals, we know $$$A \geq k_{l,i},\; B\geq k_{i+1,j},\; C\geq k_{j+1,r}$$$ by definition of $$$k$$$. In other words, we can't paint them in single color faster with longer array, because it didn't ever paint from outside. Now make sum of this inequalities. We get $$$A + B + C \geq k_{l,i} + k_{i+1,j} + k_{j+1,r}$$$. Thus $$$ M \geq A + B + C + 1 \geq k_{l,i} + k_{i+1,j} + k_{j+1,r} + 1$$$. But we supposed $$$M < k_{l,i} + k_{i+1,j} + k_{j+1,r}$$$. This is contradiction.

Now we know for sure, that $$$M \geq k_{l,i} + k_{i+1,j} + k_{j+1,r} + 1$$$. But what if $$$M = k_{l,i} + k_{i+1,j} + k_{j+1,r} + 1$$$ the case? Could it be such that $$$a_l \neq a_{j+1}$$$, so we know how to make first and last segments into not-equal colors without touching $$$l$$$ and $$$j+1$$$ correspondingly, but there exists $$$c_1$$$ that $$$c_1 \in S_{l, i}, \; c_1 \in S_{j+1,r}$$$? Then we don't know how to paint this interval.

→ Reply

3 years ago, # ^ |

Right. The last operation doesn't work: In order to replace a 3-way merge efficiently, we need the right-most color to match the left-most color, and have no way to control the colors available in the right-most interval. The worst-case looks something like this:

12 | 343 | 2
22 | 343 | 2
22 | 333 | 2
22   222   2

To avoid this problem, I need to scrutinize and replace some operation that cannot result in a 3-way merge in $$$[i..j]$$$. Luckily, in any counter-example, there must be one: The operation that modifies pixel $$$i$$$. I've fixed/replaced the proof in Hint 4 to hopefully not be broken, and added a proof to Hint 6 as well.

Let me know if you spot any other oversights.

→ Reply

3 years ago, # ^ |

← Rev. 2 →

Well, I completely agree with proof in hint 4. You're genius! I was trying to prove anything for past three days with no luck. There is tricky order of induction though.

About proof in hint 6

It doesn't prove what it meant to prove. Trouble is with M that may in original sequence expand by last coloring.

LLMMRR - regions
?????? - some previous states
..cc.. - previous coloring
.ddd.. - M is never recolored afterwards.
??dd?? - some states after

When you'll count, using induction (actually contraposition to induction hypothesis) we have suboptimal number of operations for L and R, because of their suboptimality you can replace them at least by one shorter, but you need to take into account that expanded d into region of L as an operation. You can't claim now that recoloring of M is separate 1 paint. So M of our sequence now is suboptimal by L, and suboptimal by R, but without additional step of recoloring M, it's mixed in suboptimality of L. But in case when M doesn't expand that's true. I think it's proof that painting without change of borders is always suboptimal. And then, you simply can build tree where each node has child-color into which it was painted, thus x indeed exists (just walk towards leaf).

Edit: no, not so easy, it's not proof that painting without change of borders is always suboptimal. Because we use fact that L and R is recolored, but there can be many places without recoloring

→ Reply

3 years ago, # ^ |

Re: Proof of Hint 6: The recoloring of $$$M$$$ can't partially merge it with any other region, because that region is recolored later but $$$M$$$ is not.

→ Reply

3 years ago, # ^ |

← Rev. 2 →

In proof of hint 6 you say color c is color of M before repaint. But M itself is before repaint or after? Because before last repaint it could have shorter length. If it's before repaint, then it's how I thought initially in previous reply. If M is after last repaint and L and R is also after, then let S be before repaint. Then union of L, R and S is not whole interval. Whole interval is union of L, R, M. You provide sequence to paint union L, R, S.

→ Reply

3 years ago, # ^ |

I intended it to mean $$$M_\text{before}$$$, as otherwise "previously of color $$$c$$$" doesn't make a lot of sense. But actually, $$$M_\text{before} = M_\text{after}$$$, since it is impossible for the original sequence to later recolor any cell in $$$M_\text{after}$$$ without also recoloring every cell in $$$M_\text{before}$$$.

That said, this property of $$$M$$$ shouldn't matter: The induction hypothesis and the non-clobbering guarantees from Hint 4 apply to the intervals $$$[i..x-1]$$$ and $$$[y+1..j]$$$ even if they do not respect region boundaries. The important thing is that the non-repaintedness of $$$M$$$ prevents the original sequence from being able to share work between $$$L$$$ and $$$R$$$. (So, this proof does NOT work on a circle, for example.)

→ Reply

3 years ago, # ^ |

I just wanted to tell right before you made reply that I got it. But reason is different. By contradiction, in case it enlarged into $$$M_{after}$$$ by recoloring, then joined part will never recolored, and didn't colored with this action. Thus, it was recolored earlier — we found earlier action that did recolor never-recolored-afterwards segment. Thus, our initially considered action wasn't first one of kind. Contradiction with assumption that it was earliest.

→ Reply

ToxicPie9

3 years ago, # |

← Rev. 2 →

+65

here's a nice alternate solution to Div.1 E that comes up intuitively but is surprisingly hard to prove.

my solution (spoiler)

Let's binary search for the answer. For some number $$$t$$$, we want to know if the polygon can be cut into at least $$$k+1$$$ regions, such that each region has double area $$$\ge t$$$. Call a configuration of cuts "valid" if it satisfies that condition.

Consider the dual graph of the regions that the polygon is cut into. In other words, we construct a graph such that each region is a vertex, and connect two regions with an edge iff there is a cut separating them.

Lemma 1. If there exists a valid configuration, then there is one valid configuration where the maximum degree of a vertex is at most 3.

To prove this, we need another lemma:

Lemma 2. Suppose a vertex in some configuration has degree at least 3: if region $$$X$$$ is adjacent to regions $$$A$$$, $$$B$$$, and $$$C$$$, then $$$\operatorname{area}(X) > \min(\operatorname{area}(A),\operatorname{area}(B),\operatorname{area}(C))$$$.

This seems pretty obvious if you draw the diagram. To actually prove this, we can utilize task 9.1 (on page 80) from [this book](https://www.isinj.com/mt-usamo/Geometric%20Inequalities%20-%20Bottema,%20et.%20al.%20(1968).pdf) (credits to mnbvmar for providing this). This margin is too small to contain the detailed proof, so I leave this as an exercise to the reader.

Now we go back to Lemma 1. Suppose a region $$$X$$$ has degree $$$d\ge 4$$$, and is adjacent to regions $$$A_1,A_2, \dots, A_d$$$. Then we can cut $$$X$$$ in two regions $$$X_1$$$ and $$$X_2$$$ such that they are both adjacent to at least two regions in $$$A_{1\dots d}$$$. WLOG, let $$$\operatorname{area}(X_1) \le \operatorname{area}(X_2)$$$. Since $$$X_1$$$ has degree at least 3, by lemma 2, we have $$$\operatorname{area}(X_1) > \min(\{\operatorname{area}(A_i) \mid A_i \text{ is adjacent to } X_1\} \cup \{\operatorname{area}(X_2)\})$$$, so $$$\operatorname{area}(X_2) \ge \operatorname{area}(X_1) > t$$$. This means that the configuration after cutting $$$X$$$ is also valid. After applying the procedure, the number of vertices whose degree $$$\ge d$$$ decreases, so if we repeat it enough times we will obtain a configuration where every degree is at most 3. QED

Now back to the solution. For $$$1 \le l,r \le n$$$, consider the sub-polygon with vertices in the interval $$$[l, r]$$$, wrapping around (i.e., vertices $$$l,l+1,\dots,r$$$, or $$$l,l+1,\dots,n,1,2,\dots,r$$$ if $$$l > r$$$). Let $$$dp[l][r]$$$ be the maximum number of regions we can cut that sub-polygon into, such that each region has area $$$\ge t$$$ (initialized to 0). Due to lemma 1, we only need to consider the cases where the maximum degree of regions is 3, so there are three ways to obtain $$$dp[l][r]$$$:

For each sub-interval $$$[a,b] \subsetneq [l,r]$$$, set $$$dp[l][r] \leftarrow \max(dp[l][r], dp[a][b])$$$. Notice that we only have to consider $$$[a,b]=[l,r-1]$$$ and $$$[l+1,r]$$$ here.
For $$$m \in [l,r]$$$, if the triangle with vertices $$$l,m,r$$$ has area $$$\ge t$$$, then set $$$dp[l][r] \leftarrow \max(dp[l][r], dp[l][m] + dp[m][r] + 1)$$$.
For each sub-interval $$$[a,b] \subsetneq [l,r]$$$, if the polygonal area defined by the vertices in $$$[l,a]$$$ and $$$[b,r]$$$ has area $$$\ge t$$$, then set $$$dp[l][r] \leftarrow \max(dp[l][r], dp[a][b] + 1)$$$.

Each step can be done in linear time. Case 3 can be done in linear time by using two pointers, or by maintaining an additional array $$$minl$$$, where $$$minl[a][b]$$$ is the minimum number $$$c$$$ such that $$$dp[a][a+c] \ge b$$$.

We can precompute the areas of sub-polygons in $$$\mathcal{O}(n^2)$$$, and update $$$dp$$$ in a bottom-up manner (from the smallest to largest intervals). Finally, the number $$$t$$$ satisfies the binary search condition iff $$$dp[l][r] + dp[r][l] \ge k+1$$$ for some $$$l,r$$$. (Taking $$$dp[0][n-1]$$$ directly doesn't work, see below)

The time complexity for each binary search iteration is $$$\mathcal{O}(n^3)$$$. However, it has a larger constant factor than the official solution, because we have to consider all pairs $$$(l,r)$$$ instead of only those with $$$l \le r$$$. tourist's contest submission (129206504) is the only one using this approach, and it almost got TLE (2994ms / 3000ms).

A lot of minor, tedious details were left out, but they should be quite easy to see.

sike

Congratulations to tourist for winning the contest, and solving E with this solution that is very hard to prove!

fun fact

implementation: 129215696

→ Reply

The.Dreamer

3 years ago, # |

For Div1 A, I think Topological sort isn't needed when we are using DP in DAG. We can just iterate on nodes in a random fashion and use DFS with DP to calculate the longest path

→ Reply

-_-INV4D3R-_-

3 years ago, # ^ |

Note that the process you've described simulates toposort. If a node v is reachable from node u, they either lay on the same cycle, or v belongs to a SCC reachable from u's SCC. In short, sometimes topologically sorting the graph explicitly is not necessary.

→ Reply

The.Dreamer

3 years ago, # ^ |

Not necessarily. It will be topological sort if and only if we are picking the right root randomly. Example, we have edges from 1 to 2 and 2 to 3, then topological based DFS will always start from 1 whereas a random traversal can start from anywhere. And in this problem, the order in which you pick the nodes/roots isn't important

→ Reply

-_-INV4D3R-_-

3 years ago, # ^ |

As the order of nodes isn't important for calculation of our DP, we only need to calculate dp[x] after it is calculated for all the nodes that would appear later in the topological sorting of the graph, which is ensured by the DFS itself.

→ Reply

The.Dreamer

3 years ago, # ^ |

That is the property of the DFS itself, and since it's pretty implicit, we don't need to mention the need of toposort like that, because highly likely that the readers of the editorial may relate it to the order of picking roots (which will obviously work, but an overkill)

→ Reply

adi_aggarwal

3 years ago, # |

← Rev. 3 →

This edge has weight 0 if a<b and 1 otherwise Shouldn't the weights be vice versa?

Why

→ Reply

chuka231

3 years ago, # ^ |

why answer is 5? you can read them in one cycle 1,2,3,4,5.

→ Reply

Markadiusz

3 years ago, # ^ |

Thanks for pointing out that typo. It should be correct now.

→ Reply

16204

3 years ago, # |

+37

I never believe that I will one day say this to a flow problem, but D (div 1) is great. After the contest I've talked to some people about it, and most of their thought processes involve somehow optimizing the finding-the-blocking-flow operation (which one of them apparently managed to do). I am glad to see that instead of some obscure trick written in Chinese/Polish/Russian paper #1257, the key to the solution lies in a simple observation. Kudos to the authors for coming up with such a nice problem.

→ Reply

ar_coder

3 years ago, # |

← Rev. 2 →

Can anyone help me with the problem 1572A - Book?? My solution is giving wrong answer in test case 2. I have used topological sort.

My solution — 129302238

→ Reply

3 years ago, # ^ |

IMO the problem is that for each chapter of the book (nodes if you suppose its a graph) you have to check all the ones on its require list. but you only check the last one in the topological order. since my solution is pretty much like yours, i recommend you to check it out: [](https://codeforces.me/contest/1573/submission/129306114)

→ Reply

ar_coder

3 years ago, # ^ |

You were right. I was updating only for the last element of topological sort.

Accepted solution (if anyone need) — 129310560

Thanks a lot MOOONI

→ Reply

Kuldeep_Dahiya

3 years ago, # ^ |

Can you please explain what your dp vector stores? And, what this lines of code means

int y;
            if (nx < x) {
                y = dp[x]+1;
            } else {
                y = dp[x];
            }

Thanks.

→ Reply

Can you suggest why TLE at test 3 ,I m just using set erase and insert

3 years ago, # |

div1 A was really interesting!

→ Reply

Dextroxd

3 years ago, # ^ |

← Rev. 3 →

Hello ,can we solve (DIV2C/DIV1A) problem just by modifying topological sort, you can see my code here Code link.It is giving me the wrong answer. Can you please tell me why?

→ Reply

Khoderkhoda

3 years ago, # ^ |

if(indegrees[nbr]==0&&(nbr>m)){
                            q.push(nbr);
                        }

This line ,nbr>m is incorrect.You need to check this for every parent of nbr which is present in the current 'q' and nbr should be greater than all of them .You can check my code but its giving TLE dont know why

→ Reply

Khoderkhoda

3 years ago, # ^ |

→ Reply

3 years ago, # ^ |

in your cycle function you should add a single '&' character before adj and it'll be alright.

→ Reply

Khoderkhoda

3 years ago, # ^ |

ya figured it out my bad ,thanks btw

→ Reply

yeetholmes619

3 years ago, # |

If anyone solved Book (Div 2 C / Div 1 A) with the first approach mentioned in the editorial then can you please send me your code, I'm having a hard time understanding what is written. thanks!

→ Reply

https://codeforces.me/contest/1572/submission/129340066

3 years ago, # ^ |

← Rev. 2 →

I think you can refer mine

below are comment on variables.

set<int> lefts: contains chapters that are not read yet.
set<int> reads: contains chapters that are readable.
vector<int> resolves[n]; resolves[i] contains chapters that needs the chapter i to be read first.
int need[n]: need[i] == #of chapters that must be read first before chatper i.

bool hasNext: there's next chapter readable.

→ Reply

yeetholmes619

3 years ago, # ^ |

I appreciate it! Thank you so much !

→ Reply

T1duS

3 years ago, # |

in which we can find a matching with maximum cost and size at most k with for example one of the standard min cost max flow algorithms

Can someone please explain this part?

→ Reply

Markadiusz

3 years ago, # ^ |

+22

Let's assume that after the reduction we are left with edges (1, 5), (4, 5), (4, 6), (2, 6), (2, 10). Then we can make a flow network like so and find min cost max flow from node S_0 to node T in it. Here the first value on an edge is its capacity and the second is its cost. I hope that you can figure out the general approach from this picture.

Flow network

→ Reply

__hermit__

3 years ago, # ^ |

How to prove that minimum cost always occurs when flow is k?

→ Reply

patou

3 years ago, # ^ |

It’s based on the fact that the weight of an edge $$$w(U, V)$$$ is the sum of the values of the two vertices $$$a_U + a_V$$$. Consider an augmenting path algorithm to calculate maximum weight flow/matching. In order to increase the size of the matching by one, we search for an augmenting path with maximum weight. For example, if edges (B, C) and (D, E) are in the matching, an augmenting path may be (AB), (BC), (CD), (DE), (EF). Its weight is $$$w(AB) - w(BC) + w(CD) - w(DE) + w(EF)$$$. This is equal to the sum of the values of its endpoints, $$$a_A + a_F \geq 0$$$. So, as k increases, the maximum weight of a matching of size k is non-decreasing.

→ Reply

__hermit__

3 years ago, # ^ |

Got it thanks!!

→ Reply

3 years ago, # |

Can anyone prove the optimality of the solution for div2 a?

→ Reply

jeal0uspengu1n

3 years ago, # ^ |

Well, consider taking a number 2079, so we have to make it 0, either by subtracting 1 or swapping positions. Now first we'll subtract 1, 9 times to make it 2070. After this we've to make 7->0, for this we'll need to subtract 1, 70 times but since we can swap 2 digits , so we'll swap 7 and 0. The main idea being getting every digit to the one's place so that we can make it 0 in min number of operations. For more clarity consider 10, we'll need to subtract 1, 10 times to make it to 00. And so the most optimal way is to swap 1 with 0 and then subtract 1 only once.

→ Reply

3 years ago, # |

+17

I think editorial is poorly written. And that's why I decided to write my alternative editorial with hints and proofs of tasks which I solved or upsolved. Only my solutions (alternative solutions not covered).

1573A - Countdown

Editorial

Hint 1

Hint 2

Hint 3

Hint 4

Hint 5

Hint 6

Hint 7

Hint 8

Hint 9

Solution

1573B - Swaps

Editorial

Hint 1

Hint 3

Hint 4

Hint 5

Hint 7

Hint 8

Hint 9

Solution

1572A - Book

Editorial

1572B - Xor of 3

Editorial

Hint 1

Hint 2

Hint 3

Hint 4

Hint 5

Hint 6

Hint 7

What if array starts with odd number of 1 and right next to it is even number of zeroes and we have unlimited number of actions?

My answer

For example, we can do 100001->111001->111111. What if we don't?

Assume there is 1000011??? where ? each is either 0 or 1. Then: either:

1000011???-> 1000000???
1000011???-> 1001111???
1000011???-> 1110011???

We either decrease right by 2, or increase right by 2, or increase left by 2, or decrease left by 2. In any way, until we do 101 -> 000 any segment of 111 keeps parity, and any segment of 000 also keeps party. This means we have to do 101->000 to change parity or join two segments. And to find it, easy way is to make 100001->111001->111111 = join ones. If parity becomes even -> nice. Otherwise when we appear in situation where array starts with ones, and right next to them single 0 and single 1, then we do 101->000 and make all 1 to the beginning. Then finish with algorithm for case when array starts with 0.

Proof

The only thing left: why we definitely find position with 101, or join with odd? Well, if we don't find, then all segments of 0000 were even, and all 1111 afterwards were also even, this means that total parity was odd. But odd parity can't be translated into even parity, as noted earlier. Or, we can't join odd number of 1111 because they're in the end of array. But then, every segment of 0 is even, so we never may have 101->000 so parity of all segments will be same, they only can disappear, but segment in the beginning and in the ending will remain.

Solution

1572C - Paint

Editorial

Hint 1

Hint 2

Do we really need to paint blocks without change of borders?

My answer

No. And it's not easy to prove. During contest you didn't have to prove it, you might assume it and try to solve without proof.

Try to prove it.

Wrong proof to show that it's hard

Let's imagine colored tape. Over initial array we will tape segments of same color, so 112233 would become three segments of tape. Next, each action we apply, we instead tape new layer with new color of new segment. For example, 112233->114433 would become four segments of tape: three initial segments plus segment over 22 with color 44, making there 2 layers. Similarly, 112233->112222 is three initial segments plus one segment over whole 2222.

Next, we would like to consider some sequence of actions with paint of segments that doesn't change it's borders. Then we would like to find some bad action then either don't do it, or move it. Here is counterexample of "don't do it" case: 123->124->154->155->111. If we skip 154->155 step, then we can't 154 make into 111 in single step. If we skip 124->154, then we can't get 155 from 124 in single step. This example show how skip of single step may break sequence of steps. If we think, that we can find out what steps we should skip, consider following case:

12???????????
many steps in between
13???????????
many steps in between
23???????????
many steps in between
43???????????
many steps in between
41???????????
many steps in between
31???????????
many steps in between
31111????????
many steps in between
24444????????
many steps in between
2444422222222
2222222222222

You can see that first time first element change border is when it has color 2, so you may have idea to make it 2 first time we recolor it. It happens first at 13??->23??. And this is what we want. Then just don't recolor it into 4 and 3 and we indeed have less number of actions. Also you may see that first time when second element change borders is when it has color 1. So, in first time we paint it we would have idea to paint it into color 1 straight ahead. It happens at step 12??->13??, so, we have idea to make it 12??->11?? instead. But then, whole sequence of actions become broken, because we have different borders.

Also, we failed to avoid paint without change of borders. The only easy skippable is something like 12->14->11. We can just make 12->11. But to transform sequence into this case, we probably want to reorder actions.

It's easy to see that for each segment of tape, there are other segments of tape within, and none of them intersecting. And then, very easy to claim that actions within two non-overlapping segments are interchangeable. But they're not, at least in the meaning I want. Here is counterexample:

3421->3121->4121->4111->1111

Consider state before last action: 4111. There are two segments. Let's try interchange actions within them: 3421 apply first action of segment 4 (we did color 3 into 4). 3421->4421 we now have new tape 4, which wasn't in previous set of actions. Also, borders of color change did change in different order. You can't simply claim that if you continue actions you'll get same result. At least you should define what means to continue actions if configuration of segments now different.

So, main issue in this approach is that after we swap actions or change color of segment, it may unintentionally join with other segment during steps in between, and ruin our proof.

Proof

Suitable proof is following. Let's say paint action is bad if it doesn't change segment borders. Let's prove that for minimum number of actions there is exists sequence without bad actions. We will prove it by induction by minimum number of steps required.

Base case: minimum steps required = 0. Obviously we don't need bad actions. Induction: minimum steps required is n. Pick this sequence of actions which require n steps. Perform first action. Now we left with n-1 actions, and we know sequence of actions. This means array after performing single action is possible to transform in single color using n-1 actions. Thus, minimum steps required for it is <= n-1. By induction there is sequence of actions with length <= n-1 without bad actions. Either it's exactly n-1 -> and we can just perform first action + n — 1 = n actions. Or there is < n-1 actions, and with our first step is less than n actions in total, which is contradiction with claim that minimum actions required is n. Now, consider our new sequence of actions: first original step plus sequence of n-1 actions without bad actions. This means, that only first action can be bad. If it's not, then we have required sequence of actions. If it's bad, then we have to show how to make it good.

What means that first action is bad? This means, that we paint one of initial segments into different color. Let's say it initially has borders [l, r] and color c, and we paint it with color d. It can't be whole array because n would be zero. So there should exist some step i which is first join of segment [l, r] with other segment and become segment [L, R] with color C.

Now, let's do sequence of actions without first action. Only n-1 actions, up to first point when [l, r] is joined with other segment. Let's say it's action j of n actions. It may surprisingly happen, that j == i. This means, that everything up to i-th action didn't touch segment [l, r] and it still has color c. Also, C != c because otherwise they already would join. This means, that we can color c into C, and continue making actions from step i+1 until end. So we have sequence of n-1 actions which can transform array into single color. But this is contradiction that n is minimum required number of actions.

Other case: j < i. Now, recolor [l,r] into d right before step j. If segment [l, r] doesn't expand by it, then we can continue our sequence of actions, and we will get n actions in total. But if j > 2, we made our bad action second action in sequence of later, so we can replace sequence of actions starting from second step into sequence without bad action using induction hypothesis. Otherwise j = 2, so our sequence looks like: color [l, r] into d, then color something into c, such that if [l,r] would be still c, then it would join to other segment:

original sequence
????ccc????
????ddd???? step 1
????dddcc?? step 2
after we skip step 1
????ccc????
????ccccc?? step 2

But don't forget that only first move is bad, so this can't be the case:

????ccceef?
????dddeef? step 1
????dddccf? step 2 <- because this is bad step
So f = d. This leads to case
????ccceec?
????cccccc? step 2 (we skip step 1).

And... You know, this drives me crazy. I spent many hours trying to prove it, and, you can't just say well, every left border in version of first sequence at each step will be less or equal to same border without skipped step 1, also every right border in second sequence at each step will be greater or equal than in version without skip, thus at last step left border will be 0 because in version without skip it was 0, and similarly right border will be n, thus whole segment will be same color. Because: why the hell it should be true? What is the reason? It might be even wrong, but I don't think I can produce counterexample. Also, why wouldn't this colored transition not cause any issues like blocking filling with color that can't pass this one?

So here is example of this case:

54532 - initial sequence
54232 - paint 5 into 2 <- step 1 is bad
55232 - paint 4 into 5
55222 - paint 3 into 2
55555 - paint 2 into 5

After first step, everything is optimal, and no bad moves. And yes, you can paint it faster:

54532 - initial
55532 - paint 4 into 5
55552 - paint 3 into 5
55555 - paint 2 into 5

So... NO, I Don't have a proof. I tried everything. I even tried to draw connection with problem from USACO mentioned above, and everything there is much easier.

Very short way to prove solution from USACO problem.

Well, let's continue without proof. I'm sorry. I said I'll give proofs, but well... I'm looking for one though. (even starting to doubt that solution is legit)

Hint 3

Hint 5

Hint 6

Hint 7

Hint 8

Hint 9

Hint 10

Hint 11

Solution

1572D - Bridge Club

Editorial

Hint 1

Hint 2

Hint 3

Hint 4

Hint 6

Hint 7

Hint 8

Hint 9

Hint 10

Hint 11

Solution

→ Reply

Dzksh

3 years ago, # |

How is the time complexity of the first approach of 1572 — A Book O(nlogn) ? Please can someone explain.

→ Reply

3 years ago, # ^ |

← Rev. 2 →

all chapters(n) are once added to set(logn) and removed from it(logn).

so total O(nlogn + nlogn) = O(nlogn)

→ Reply

Dzksh

3 years ago, # ^ |

Thanks a lot.

→ Reply

3 years ago, # ^ |

no problem!

→ Reply

akshpan

3 years ago, # ^ |

Just to confirm, logn because we are using sortedset? I tried to find some submission which has implemented the first approach but couldn't so not sure.

→ Reply