https://mirror.codeforces.com/contest/1459/submission/101773389 Why my solution fails in test case 21 . problem div2c

Can someone explain why the property used in Problem C is also valid for multiple arguments?

why someone's submissions been skipped and receive no message

I didn't know the proof for problem B's solution but i solved it.

Endagorion Please add implementations to the problems as well it will be really helpful.

Solution sequence for Div2B is also available on OEIS. https://oeis.org/A241496. But I didn't understand the general formula. Can someone explain?

https://youtu.be/1OWGTQpfk5Y — recording of post-contest discussion with Endagorion with analysis of all div2 problems (so up to div1-D)

In problem D (div. 2) isn't the complexity O(n * k * n * A) where A the maximum capacity of a glass? Which in turn is 100^4 (since max n = 100 max k = 100 and max A = 100 )? 100^4 = 100 000 000 dp cells, so the solution should pass yes (with the memory optimization). But your complexity is O(n * k * n * A) I don't get how you got A^2 in there. Please someone explain, thanks.

In Problem-B's explanation,

Last Line:

Shouldn't it be where k=n/2 rounded up, instead of where k=n/2 rounded down?

Endagorion

Someone, do correct me if I am wrong.

Endagorion I think that in Problem-E's(div2) explanation

$$$p'$$$ should be equal to $$$v_0 + iv_x + jv_y + kv_z$$$ instead of $$$v_0 + xv_x + yv_y + zv_z$$$

this is part of the paragraph before the last one

Sorry if I am wrong.

Why did the rating change again as it was? Endagorion

Ignoring the short contest time and difficulty gap, I think your rounds are generally of high quality.

Thanks for the round :)

Auto comment: topic has been updated by Endagorion (previous revision, new revision, compare).

Is there a thought process on how to obtain the key observation of 'Latin Square'? It feels very clever and beautiful, but hard to come up with at the same time

In problem D(Glass half spilled), can anybody tell me , why we are considering taken glasses from n to 1 order.

How is the graph structured in Flip and Reverse F? The editorial makes it look like something on a straight line, which cant be true

Can Div2D/Div1B be solved using a top-down approach? Recursion with memoization?

Finally finished my alternative solution for div1D.

• Consider the sequence of $$$N+1$$$ prefix differences (number of 1 minus number of 0). The given operation is just reversing a contiguous subsequence between two equal values.
• Find ranges between equal values for the initial sequence of differences, merge overlapping/touching ranges. We can treat the resulting disjoint ranges independently since a reverse within one of them can't affect the rest.
• What does an "optimal" result look like? There's no reversible substring starting and ending with 1, so when we throw away leading and trailing 0-s, we must get a string like 1...101...101...1. Proof left to the reader. (Alternatively, we can have no possible operation even at the start.)
• For each of our substrings corresponding to disjoint ranges, we should be able to achieve this "optimal" situation. Turns out that the final string is now uniquely determined. Let's say that at the end, there are $$$a$$$ leading 0-s, $$$b$$$ trailing 0-s and a string starting and ending with 1 in between.
• Let's look at the minimum of our sequence of differences. If it's equal to the final difference, then $$$b \gt 0$$$. Proceed recursively without the last 0.
• Otherwise, the final difference is strictly not the minimum. That means the minimum difference is $$$-a$$$. We know $$$a$$$, time to remove the leading 0-s and proceed recursively again with $$$a=0$$$.
• Let's look at the maximum difference. That's reached after the last 1. Now $$$b$$$ = maximum difference — final difference.
• Now $$$a = 0$$$ and $$$b = 0$$$. If the minimum difference is unique, the final string must start with "1(1)", let's remove the leading 1 and again proceed recursively. Otherwise, it must start with "10".
• All cases are covered and we can find the answer in $$$O(N)$$$.

Can someone please help me understand the proof why we can convert any two Eulerian pathS with the operation of reversing a cycle ?

In problem b if r = 51 and b = 61, then blue will win. But when r = 51 and b = 16 then they will end up equal. Am I missing something?

does anyone know the proof of this property of gcd? GCD(x,y)=GCD(x−y,y) or any resource for exlanation?

Can anyone explain me the DP solution of div2-B...Please

In problem D why is the total available capacity necessary as a state ?

For 1459D - Glass Half Spilled

When I used int for integer variables, I got a runtime error. 107625846

However, when I replaced all int's with int16_t, it gave AC. 107680750

This is the first time I've encountered something like this. Is there a way to avoid runtime error without using int16_t?

Problem C can be solved using following identities

Instead $$$L$$$ write it as $$$R^{-1}$$$ and instead of $$$U$$$ write it as $$$D^{-1}$$$

• $$$ID = DI$$$
• $$$CR = RC$$$
• $$$II$$$ is identity
• $$$CC$$$ is identity
• $$$IC = TI$$$ and $$$CI = TC$$$ where $$$T$$$ is the transpose operation
• $$$IR^{k}I$$$ and $$$CD^{k}C$$$ are same as adding $$$k$$$ to each entry and taking $$$\mod n$$$.

Using these identities, we can reduce the whole expression to an expression where there is atmost one $$$I$$$ or $$$C$$$ and at most one transpose and rest $$$R$$$, $$$D$$$ and add operations which freely commute with each other.

A much simpler $$$O(n \log{n})$$$ solution for D1-F: 372965425

Define $$$f(l, r, u)$$$ to be true if node $$$u$$$ is the end of some diameter in the virtual tree defined by nodes $$$\lbrace l, l + 1, \dots r \rbrace$$$, and false otherwise.

The key observation is that for every node $$$l$$$, there exists some $$$b_l \geq l$$$ such that $$$(f(l, x, l) = 1) \iff (l \leq x \leq b_l)$$$ (in plain words, $$$l$$$ remains an endpoint of some diameter until $$$b_l$$$, and then ceases to be relevant).

How do we use this fact? Let's iterate over $$$l$$$ from $$$n$$$ to $$$1$$$ and maintain $$$S = \sum_{l \leq r \leq n} (\operatorname{diam}(l, r))$$$. At every step, we add $$$S$$$ to the global answer.

How do we update $$$S$$$ efficiently as we move from $$$l + 1$$$ to $$$l$$$?

It's easy to show that the required changes take the form of a few positive range updates on some prefix of the suffix $$$(l, n]$$$. More formally, we're required to process a set of updates $$$U(l) = \lbrace (l_1, r_1, d_1), (l_2, r_2, d_2) \dots \rbrace$$$.

1. $$$l + 1 \leq l_i \leq r_i \leq n, l_1 = l + 1, l_i = r_{i - 1} + 1$$$
2. $$$\operatorname{diam}(l, x) = \operatorname{diam}(l + 1, x) + d_i \qquad\forall \; (l_i \leq x \leq r_i)$$$
3. $$$d_i \geq d_{i + 1}, d_i \gt 0$$$

The proof for these statements is left as a simple exercise to the reader. The first two are trivial, but the third involved annoying casework for me.

It therefore suffices to add $$$\sum_{U(l)} (r_i - l_i + 1) \cdot d_i$$$ to $$$S$$$.

Now, due to the structure of these tuples (they're disjoint, adjacent ranges and the update value decreases) and the fact that we can query $$$\operatorname{diam}(l, r)$$$ in $$$O(1)$$$ (using a sparse table and an $$$O(1)$$$ LCA method of your choice), we can easily find them for any $$$l$$$ in $$$O(\vert U(l) \vert \log {n})$$$ using binary search + the $$$O(1)$$$ range diameter query structure.

But is doing just this for all $$$l$$$ efficient? Yes, as one can show that $$$\sum_{1 \leq l \leq n} \vert U(l) \vert \leq 4 \cdot n$$$!

The proof is left as an exercise to the reader.