Codeforces Global Round 9 — Editorial

4 years ago, # ^ |

+21

Yes, it is true because $$$|q| / x = |q| \cdot |x|^{-1} \cdot \bar x$$$. Since $$$|q|/x$$$ is Hurwitz quaternion and $$$\bar x$$$ is irreducible, we obtain that $$$|x|$$$ must divide $$$|q|$$$.

About transformation being $$$q \cdot v \cdot \bar q$$$, I think it's mostly correct. Assume $$$v \mapsto \frac{1}{2} q \cdot v \cdot \bar q$$$, where $$$q=s+ix+jy+kz$$$ is primitive, makes the transformation with integer matrix. It means that among $$$(s,x,y,z)$$$ exactly two numbers are odd and two numbers are even. Without loss of generality let's assume that $$$(s,x)$$$ are odd and $$$(y,z)$$$ are even. Consider quaternion $$$q'=s'+ix'+jy'+kz'$$$, where:

$$$s'=\frac{s+x}{2},~ x'=\frac{s-x}{2},\\ y'=\frac{y+z}{2},~ z'=\frac{y-z}{2}$$$

Note that all $$$s'$$$, $$$x'$$$, $$$y'$$$ and $$$z'$$$ are integer here. Matrix form of transform given by $$$v \mapsto q'\cdot v \cdot \bar{q'}$$$ is:

$$$ \frac{1}{2} \begin{pmatrix} s^2+x^2-y^2-z^2 & 2(sz-xy) & 2(sy+xz) \\ 2(sy-xz) & 2(sx+yz) & -s^2+x^2+y^2-z^2 \\ -2(sz+xy) & s^2-x^2+y^2-z^2 & 2(sx-yz) \end{pmatrix} $$$

I used wolframalpha to get the matrix. As you may see, it's quite similar to matrix of $$$v \mapsto \frac{1}{2} q \cdot v \cdot \bar q$$$ transform. To actually get that matrix, you have to:

Swap second and third row;
Multiply second and third rows and second columns by $$$-1$$$;

Swapping second and third rows alongside with multiplying them with $$$-1$$$ is done via $$$180^\circ$$$ rotation around $$$x$$$ axis, which may be represented as quaternion with unit norm. Multiplying second column by $$$-1$$$ is equivalent to changing $$$r_2 \mapsto -r_2$$$, but we don't really need it for this problem, as we're allowed to use negative coefficients. Layout is a bit messy here, but I hope it's clear now that considering only $$$v \mapsto q \cdot v \cdot \bar q$$$ is fine, as it's always possible to get here from $$$v \mapsto \frac{1}{2} q \cdot v \cdot \bar q$$$ if you're fine with loosing some signs or the relative order of $$$r_1$$$, $$$r_2$$$ and $$$r_3$$$ (which is the case in this problem).

→ Reply

Benq

4 years ago, # ^ |

← Rev. 2 →

+13

Why is $$$\overline{x}$$$ irreducible? According to Wikipedia "a Hurwitz integer is irreducible if and only if its norm is a prime number" but this isn't the case here?

→ Reply

4 years ago, # ^ |

+13

By irreducible I meant primitive there, sorry.

→ Reply

krijgertje

4 years ago, # ^ |

+10

I think I follow most of the editorial for problem I, except for several statements in the last paragraph:

Under given constraints $$$g$$$ is primitive (not divisible by any integer constant larger than $$$1$$$). It may be proven thus that if $$$g$$$ is primitive and $$$\lVert g\rVert =ab$$$ then $$$g$$$ may be uniquely (up to units) represented as $$$g=qp$$$ where $$$\lVert q\rVert =a$$$ and $$$\lVert p\rVert=b$$$. Due to this if we fix $$$\lVert q\rVert $$$ we may find actual $$$q$$$ as $$$gcd(g,\lVert q\rVert)$$$ because $$$q\bar q=\lVert q\rVert $$$.

Why is $$$g$$$ primitive (has it to do with the gcd of input being 1? if so how?). For the 'it may be proven'-statement, how can it be proven and how is it used? Maybe we need to do it repeatedly (needing $$$q$$$ and $$$p$$$ to be primitive as well) to create a unique factorization of $$$\lVert g\rVert$$$ (and therefore also of $$$g$$$ up to units)? Why does $$$q$$$ has to divide $$$g$$$? And lastly why has $$$gcd(g,\lVert q\rVert)$$$ to be equal to $$$q$$$?

Also, I don't see where the assumption mentioned by Benq comes up.

→ Reply

Benq

4 years ago, # ^ |

← Rev. 4 →

+23

Assuming that all input vectors are in the form $$$k\cdot q\cdot v\cdot \overline{q}$$$, we know that $$$k\cdot q$$$ divides each of them, so $$$k\cdot q$$$ must also divide their gcd $$$g$$$.

If some integer $$$x>1$$$ divides all coefficients of $$$g$$$ then it will divide all coefficients of any multiple of $$$g$$$. Since $$$g$$$ divides all the quaternions given in the input, $$$x$$$ cannot exist (actually, I'm not exactly sure how this works for $$$x=2$$$ since we can have half-integer coefficients).

I think my assumption shows that $$$\gcd(g,\lVert q\rVert)$$$ can't have norm greater than $$$\lVert q\rVert$$$, idk about the unique factorization though.

→ Reply

4 years ago, # ^ |

+20

I hope, Benq's comment clarifies a bit about why's $$$g$$$ primitive. Indeed if it's not then there is some common integer factor $$$x$$$ which would divide every point from input. $$$x=2$$$ can't work here as well because for all points it holds that $$$s=0$$$ and Hurwitz quternions either have all coordinates integer or all coordinates semi-integer.

Benq's assumption indeed helps it that $$$\gcd(g,|q|)$$$ doesn't have norm greater than $$$q$$$. On the other hand we know that primitive $$$g$$$ has a unique divisor $$$q$$$ with norm $$$|q|$$$ if this norm divides $$$|g|$$$, thus this $$$q$$$ should be the $$$\gcd$$$.

You may read on the uniqueness of factorisation for primitive quaternions in Conway's book On Quaternions and Octonions. You may also read Factorization of Hurwitz Quaternions for detailed proof in generic case.

→ Reply

4 years ago, # ^ |

← Rev. 4 →

+24

Here's a simpler mapping from transformations $$$v \mapsto \frac{1}{2} q \cdot v \cdot \bar{q}$$$ to $$$v \mapsto q \cdot v \cdot \bar{q}$$$ that doesn't involve expanding matrices:

Consider any integer rotation $$$v \mapsto \frac{1}{2} q \cdot v \cdot \bar{q}$$$ where $$$q$$$ is primitive. This maps integer vectors to integer vectors, so 2 divides $$$\lVert q \cdot \vec{e_x} \cdot \bar{q} \rVert = \lVert q \rVert^2$$$, and thus 2 divides $$$\lVert q \rVert$$$. Now, consider the factorization $$$q = q' p$$$ where $$$\lVert p \rVert = 2$$$; this exists by the factorization property of quaternions. Then, our rotation is the composition of $$$v \mapsto \frac{1}{2} p \cdot v \cdot \bar{p}$$$ and $$$v \mapsto q' \cdot v \cdot \bar{q'}$$$.

Note that there are exactly $$$24$$$ Hurwitz quaternions with norm $$$2$$$: $$$\pm 1 \pm i$$$ and symmetric with other terms. It's easy to check that the 24 possible transformations $$$v \mapsto \frac{1}{2} p \cdot v \cdot \bar{p}$$$ correspond to the 12 possible rotations of the unit octahedron $$$\pm \vec{e_x}, \pm \vec{e_y}, \pm \vec{e_z}$$$ which "flip the parity" of the faces (remember that $$$\pm p$$$ correspond to the same rotation). (The other 12 rotations are the 24 transformations $$$v \mapsto u \cdot v \cdot \bar{u}$$$ where $$$\lVert u \rVert = 1$$$.) Thus, in our problem, it's fine to discard the $$$v \mapsto \frac{1}{2} p \cdot v \cdot \bar{p}$$$ part of the transformation and use the equivalent $$$v \mapsto q' \cdot v \cdot \bar{q'}$$$.

In fact, there's a stronger statement for Hurwitz quaternions that $$$2 \mid \lVert q \rVert$$$ iff $$$\forall v: 2 \mid q \cdot v \cdot \bar{q}$$$. We can use this to get a tighter classification of the valid transformations:

Each transformation of the axes $$$\vec{e_x}, \vec{e_y}, \vec{e_z} \mapsto \vec{r_1}, \vec{r_2}, \vec{r_3}$$$ can be represented as a transformation of the form $$$v \mapsto k \frac{q \cdot v \cdot \bar{q}}{n}$$$ for a positive integer $$$k$$$, a primitive Hurwitz quaternion $$$q$$$, and $$$n = 2$$$ if $$$2 \mid \lVert q \rVert$$$ and $$$n = 1$$$ otherwise. Furthermore, these representations are unique up to the sign of $$$q$$$.

→ Reply

4 years ago, # ^ |

Wow, nice observation, thanks!

→ Reply

4 years ago, # ^ |

← Rev. 2 →

adamant also asked me about the case when the input coordinates have some nontrivial common factor $$$k^*$$$. It turns out that you can just divide all coordinates by $$$k^*$$$ and solve the reduced problem; equivalently, there exists some optimal solution of the form $$$v \mapsto k^* q v \bar{q}$$$.

Proof: consider any optimal solution $$$a_i = k q v_i \bar{q}$$$, where $$$q$$$ is a primitive Hurwitz quaternion with odd norm (see the characterization above), the $$$v_i$$$ are arbitrary Hurwitz quaternions, and $$$k$$$ is a positive integer. (The norm of this solution is $$$r = k \lVert q \rVert$$$.) Furthermore, among optimal solutions, pick one with maximal $$$k$$$. Obviously, $$$k \mid k^*$$$ because $$$k \mid a_i$$$ for all $$$i$$$. Assume for the sake of contradiction that $$$k < k^*$$$. Pick some prime $$$p \mid \frac{k^*}{k}$$$.

Case 1: $$$p \not\mid \lVert q \rVert$$$. Then, for all $$$i$$$, $$$p \mid \frac{a_i}{k} = q v_i \bar{q} \implies p \mid \bar{q}(q v_i \bar{q})q = \lVert q \rVert^2 v_i \implies p \mid v_i$$$. Thus, we can write $$$a_i = (kp) q \frac{v_i}{p} \bar{q}$$$ for all $$$i$$$, which is a solution with strictly higher norm ($$$r = kp \lVert q \rVert$$$).

Case 2: $$$p \mid \lVert q \rVert$$$. Let $$$q = q'h$$$ where $$$\lVert h \rVert = p$$$ (this exists by Hurwitz quaternion factorization). Then, $$$p \mid \frac{a_i}{k} = q' h v_i \bar{h} \bar{q'}$$$. Now, $$$q'h$$$ and $$$\bar{h}\bar{q'}$$$ are both primitive, and $$$\lVert h \rVert = p$$$, so we actually must have $$$p \mid h v_i \bar{h}$$$. This is an immediate result of Lemma 4.2 of Factorization of Hurwitz Quaternions. Intuitively, if a Hurwitz quaternion is a multiple of $$$p$$$, two "adjacent" terms with norm $$$p$$$ of its prime factorization must multiply to $$$p$$$ times a unit; in this case, that can't occur in $$$q'h$$$ or $$$\bar{h}\bar{q'}$$$ because those are primitive, so it must occur in the middle.

Thus, we can actually write $$$a_i = (kp) q' \frac{h v_i \bar{h}}{p} \bar{q'}$$$. This solution has the same norm as the original ($$$r = kp \lVert q' \rVert = k p\frac{\lVert q \rVert}{p} = k \lVert q \rVert$$$), but this has a larger $$$k$$$, which contradicts our maximality assumtion.

Hence, there must exist an optimal solution where $$$k = k^*$$$, so we can solve the problem for $$$a_i' = a_i / k^*$$$ and multiply the solution by $$$k^*$$$.

→ Reply

4 years ago, # ^ |

A quick followup: we can use this proof to almost classify all maximal solutions.

Let the primitive solution from above be $$$a_i = k^* q^* v_i^* \bar{q^*}$$$ (this is unique up to reordering/reflection of the axes, i.e. multiplication of $$$q$$$ by a unit). Then, the same proof shows that any other solution must be of the form $$$a_i = k q v_i \bar{q}$$$ where $$$q = q^* h$$$, $$$k = k^* / \lVert h \rVert$$$, and $$$v_i = \bar{h} v_i^* h / \lVert h \rVert$$$ for some Hurwitz quaternion $$$h$$$.

There are a few constraints on $$$h$$$. Obviously, we need $$$\lVert h \rVert \mid k^*$$$. Also, we want $$$q^* h$$$ to be primitive. The other constraint is the harder to satisfy: for all $$$i$$$, we need $$$v_i = \bar{h} v_i^* h / \lVert h \rVert = h^{-1} v_i^* h$$$ to be a Hurwitz quaternion. Equivalently, we need $$$v_i^* h = h v_i$$$ for some choice of $$$v_i$$$. This process of swapping terms is roughly "meta-commutation"; there's more information about meta-commutation at https://arxiv.org/abs/1307.0443. We roughly need $$$h$$$ to be a fixed point of meta-commuting by $$$v_i^*$$$ for all $$$i$$$ (more precisely, we should analyze each prime factor of $$$\lVert h \rVert$$$ separately, but the idea is the same).

If someone could finish this classification and do it algorithmically, we could get an algorithm for the original problem which doesn't involve brute forcing the norm. Maybe this is possible!

→ Reply

krijgertje

4 years ago, # ^ |

Thanks for your help. The pieces start coming together for me now. Some last questions / remarks.

It looks like it is important how exactly division (which is used inside gcd) is done: $$$round(b^{-1}a)$$$ works, but $$$round(ab^{-1})$$$ doesn't. How can we decide which one we need? Has it something to do with $$$q$$$ being a left factor of $$$g$$$?
You say 'for simplicity we will further work with vectors $$$a_i$$$ multiplied by $$$2$$$', but can't this cause $$$g$$$ to be non-primitive, resulting in the divisor of $$$g$$$ with norm $$$\lVert q \rVert$$$ being non-unique?
We don't need to worry about $$$k>1$$$, because then the gcd of input coordinates would be greater than $$$1$$$.
It doesn't matter to us that $$$q$$$ is only unique up to units, since that only changes the order and signs of $$$r$$$.
In your comment regarding the transformation being $$$q \cdot v \cdot \bar q$$$, I think $$$180^\circ$$$ rotation is only multiplying rows with $$$-1$$$, not swapping them. I think swapping is a $$$90^\circ$$$ (or $$$270^\circ$$$) rotation, which also multiplies one of the rows.
I think using $$$s'=\frac{s+x}{2},~ x'=\frac{x-s}{2},~ y'=\frac{y+z}{2},~ z'=\frac{z-y}{2}$$$ is even cleaner. If my calculations are correct, this only multiplies the second row with $$$-1$$$ and then swaps the second and third rows, which I think is just a $$$90^\circ$$$ rotation around the x axis.
$$$90^\circ$$$ rotation around an axis may also be represented as quaternion with unit norm (but with irrational coefficients), so I think your observation is still valid.

→ Reply

4 years ago, # ^ |

← Rev. 2 →

+18

Divisibility: You're right that the order matters, and is determined by whether $$$q$$$ is a left- or right- factor. I think we've been pretty wishy-washy with what we mean by divisibility/division. If you look at the link on factorizations, I believe they're more precise with talking about left-module/left-ideal versus right-module/right-ideal, though they're obviously symmetric. Here's one explanation for this problem that's a little more precise: we will try to find the right-gcd of $$$a$$$ and $$$b$$$, i.e. the largest $$$g$$$ so that $$$a = ga'$$$ and $$$b = gb'$$$. Then, in one step of the Euclidean algorithm, we'd like to find $$$a = bq + r$$$ so that $$$r = g (a' - b' q)$$$ is stil right-divisible by $$$g$$$. Thus, we want $$$a \approx bq \iff b^{-1}a \approx q$$$. (Update: apparently the convention is that $$$a = ga'$$$ means that $$$a$$$ is "right-divisible" by $$$g$$$.)
See my comment above for a bit of explanation about the factor of 2. You're right that multiplying by 2 doesn't quite do what we want.
Yup, $$$k > 1$$$ isn't important.
Yeah, we don't really care about uniqueness, but it's nice to know.
I think the cleanest view of the transformation is dividing by $$$1 + i$$$.
It's important to avoid irrational coefficients so that our claims about Hurwitz quaternions hold.

→ Reply

4 years ago, # ^ |

+10

Here's an alternative solution which does not involves caseworking on $$$\lVert q \rVert$$$ at all and is almost polynomial time.

Let $$$g = \operatorname{right-gcd}_i(a_i)$$$.

Consider any valid solution $$$a_i = q v_i \bar{q}$$$. Then, we can make a few observations:

$$$q$$$ must right-divide each of the $$$a_i$$$, so $$$q$$$ right-divides $$$g$$$, i.e. $$$g = qh$$$ for some $$$h$$$.
$$$v_i = q^{-1} a_i \bar{q}^{-1}$$$ is an integer, i.e. $$$\lVert q \rVert^2 \mid \bar{q} a_i q$$$. Also, $$$g$$$ is a right-multiple of $$$q$$$, so $$$\boxed{\lVert q \rVert^2 \mid \bar{g} a_i g}$$$.
$$$a_i = q v_i \bar{q}$$$, so $$$\boxed{\lVert q \rVert^2 \mid \lVert a_i \rVert}$$$.

It turns out that these conditions are necessary and sufficient when $$$g$$$ is primitive (as in this problem). The proof of this involves the observation that the $$$a_i$$$ are pure-imaginary, so if $$$h$$$ right-divides $$$a_i$$$, then $$$\bar{h}$$$ left-divides $$$\bar{a_i} = -a_i$$$, as well as some analysis about primitive Hurwitz quaternions.

Thus, the solution is as follows:

For a Hurwitz quaternion $$$q$$$, let $$$\operatorname{gid}(q)$$$ be the greatest integer divisor of $$$q$$$, i.e. the GCD of the coordinates of $$$q$$$. This is easy to evaluate.

Compute $$$g = \operatorname{right-gcd}_i(a_i)$$$.
Compute $$$v = \gcd(\gcd_i(\lVert a_i \rVert), \gcd_i(\operatorname{gid}(\bar{g} a_i g)))$$$. To avoid integer overflow, note that $$$g$$$ left-divides $$$a_i$$$, so $$$\bar{g} a_i = \lVert g \rVert (g^{-1} a_i)$$$. Thus, we can compute $$$v = \gcd(\gcd_i(\lVert a_i \rVert), \lVert g \rVert \cdot \gcd_i(\operatorname{gid}((g^{-1} a_i) g)))$$$
Now, compute the maximum $$$r$$$ such that $$$r^2 \mid v$$$. Unfortunately, there's no known way to do to find the square-free component of $$$v$$$ which is faster than prime-factorizing $$$v$$$; thus, we do this with either trial division up to $$$\sqrt[3]{v}$$$ or via a fast factorization algorithm.
Finally, compute $$$q = \operatorname{right-gcd}(g, r)$$$. As above, $$$\lVert q \rVert = r$$$.
Output $$$r^2$$$, $$$qi\bar{q}$$$, $$$qj\bar{q}$$$, and $$$qk\bar{q}$$$.

Let $$$G$$$ be the maximum norm of the $$$\lVert a_i \rVert$$$. Then, $$$\operatorname{right-gcd}$$$ takes $$$O(\log(G))$$$ time, so the runtime of this algorithm is $$$O(n \log(G) + T_{\operatorname{square-free}}(G))$$$, where $$$T_{\operatorname{square-free}}(n)$$$ is the time to find the square-free component of $$$n$$$. Trial division gives $$$T_{\operatorname{square-free}}(G) = G^{1/3}$$$ runtime, while factoring via Pollard's rho gives $$$T_{\operatorname{square-free}}(G) = G^{1/4}$$$ expected time.

→ Reply

4 years ago, # ^ |

+10

Here's a proof the solution. It suffices to prove the following:

Claim: [Sufficiency for a single prime] Consider any prime $$$p$$$ and Hurwitz quaternion $$$q$$$ with $$$\lVert q \rVert = p$$$. Also, consider any primitive quaternion $$$g$$$ such that $$$q$$$ right-divides $$$g$$$, and any pure-imaginary Hurwitz quaternion $$$a$$$ such that $$$p^2 \mid \bar{g} a g$$$ and $$$p^2 \mid \lVert a \rVert$$$. Then, $$$q^{-1} a \bar{q}^{-1}$$$ is a Hurwitz quaternion, i.e. $$$p^2 \mid \bar{q} a q$$$.

This claim suffices because we can repeatedly apply the claim and divide out $$$q$$$, i.e. replace $$$a' = q^{-1} a \bar{q}^{-1}$$$ and $$$g' = q^{-1} g$$$. It's easy to verify that the original conditions indeed shrink the maximum possible norm by a factor of $$$p = \lVert q \rVert$$$, so this iteration works.

To prove this claim, we will use the following powerful lemma about prime factorizations of Hurwitz quaternions. (This is Lemma 4.2 from Factorization of Hurwitz Quaternions.)

Lemma: Consider a prime $$$p$$$ and Hurwitz quaternions $$$a$$$,$$$b$$$,$$$c$$$ such that $$$p = \lVert b \rVert$$$. Then, $$$p \mid abc$$$ implies $$$p \mid ab$$$ or $$$p \mid bc$$$ (the converse is obviousyly true too).

Proof of lemma: Consider any $$$abc$$$ such that $$$p \mid abc$$$. Let $$$g$$$ be the right-gcd of $$$\bar{b}$$$ and $$$c$$$, with $$$\bar{b} = gx$$$ and $$$c = gy$$$. Then, $$$\lVert g \rVert \mid \lVert b \rVert = p$$$.

If $$$\lVert g \rVert = p$$$, then $$$\bar{b} = gx$$$ implies $$$x$$$ is a unit. Thus, we can write $$$bc = bgy = b(\bar{b}x^{-1})y = p \cdot x^{-1}y$$$, so $$$p \mid bc$$$.

Otherwise if $$$\lVert g \rVert = 1$$$, by the extended Euclidean algorithm, we can write $$$\bar{b}s + ct = g$$$ for some $$$s$$$ and $$$t$$$. Thus, $$$ab(\bar{b}s + ct) = abg \implies \lVert b \rVert as + abc t = abg$$$. $$$\lVert b \rVert = p$$$, and $$$p \mid abc$$$, so $$$p \mid abg$$$. $$$g$$$ is a unit, so $$$p \mid ab$$$, as desired.

Thus, we have proven the lemma.

In essence, if you have $$$p \mid h_1h_2h_3\cdots$$$, the part that "generates" the factor of $$$p$$$ cannot jump over any prime factors of norm $$$p$$$; it must come from two "adjacent" ones.

We're now ready to prove our original claim.

Proof of claim: First, let $$$g = qh$$$. Note that $$$p^2 \mid \lVert a \rVert$$$. We will casework on whether $$$p \mid a$$$ or not.

Case 1: $$$p \mid a$$$. Then, note that $$$p^2 \mid \bar{g} a g \implies p \mid \bar{g}\frac{a}{p}g = \bar{h} \bar{q} \frac{a}{p} q h$$$. Then, $$$\bar{h}\bar{q}$$$ is primitive and $$$\lVert \bar{q} \rVert = p$$$, so by the lemma, $$$p \mid \bar{q} \frac{a}{p} q h$$$. Also, $$$qh$$$ is primitive and $$$\lVert q \rVert = p$$$, so applying the lemma again, $$$p \mid \bar{q} \frac{a}{p} q$$$. Thus, $$$p^2 \mid \bar{q} a q$$$ and $$$q^{-1} a \bar{q}^{-1}$$$ is Hurwitz as desired.

Case 2: $$$p \not\mid a$$$. Then, $$$p^2 \mid \lVert a \rVert$$$, so we can write $$$a = xyz$$$ where $$$\lVert x \rVert = \lVert z \rVert = p$$$.

Now, $$$q$$$ right-divides $$$a$$$, so $$$p \mid \bar{q} a = \bar{q} xyz$$$. Once again, by the lemma, $$$\lVert x \rVert = p$$$ and $$$p \not\mid xyz$$$, so $$$p \mid \bar{q} x$$$.

Also, $$$a$$$ is pure imaginary and $$$q$$$ right-divides $$$a$$$, so $$$\bar{q}$$$ left-divides $$$\bar{a} = -a$$$, so $$$\bar{q}$$$ left-divides $$$a$$$. Thus, we have $$$p \mid a \bar{\bar{q}} = xyz q$$$. $$$\lVert z \rVert = p$$$, and $$$p \not\mid xyz$$$, so $$$p \mid zq$$$.

Thus, we can write $$$\bar{q} a q = \bar{q}xyzq = p^2 \cdot \frac{\bar{q}x}{p} y \frac{zq}{p}$$$, so $$$p^2 \mid \bar{q} a q$$$ and $$$q^{-1} a \bar{q}^{-1}$$$ is Hurwitz as desired.

Thus, our proof is complete.

→ Reply

LJF007

4 years ago, # ^ |

← Rev. 2 →

How to define the right-gcd of quaternion? I was confused by it

→ Reply

4 years ago, # ^ |

https://codeforces.me/blog/entry/79731?#comment-658311 has a definition.

→ Reply

4 years ago, # |

+672

By the way it's my meme.

→ Reply

babu1998

4 years ago, # ^ |

I did not understand it

→ Reply

4 years ago, # ^ |

Mojang added many shit mobs/etc to Minecraft(specially bees), and ruined it. I'm pointing out that Antontrygub's profile is a bee, and . . .

→ Reply

shiftyblock

4 years ago, # |

what happened to "doomsday" and tester comments :O

→ Reply

A_Gentle_Name

4 years ago, # |

+20

tricky Questions!!

→ Reply

4 years ago, # |

← Rev. 3 →

+17

problem C — summing all values of consecutive differences and checking if its greater than zero passes the system tests, I don't know whether its based on some proof and is correct or its wrong and bad system tests that let it pass. Any help will be appreciated.!

link to solution

→ Reply

Kuroni

4 years ago, # ^ |

+55

Not wrong. $$$a_2 - a_1 + a_3 - a_2 + a_4 - a_3 + ... + a_n - a_{n - 1} = a_n - a_1$$$. $$$a_n - a_1 > 0 \leftrightarrow a_n > a_1$$$, which is the same as the tutorial.

→ Reply

4 years ago, # ^ |

+35

thanks

→ Reply

rego97

4 years ago, # ^ |

+29

I'm just curious how people arrive to solutions like that when they don't have an idea whether it is correct or not.

→ Reply

4 years ago, # ^ |

just observed from the test cases, don't know how that happened.I am just starting with cp.

→ Reply

rego97

4 years ago, # ^ |

That's understandable. Although one must be careful with sample test cases. In many problems they are intentionally misleading, as I realized, especially in geometry problems.

→ Reply

4 years ago, # ^ |

Thanks for the advice , I prefer doing things after proving most of the times but sometimes I cant prove and get a solution then I go for observation.

→ Reply

IcantComeUpWithOrigName

4 years ago, # ^ |

+28

Sometimes it feels like someone telepatically gives me random hints.

→ Reply

iit_yt_28

4 years ago, # ^ |

Or Maybe you are John Wick of Coding. #QuesKiller

→ Reply

erekle

4 years ago, # ^ |

Your name is quite original.

→ Reply

Hz_

4 years ago, # ^ |

← Rev. 3 →

Because they get encouraged by seeing "Accepted" or "Pretests passed" and also positive rating changes.

But it is sure that the people who want to learn and to find out the proof of problems not always do that (i.e.Solution without proof).

→ Reply

-is-this-fft-

4 years ago, # ^ |

Yeah but how do they even come up with that? Like does your brain just generate random algorithms and you type them up?

→ Reply

dan_nil

4 years ago, # |

https://codeforces.me/contest/1375/submission/85969397 can u please tell me what's going wrong in this??

→ Reply

AnonySharma

4 years ago, # ^ |

This permutation can be reduced to a single element, but your code returns "NO". Check your code against it and myabe that would resolve the issue.

Test Case

→ Reply

vitux

4 years ago, # |

+176

Extremely liked problems C & F, thanks a lot for such a nice trolling!

→ Reply

confusedman

4 years ago, # ^ |

Could you give an intuition for how you came up with a solution for F?

→ Reply

towrist

4 years ago, # ^ |

I solved it myself during practice :P, so I can:

First of all, I noticed that the sample contained "First" as the optimal answer. If the sample is correct, this means that with all possibilities, First can force-win this game, regardless of the moves of the interactor (second player). So I took it as a working hypothesis that the First Player can always win.

It is immediately obvious that just before the winning move of the first player, the sequence looks like $$$a$$$, $$$a+d$$$, $$$a+2d$$$ and the number that the first player outputs is $$$d$$$, and the second player has just updated the pile with $$$a+2d$$$ stones, so he can't do it again. With some tinkering (and a bit of luck), you can find out that the magic number is $$$2c-(a+b)$$$ :)

→ Reply

Mikasa

4 years ago, # |

Thanks for the interesting round and editorial!!! now I can solve the problem e, f

→ Reply

https://codeforces.me/contest/1375/submission/85979406

4 years ago, # |

this is my solution for D which fails in tc 2 because my resultant array is 0 1 2 3 4 5 7 and not 0 1 2 3 4 5 6 in test number 2 if there is any other mistake please inform me ....thanks ....pretty good contest and kudos to the problem setters

→ Reply

dorijanlendvaj

4 years ago, # ^ |

0653443 -> 0153443 -> 0123443 -> 0123453 -> 0123463 -> 0123465

→ Reply

dhruv111

4 years ago, # |

← Rev. 3 →

-23

[deleted]

→ Reply

joseacaz

4 years ago, # ^ |

+22

What's the difference with the solution described in the editorial?

→ Reply

dhruv111

4 years ago, # ^ |

← Rev. 2 →

-17

[deleted]

→ Reply

sinnersneversleep

4 years ago, # |

Why so many wrong submissions for C even by red coders.

→ Reply

nagaraj41

4 years ago, # ^ |

-15

It was too simple for a C problem. (ig)

→ Reply

NiteshSharma5

4 years ago, # ^ |

NO it wasn't too simple, the solution might be 2 lines of code where you don't even need to store the array values and require only the first and last values to answer the question but it was a tricky in which even some of the the red coders have submitted wrong submissions.

→ Reply

nagaraj41

4 years ago, # ^ |

-6

I meant the implementation of it, not the problem itself. Lol i couldn't solve it during contest either.

→ Reply

kushb30

4 years ago, # |

← Rev. 4 →

-148


~~~~~
There also exists O(n) solution for d
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
using namespace __gnu_pbds;
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define tf(x) get<0>(x)
#define ts(x) get<1>(x)
#define tt(x) get<2>(x)
#define endl '\n'
#define F first
#define S second 
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define tup tuple<int,int,int>
#define ve vector <int>
#define vep vector<pii >
#define mod 1000000007
#define maxn 2e5+5
#define ld long double
#define in insert
#define fr(i,a,b) for(int i=a;i<b;i++)
#define forn(i,n) for(int i=0;i<n;i++)
#define fora(m) for(auto it:m)
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL); 

void solve() {
	int n;
	cin>>n;
	int a[n];
	forn(i,n) cin>>a[i];
	map <int,int> m;
	ve v;
	forn(i,n) {
		if(a[i]==n) v.pb(i);
		else {
			if(!m[a[i]]) m[a[i]]=i+1;
			else v.pb(i);
		}
	}
	int b[n];
	forn(i,n) b[i]=-1;
	fora(m) b[it.S-1]=it.F;
	ve aux;
	fora(m) aux.pb(it.F);
	sort(all(aux));
	int l=0,r=0;
	if(aux.size()==0) aux.pb(-1);
	forn(i,n) {
		if(l==aux.size() || i!=aux[l]) {
			b[v[r]]=i;
			r++;
		}
		else l++;
	}
	set <int> s;
	forn(i,n) 
		if(b[i]!=i) {
			s.in(i);
		}
	int curr=n;
	l=-1;
	if(s.size()!=0) l=*s.begin();
	 while(!s.empty()) {
	 	int tmp=b[l];
	 	b[l]=curr;
	 	v.pb(l);
	 	if(s.find(l)!=s.end() )s.erase(l);
	 	l=tmp;
	 	curr=tmp;
	 	if(curr==n and s.size()!=0) l=*s.begin();
	 }
	 if(l!=n and l!=-1) v.pb(l);
	 cout<<v.size()<<endl;
	 fora(v) cout<<it+1<<" ";
	 cout<<endl;
}
signed main() {
	IOS
	int t=1;
	cin>>t;
	while(t--) {
		solve();
	}
	return 0;
}

→ Reply

bestial-42-centroids

4 years ago, # |

Thank you very much for this round :p

→ Reply

tri_e

4 years ago, # |

+11

nearly 21000 participants registered and only about 8000 solved problem A so either participants are becoming too much conscious about their rating that they don't submit if they didn't solve problem A fast or problems were that tough but i don't think A and B were tough.so its actually the former point

→ Reply

AnandOza

4 years ago, # ^ |

+42

Wow, that's a much smaller ratio than I expected.

The other factor is that registration is open for days ahead of time, so frequently people (myself included) will Register "just in case" because it's much better to register & not participate than to want to participate but forget to register.

→ Reply

YaaKuZaa

4 years ago, # ^ |

+22

Another shirt color change, nice!!

→ Reply

R-d-G

4 years ago, # ^ |

+15

It also depends on initial approach... if it goes in wrong direction initially..you end up taking a lot of time on a question... like I thought of a lot of nonsense in C.. but the solution is simple .. still the way I solved C ..is more time consuming and lengthy as compared to solution ..

→ Reply

brezhart

4 years ago, # ^ |

Yes! Div2AB hatters don't understand, that keeping first problem easy (or seems to be easy) is key for right rating correlation.

→ Reply

back_to_code

4 years ago, # |

← Rev. 2 →

Another way to look Ques C:

If largest in present array is at position 1 or smallest is at position n, then it is not possible.

The final logic might be same but this one is easy to visualise or interpret. If you have smallest element at the rightmost spot or largest at leftmost spot you can never get they final array

Now largest is n and smallest is 1, start from either largest and smallest and check above condition.

→ Reply

raja_11sep

4 years ago, # ^ |

→ Reply

back_to_code

4 years ago, # ^ |

Here

The final logic might be same but this one is easy to visualise or interpret. If you have smallest element at the rightmost spot or largest at leftmost spot you can never get they final array

cnt stores index of each number ( from i to n )

Now we know that number goes from 1 to n , so we iterate from 1 to n ( small to large )
During every iteration , if current number if at the rightmost spot, then you cannot convert this array , else continue.

→ Reply

foxface_ap

4 years ago, # |

I did C in different way:

for(int i=0;i<n-1;i++)
       {
           sum=sum+(a[i+1]-a[i]);
       }
       if(sum<0)
       cout<<"NO\n";
       else
       cout<<"YES\n";

Anyone else who used this logic??

→ Reply

Kuroni

4 years ago, # ^ |

Here I think.

→ Reply

foxface_ap

4 years ago, # ^ |

Ohh yes, thanks for the explaining.

→ Reply

Omer223

4 years ago, # ^ |

It's exactly the same thing, notice that every element cancels out except for the first and the last but interesting nonetheless

→ Reply

saurabh_129

4 years ago, # |

what is the significance of this line in question B:"exactly k of its neighboring cells have a number greater than 0 written on them."

→ Reply

Yash2000

4 years ago, # ^ |

It means that if a cell has a number k then that implies that exactly k neighbors of that cell are non zero.

→ Reply

yash1402_

4 years ago, # ^ |

It says that out of 4 possible neighbours, there should be only k neighbours who have number > 0.

→ Reply

Hisham_hates_graphs

4 years ago, # |

keep make like this announcements

they keep Cowards away

→ Reply

souvenir_vayne

4 years ago, # |

+23

Well, I see that those testers comment were not lying, tho

→ Reply

4 years ago, # |

A crazy $$$\textbf{D&C}$$$ solution for A :

Don't look at it for too long

#include <bits/stdc++.h>

using namespace std;

#define fios        ios::sync_with_stdio(false), cin.tie(), cout.tie();
#define fr          first
#define sc          second
#define all(v)      v.begin(), v.end()
#define scan(a, n)  for(int i = 0; i < n; i++)cin >> a[i];
#define print(a, n) for(int i = 0; i < n; i++)cout << a[i] << ' '; cout << '\n';

typedef long long ll;
typedef pair<int, int> pt;

const int MN = 3e5+7;

int a[MN], n;

void inp(){
    cin >> n;
    scan(a, n);
}

int f(int l, int r){
    if(l == r)return 0;
    int sw = 1, ssw = 1;
    for(int i = l+1; i <= r; i++)if(a[i] < a[i-1])sw = 0;
    for(int i = l+1; i <= r; i++)if(a[i] > a[i-1])ssw = 0;

    if(sw == 1 || ssw == 1){
        for(int i = l; i <= r; i+=2)a[i] = -a[i];
        return ((r-l)&1);
    }

    int ii = -3;
    for(int i = l+1; i < r; i++){
        if(a[i] >= a[i-1] && a[i] >= a[i+1]){
            ii = i;
            break;
        }
    }
    if(ii == -3){
        for(int i = l; i <= r; i+=2)a[i] = -a[i];
        return ((r-l)&1);
    }
    int le = f(l, ii-1), re = f(ii+1, r);

    if(abs(le+re) > 1){
        for(int i = l; i < ii; i++)a[i] = -a[i];
        return 0;
    }
    return le+re;
}

void slv(){
    for(int i = 0; i < n; i++)a[i] = abs(a[i]);
    f(0, n-1);
    print(a, n);
}

signed main()
{
    int t = 1;
    cin >> t;
    while(t--){
        inp();
        slv();
    }
    return 0;
}

→ Reply

_pastor_

4 years ago, # ^ |

what D&C means?

→ Reply

4 years ago, # ^ |

+25

Divide and Conquer, I solved A like that after 1 hour of struggling . . .

→ Reply

dv.jakhar

4 years ago, # ^ |

from which account?

→ Reply

4 years ago, # ^ |

+20

I'm a tester.

→ Reply

fkhjoy

4 years ago, # ^ |

+31

Now I can feel how these Round Feedback was compiled from the opinion of testers :p

→ Reply

abhinash6g

4 years ago, # |

Thanks for such a wonderful contest! Thank_u

→ Reply

Jarjit_sigh

4 years ago, # |

drunk coordinator

→ Reply

Devil

4 years ago, # |

+18

Thanks anthoctryhardO_o for this beautiful round!!

→ Reply

skittles1412

4 years ago, # |

+101

Welcome to the new era of AdHocForces

→ Reply

nobody_1

4 years ago, # |

← Rev. 2 →

https://codeforces.me/contest/1375/submission/86002430 I am not able to get where is my logic is going wrong for problem C? Logic: I have stored the first element of every increasing continuous sub-array(as it will be replaced by it only, when we will apply operations) in list(say A), except last element of array and then check whether any element greater then last element in list A, if no then ans is YES, otherwise NO. Please help anyone! Thank you.

→ Reply

pied-piper

4 years ago, # ^ |

3 6 5 2 1 4
Try this permutation. Answer should be YES while yours give NO.

→ Reply

shubhanshushekharp

4 years ago, # |

For problem C, I used stack, in which if a smaller element is there I will not push a larger element and is a smaller element comes I push it and try to empty the stack using larger number coming.. Can anyone tell where it fails..... my code..85979051

→ Reply

4 years ago, # ^ |

Using stack missed some cases this problem can be handled in adhog way try this-Link

→ Reply

ZCKevin

4 years ago, # ^ |

+10

It's ok to use a stack to solve the problem, but you need a different strategy .

Don't try to empty the whole stack, keep the first one there instead.

85954948

→ Reply

nkamzabek

4 years ago, # |

Typical adamant problem)

→ Reply

4 years ago, # |

Hi guys, As a beginner i faces a lot of problems understanding solution of problems I always taught that can there be some creative way of easily explaining solution, then i realizes the best was is by visual explanation

so i have prepared visual explanation and solution of problem A,B,C as i was able to get them under control

Links: -

Problem A

Problem B

Problem C

I have just started with this i hope it will be helpful to lot of beginners and i will also improve my explanation skills as we proceed in this new Journey

Hope it helps :) :) Waiting for valuable feedback :) :)

→ Reply

Rocker21

4 years ago, # ^ |

How can number of neighbours be 0 in B bro ?

→ Reply

https://codeforces.me/contest/1375/submission/86019209

4 years ago, # ^ |

In the question it is given that if a cell contains 0 then there is no constraint to it it will not make matrix not good In this context we can say that a cell with 0 can have 0 neighbors

→ Reply

niteshchaurasia30

4 years ago, # ^ |

Can you check where i am wrong?

→ Reply

Your text to link here...

4 years ago, # ^ |

You are setting value of f1 wrong We need to check each of 3 cases separately I.e corner>2 and side >3 and other >4 while setting f1 you can check the video in that we have check all 3 cases separately then your code will also be accepted

→ Reply

niteshchaurasia30

4 years ago, # ^ |

yeah got it. Thanks

→ Reply

low_

4 years ago, # |

Wow I got tricked on G :(

I didn't think G was that easy (in fact I thought of this solution 30 secs after I read it), but then instead thought of some crazy DP, and then gave up and didn't really try it...

→ Reply

shubhanshushekharp

4 years ago, # ^ |

What is your approach??

→ Reply

low_

4 years ago, # ^ |

It supposed to be simple DFS, but I thought it was some hardcore shit DP.

→ Reply

25dinmepaisax2

4 years ago, # |

+12

These days I dream of codeforces' contest with problems based on algorithms and data structures. DREAMS.

→ Reply

AM_I_Learning

4 years ago, # |

How to solve D for minimum number of operations?

→ Reply

vishalchaudhary1975

4 years ago, # |

can anyone tell me why it is not accepting

→ Reply

Thallium54

4 years ago, # ^ |

Your link doesn't work, try to use a submission link.

→ Reply

krishna_0_9

4 years ago, # |

+21

Appreciate the hard work that goes into making a problem. But it would be really great to see more problems related to data structures and algorithms. Now we can mostly find ad-hoc or else greedy problems. Most people solve upto C or D and it would be really interesting to have DSA problems in this range too. I hope you guys agree with this and relevant people can see this comment so we can see a change in future contests. I am sorry if my comment is inappropriate.

→ Reply

limabeans

4 years ago, # ^ |

It depends on your thought process, but I solved C and D with data structures.

→ Reply

krishna_0_9

4 years ago, # ^ |

I agree with you, but its rare to see problems that can be solved using only data structures or with the help of any algorithm. Using data structure to solve today's C is an overkill.

→ Reply

limabeans

4 years ago, # ^ |

I think there's many ways to arrive at C's solution, but one way is to simulate with stack, and then one may observe that first element needs to be less than last element.

So actually, the simpler solution is still inspired by data structures. Depending on the person, it may be faster to code the stack solution as opposed to thinking any longer about making any simplifying observations, especially when the stack simulation is obviously correct in one's mind.

→ Reply

kartik8800

4 years ago, # |

← Rev. 2 →

Here is my approach for Problem C(using stack) : https://youtu.be/xOFkewgFhjA

Let me know if you find this helpful :)

→ Reply

jainbro

4 years ago, # ^ |

Understood. Thanks for the video!

→ Reply

huikang

4 years ago, # |

← Rev. 2 →

I have not seen someone printing the matrix for B here, so this is how it looks like

2 3 3 3 3 2
3 4 4 4 4 3
2 3 3 3 3 2

If any part of the input matrix is larger than the above matrix, the result is "NO".

→ Reply

aficio.nado

4 years ago, # |

problem C, sum of differences of all consecutive numbers in the array equals (a[n]-a[1]).

[problem:C] 85966335

→ Reply

sayeed_1999

4 years ago, # |

-11

Can anyone believe todays problem C was just one if-else!!! :D

if(a[0]<a[n-1]) cout << "YES\n"; else cout << "NO\n"; The fuck!!

→ Reply

Arcane

4 years ago, # ^ |

+12

Yes. That is what a lot of people did.

→ Reply

TleTerror

4 years ago, # |

These days there is a trend of Adhoc problems on codeforces.

→ Reply

apoorva222g

4 years ago, # ^ |

-13

We need data structures and algorithms based problems.

→ Reply

Lolboyyyy

4 years ago, # |

Here's another (almost equivalent) solution for C.

It is easy to see that $$$a_1<a_n$$$ is a necessary condition. If $$$a_1>a_n$$$, no matter what we do, for the last two elements (let them be $$$a_i$$$ and $$$a_j$$$), we must have $$$a_1 \leq a_i$$$ and $$$a_j \leq a_n$$$, so $$$a_i>a_j$$$, which is not reducable. To prove its sufficiency, I devised the following algorithm :-

Take the smallest element in the permutation. Obviously, it will be $$$1$$$ initially. Let its position in the array be $$$i$$$ (note that it cannot be $$$n$$$ because then $$$a_1<a_n$$$ would not hold). I will use this element to delete every element to the right of $$$i$$$ except $$$a_n$$$. I can do this because by definition $$$a_i$$$ is the smallest so $$$a_i<a_{i+1}$$$ will always hold. Now my array is $$$a_1, a_2,... , a_{i-1}, a_i, a_n$$$. Here I will use $$$a_i<a_n$$$ to delete $$$a_i$$$. So, my array is $$$a_1, a_2,... , a_{i-1}, a_n$$$. Repeat this process until a single element remains.

→ Reply

iit_yt_28

4 years ago, # |

Can anyone please tell me why this approach is wrong or if the code is wrong. Please tell me I have no clue whatsoever regarding why I am passing the Test Case 1 and not 2. https://codeforces.me/contest/1375/submission/85968254 is the solution link.

→ Reply

skylinebaby

4 years ago, # ^ |

86013495 You forgot to check whether $$$a[i][j] > 4$$$

→ Reply

skylinebaby

4 years ago, # |

← Rev. 4 →

85986603

I am curious about the correctness of my submission in problem D

My approach is to eliminate those duplicate numbers from left to right, then to apply the algorithm introduced in the editorial, this is, to say that "the number of duplicated numbers" $$$+$$$ "the number of cycles" — "number of fixed points" $$$\leq n$$$

The approach might sound ridiculous at first glance, but I can't find any counter case. Even more surprisingly( or obviously?), there are a lot of cases that my algorithm needs exactly $$$2n$$$ operations.

For example, any $$$a_1, ..., a_n$$$ has the form $$$a_1 = a_2 = ... = a_n = n - 1$$$ will achieve the equality, and this is not the only case the equality holds.

For instance, consider the following case where $$$n = 7$$$,

$$$6, 4, 5, 5, 4, 6, 6 \Rightarrow 6, 4, 5, 0, 1, 2, 3$$$ has $$$3$$$ cycles and $$$4$$$ repeated numbers.

So, the problem is, is there any proof about this amazing fact? Or this is just simply wrong.

→ Reply

Maksim1744

4 years ago, # ^ |

+25

I don't count cycles of length 1

Let's color duplicate numbers with red, and others with blue. After removing duplicates, red numbers will form an increasing sequence, because after each step MEX increases.

Take one cycle. Let's prove that it cannot consist only of red numbers. Suppose it is. Let $$$i$$$ be the index of the last number in the cycle. Since it is the last number, $$$a[i] < i$$$. Since red numbers form an increasing sequence, and $$$a[i]$$$ and $$$i$$$ are both red, then $$$a[a[i]] < a[i]$$$. And $$$a[a[a[i]]] < a[a[i]]$$$, and so on. So, the first number in the cycle points to the left, which can't be true. Thus, each cycle has at least one blue number in it.

\begin{gather*} n — N_{red} = N_{blue} \geqslant N_{cycles}\\ n \geqslant N_{red} + N_{cycles}\\ N_{red} = N_{duplicates} \Rightarrow N_{duplicates} + N_{cycles} \leqslant n \end{gather*}

→ Reply

skylinebaby

4 years ago, # ^ |

Wow, I made it too complicated.

→ Reply

bit_2

4 years ago, # |

I have never ever seen a problem set like this.

→ Reply

KonomoriKanon

4 years ago, # |

+14

When I saw the tester comments I thought they were joking but now I know they weren't （

→ Reply

g0uravlathwal

4 years ago, # |

← Rev. 3 →

Question are really tricky. Even I did not able to solve a single Problem in first hour of contest. And thinking lot about problem I solved first four problems until the end of contest. The logics to solce problems are really tricky and unique logic.

→ Reply

4 years ago, # |

+33

A simpler explanation for problem E: We need to apply all inversion swaps, so we must keep other inversions when swap a pair. We can achieve this by swapping the pair whose corresponding array elements have smallest difference.

How to effectively find the pair? See tourist's submission: 85960652. In this submisison, it first squeezes array values to 0..n-1, then only swaps the pair whose corresponding difference is 1. Such pair always exists.

→ Reply

Rock2000

4 years ago, # ^ |

can you please explain a little bit more?

→ Reply

4 years ago, # ^ |

e.g. In [3, 1, 2], you should swap (3, 2) first. If you swap (3, 1) first, then you get [1, 3, 2], (1 2) is not a inversion while (3, 2) in original array is a inversion. It is invalid.

e.g. In [3, 2, 1], you can swap (3, 2) first or (2, 1) first. But you cannot swap (3, 1) first.

If we can swap the pair whose corresponding array elements have smallest difference, then we can keep all other inversions after swapping a pair. More precisely, given k and a[k], for all i < k and a[i] > a[k], we should swap the smallest a[i] with a[k] first.

→ Reply

QuitAfterPurple

4 years ago, # ^ |

why swapping the pair whose corresponding difference is 1 is answer? please explain a little bit more

→ Reply

cadugomes

4 years ago, # ^ |

The way I thought about problem E:

The main idea is that, since we must go through all inversions, we should start with the ones that put the last elements of the array in their correct positions, and then going on until the first element is in its place.

But since for the same position we may have to do more than one swaps that move elements there, in which order should we do it? The ideia is to move in increasing order of a[i]. This way, after we finish all the swaps that affect a position we guarantee that we have the largest number. Since we are moving through the array from the largest to the smallest position, then it's correct.

The following code does exactly that:

void run_test() {
    int n; cin >> n;
    vi a(n); trav(_a, a) cin >> _a;
    vector<tuple<int, int, int>> ip;
    rep(i, n) repa(j, i + 1, n) if(a[i] > a[j]) ip.eb(-j, a[i], i);
    sort(all(ip));
    cout << sz(ip) << endl;
    for(auto [j, x, i] : ip) cout << i + 1 << " " << -j + 1 << endl;
}

→ Reply

4 years ago, # ^ |

I understood it. You keep all inversions by moving in increasing order of a[i]. Your idea is naturally described. Great.

→ Reply

4 years ago, # ^ |

My idea is that if we can apply all inversion swaps, then the array should be non-decreasing because its number of inversion pairs is zero. So I struggled to keep other inversions when swap a pair.

→ Reply

varun_saini

4 years ago, # |

← Rev. 2 →

-16

Question number D can be solved in O(n). We can calculate the mex of the arr in the beginning only and try to place 0 to n-1 elements from left to right of the array and also store the frequency of every number from 1 to n. Then by using logic that which element you are replacing then you will be having two choices that the number you replaced was smaller than the previous mex or grater than the previous mex. If the number you replaced was lesser than current mex and its frequency was 1 then definitely new mex will be replaced number. In this way we have to travel the whole array once only for calculating mex. I have not solved it though

→ Reply

Pretest

4 years ago, # ^ |

+18

I checked your submissions for problem D. None of them got accepted. Did you solve D using your idea???

→ Reply

varun_saini

4 years ago, # ^ |

Sorry but actually not

→ Reply

pranay.agra

4 years ago, # |

← Rev. 2 →

For Div2D, I thought of a different approach which sounds logically correct to me, but it gives WA on tc2. Here is the submission 86000887. If someone could give a test case where this fails that would be helpful.

Algorithm Description: - 1) make all elements unique. This can be done by performing the MEX of the first n-1 elements, taking n-1 operations. - 2) make the last element equal to n. If there is an element already equal to n, perform MEX at that index, and then perform MEX on the last index. If there is no element equal to n, perform MEX on the last index. This guarantees that the elements are unique and the last element is equal to n in at most n+1 operations. - 3) Note we have n-1 spots but n numbers to choose from (0 to n-1 inclusive) since the last element has already been fixed. Therefore, at least one number between 0 to n-1 will be excluded from the array. Let us try all possibilities of exclusion. Suppose we are excluding the element 2 from our array. Then, our array needs to look like: 0 1 3 4 ... n. We will find the MEX of the current array, which must be somewhere between 0 and n-1 inclusive. The MEX will fill the corresponding index from the array above, indexing the array from 0 but decrementing the index if MEX is > 2. If MEX is exactly 2, then we will stop the simulation early and check for validity. Otherwise, we perform n-1 operations and then check for validity, for a total of 2n operations. I claim that some exclusion iteration will always produce a valid answer.

→ Reply

gfonn

4 years ago, # ^ |

I did exactly the same, but i struggled to get AC.

→ Reply

NiteshSharma5

4 years ago, # |

Problem D

how the author directly arrives at the conclusion that above algorithm will take at most 1.5n operations. Can someone elaborate?

→ Reply

kkdrummer

4 years ago, # ^ |

If you notice the case when all numbers from 0 to n-1 are present but not in sorted order . Moreover consider that it is a derangement(no number is at its appropriate position), then if you follow the algorithm in the editorial it will take you 2 moves for placing the first number , then one move for placing the second number , 2 moves for third number , one move for fourth number... so on and so forth , if you are trying to place the numbers greedily in increasing order. So one move for n/2 elements and two moves for n/2 elements which is 1.5n. I think this is how he arrived at the conclusion, solving the worst case with the greedy(best) approach.

→ Reply

AlwaysACoder

4 years ago, # |

← Rev. 2 →

+18

Another approach for G:

We can have only one node as the centre node in the star graph. Let's find for each vertex the minimum cost of building the star graph if it was the centre node.

Let's initially root the tree at node $$$1$$$ and define $$$dp[u]$$$ the minimum cost to convert the subtree of node $$$u$$$ to star graph. Therefore, $$$dp[u]$$$ can be calculated as:

$$$dp[u] = \sum_{v \in c[c[u]]} 1 + dp[v]$$$

here $c[u]$ denotes children of node $$$u$$$ and $$$c[c[u]]$$$ means grandchildren of node $$$u$$$. Now, $$$dp[1]$$$ stores the minimum cost of building a star graph for node $$$1$$$. Now, we can simply do a dfs on the tree and on the go update the $$$dp$$$ values of the adjacent nodes.

Submission

→ Reply

PrantaSaha

4 years ago, # |

Is there any way to recompute MEX in less than O(n) time?? Problem D.

→ Reply

pprockys

4 years ago, # ^ |

← Rev. 2 →

+32

You can use unordered_map and set to find mex. I have solved it using this method only. You can see my solution Solution.

→ Reply

Jakube

4 years ago, # ^ |

← Rev. 2 →

+19

Take the boolean array that tells you which numbers are inside the current array, and build a Segment Tree with sum queries over it.

Then you can binary search for the current MEX in $$$O(\log n)$$$ (start at the root node, and whenever the left subtree is not full, go to that subtree). And you also make updates in $$$O(\log n)$$$.

But's it's not required to do so in problem D. Just a simple $$$O(n)$$$ approach is completely fine for that one.

→ Reply

Jakube

4 years ago, # ^ |

+38

Looks like I'm cracking the nut with a sledgehammer. @pprockys solution is actually a lot easier.

To explain it: just maintain a set with all numbers from 1 to $$$n+1$$$ that are currently NOT in the array. Then the MEX will simply be the smallest one of these, e.g. *set.begin(). This gives you the MEX in $$$O(1)$$$ time, and updates are also just $$$O(\log n)$$$.

→ Reply

Mike_Mirzayanov_Is_Pussy

4 years ago, # |

can someone explain the problem E editorial using examples say 3,2,2 ? .According to the editorial we swap (1,3) thus we get 2,2,3 .$$$a_1>a_2$$$ but $$$b_1=b_2$$$ .

→ Reply

aKILLL

4 years ago, # |

How to generally approach a problem like C as there were some key observations needed and to prove that the observation work requires a lot of time. I usually get lost in a dead-end in such type of problems.

→ Reply

spookywooky

4 years ago, # ^ |

You can check some edgecases. C is obviously about smaller/bigger element. What if smallest/biggest element is leftmost? What if smallest/biggest element is rightmost?

Even if you do not find the simplest solution that leads often to at least some solution.

→ Reply

clairvoyant

4 years ago, # |

For G, would the solution still be the same if in each operation we only delete the edge connecting a and b and add the edge connecting a and c?

→ Reply

sanskar111100

4 years ago, # |

https://codeforces.me/contest/1375/submission/86033992 Getting runtime error, don't know why!

→ Reply

clairvoyant

4 years ago, # ^ |

$$$0≤a_i≤n$$$, so the size of "temp" should be n+1

→ Reply

vezcraz

4 years ago, # |

Video for D: Replace MEX

→ Reply

ka16

4 years ago, # |

Can someone explain or give an idea on how to solve the problem E Inversion Swapsort? I don't quite understand the editorial above.

→ Reply

chengheichit

4 years ago, # |

← Rev. 2 →

Looking forward to AC4

→ Reply

827852427

4 years ago, # |

I thought the tutorial's method to D in the contest, but it wasnt enough.

I didnt konw what to do if the mex is exactly n. So, I just went to the other way and deviated futher from the right method lol.

And now I konw that if the mex in n, we can just change any unfixed point, what a nice and meaningful way to handle it! And also learn how to find the mex in $$$log(n)$$$ time, nice round!

→ Reply

60D9

4 years ago, # |

+22

antontrygubO_o Could you explain general way how to aproach problems like F? How did you come up with the solution?

→ Reply

enoone

4 years ago, # ^ |

← Rev. 2 →

+10

You can look at it backwards. The first player wins if there are two equal elements, knowing that you can think of the triplets (a,b,c) which can lead to the first player winning in one turn. After understanding that go one step further to 2 turns and so on. In this particular case you'll reach to the conclusion that first player can win regardless of the starting triplet in 3 turns. Not all problems like this will have same kind of solution, for some of them you may realize that all the winning positions for the first player share some common property, there also can be problems that this method will not work at all. Hope this helps.

→ Reply

sammyMaX

4 years ago, # ^ |

+61

Here are some observations I found helpful for F.

Consider the last move (the one that player 2 makes that leads to two piles having an equal quantity of stones). This move must have occurred on one of the two smaller piles; placing more stones on the largest pile will never make two piles equal in size. So if we have piles $$$a$$$, $$$b$$$, $$$c$$$, with $$$a<b<c$$$, the last move added $$$x$$$ stones such that $$$a+x=b$$$ or $$$b+x=c$$$. If you add $$$x$$$ to $$$c$$$ then clearly none of the piles are equal in size.

This also implies that $$$b-a=c-b$$$; in other words, $$$a, b, c$$$ form an arithmetic sequence right before the losing turn. Player 2 can't place the stones on $$$c$$$, and placing $$$x=b-a=c-b$$$ stones in either the smallest or middle pile both force a loss.

Our challenge as player 1 reduces down to making the pile sizes an arithmetic sequence (although not necessarily in order, like the piles could be $$$14, 26, 20$$$ and that's still fine) such that player 2 is prohibited from placing stones on the largest pile.

So let's assume we have some initial $$$a<b<c$$$ and pick $$$x$$$ such that whatever pile we add $$$x$$$ to, it becomes the biggest pile (thus prohibiting player 2 from putting more stones on it the next turn). So we want $$$b,c,a+x$$$ to be an arithmetic sequence, which gives us $$$x=2c-b-a$$$. It turns out this would also make $$$a,c,b+x$$$ an arithmetic sequence. The only case this doesn't solve is $$$a,b,c+x$$$ but as you can see in the official solution we can repeat this procedure and be done.

Granted, this whole approach glosses over the problem of figuring out player 1 has a winning strategy in the first place. The fact that you have 1000 turns and you can pick, for each test case, between player 1 and 2 makes things even trickier...it scared me off of the problem during the contest because I figured the solution would be much trickier (I guess same could be said of most problems this entire contest)

→ Reply

bb2211

4 years ago, # ^ |

Very well explained

→ Reply

stormshadow16

4 years ago, # |

can someone explain why a simple bubble sort for problem E is wrong answer? it will give u,v with au>av.

→ Reply

4 years ago, # ^ |

because the first two conditions of question are not met, only the third condition is satisfied

→ Reply

LRJf

4 years ago, # |

For problem E,could anyboy tell me why it's wrong when I just simple swap the biggest number each time .86083757

→ Reply

Aesir

4 years ago, # |

I should read F and G first Hmmmmm :((

→ Reply

4 years ago, # |

← Rev. 2 →

+20

Problem H segment tree details:

The basic idea is that instead of splitting the nodes by index ranges, we split the nodes by the array value ranges. This allows us to merge child node results with a single operation.

The values stored in each node of the segment tree are the indices whose array values are within some range $$$[lb, rb]$$$ and the map of subset IDs for each possible subsequence of the stored indices. These subsequences can be represented as a pair consisting of the leftmost index and rightmost index of the subsequence. For example, with array $$$3,7,1,5,2,4,6$$$ and range $$$[4,7]$$$, the node stores indices $$$2,4,6,7$$$. One possible subsequence pair would be $$$(4, 7)$$$ representing index sequence $$$4,6,7$$$ and subsequence $$$5,4,6$$$ in the array.

When querying on the range $$$[l_i, r_i]$$$ for a some node, we first get the longest subsequence that is within the range. This can be done using lower_bound() and upper_bound() on the stored indices. Then, if that subsequence already has a subset ID registered in the map, we return it. Otherwise, we query the left and right nodes without shrinking the $$$[l_i, r_i]$$$ range (since the nodes are split by array values).

If we were successfully able to get a subset ID from both the left and right nodes, we merge the two into a new subset. This is possible because all the left node array values are less than the right node array values. Once merged, we register the new subset ID in the node's subsequence map. If we only get one subset ID from either the left or right node, we register that instead.

Overall time complexity: $$$O(n \sqrt{q} \log n)$$$ (see proof in the replies)

My submission

→ Reply

lxc

4 years ago, # ^ |

← Rev. 3 →

The solution is inspiring! But the complexity isn't as low as O(q * log^2 n). In worst case, there could be O(min(n^2, q*n)) index sub-ranges over the course, each costing O(log^2 n) look-ups down the tree.

Thus I think time should be O(min(n^2 * log^2 n, q*n * log^2 n)). It's just that getting into that worse case is really hard either by random or manual input, so the answer is low enough to pass the 2.2*10^6 limit.

→ Reply

4 years ago, # ^ |

Do you mean $$$min(n^2, q)$$$ ranges? I'm not sure where the extra factor of $$$n$$$ comes from. But I do agree the runtime would be $$$O(n \log n + min(n^2, q) * \log^2 n)$$$ without that extra factor.

The $$$2.2*10^6$$$ limit is for the number of sets, which the editorial proves that it's bounded by $$$2n\sqrt{q}$$$. The runtime isn't related since every query could generate more than one set and the sets take O(1) space.

→ Reply

lxc

4 years ago, # ^ |

No I meant time is q*n*logn. Sorry the last sentence of my last reply is wrong. That's for space not related to time. But runtime wise, your qLog^2n is even smaller than the output size n*sqrt(q), e.g. if q=1E4 and n=1E6. That couldn't happen, right?

→ Reply

4 years ago, # ^ |

← Rev. 3 →

Ah right time can't be faster than space, my bad :)

Though I'm still confused how the runtime could be $$$O(n q \log^2 n)$$$. Do you mind explaining it further?

→ Reply

4 years ago, # ^ |

← Rev. 2 →

Nevermind, I think I have a proof for a more correct runtime of $$$O(n \sqrt{q} \log n)$$$.

Like the editorial, we have $$$n = 2^N$$$ and $$$q = 2^Q$$$. The total runtime would be:

$$$ \begin{align} & \sum_{i=0}^N 2^{N-i} \min(2^{2i}, 2^Q) \log(2^{i+1}) \\ & = \sum_{i=0}^N 2^{N-i} \min(2^{2i}, 2^Q) (i+1) \\ & \le N \sum_{i=0}^N 2^{N-i} \min(2^{2i}, 2^Q) \end{align} $$$

The $$$2^{2i}$$$ term is different from the set count because a full node could still be queried. However, once the parent node is full, then the queries will never reach the child. The extra log factor comes from the index lookups. For $$$i \le Q/2$$$:

$$$ \begin{align} & N \sum_{i=0}^{Q/2} 2^{N-i} 2^{2i} \\ & = N \sum_{i=0}^{Q/2} 2^{N+i} \\ & \le N * 2^{N+Q/2} \end{align} $$$

And for $$$i > Q/2$$$:

$$$ \begin{align} & N \sum_{i=Q/2+1}^N 2^{N-i} 2^Q \\ & \le N * 2^{N-Q/2} 2^Q \\ & = N * 2^{N+Q/2} \end{align} $$$

Combine the two:

$$$ \begin{align} & N * 2^{N+Q/2} + N * 2^{N+Q/2} \\ & = N * 2^{N+Q/2+1} \\ & = 2 n \sqrt{q} \log n \\ & = O(n \sqrt{q} \log n) \end{align} $$$

→ Reply

lxc

4 years ago, # ^ |

Perfect, and brilliant! I tried to prove it but didn't succeed :p This now explains why its a fast solution (and BTW tourist did it too 85990887, not sure if he proved it in his mind :D ).

Interestingly, I think this kind of resonates with my memory that in general $$$\sqrt n$$$-decomposition related problems can be solved by binary division algorithms too, like the classic range add-update-query problem which can be solved via both sqrt or segment trees. Not sure if there is a deeper reason behind that :)

→ Reply

4 years ago, # |

-16

any one explain me problem A , and approach in tutorial why is true?

→ Reply

4 years ago, # ^ |

+25

Spoiler

I just pasted editorial's explanation, because it perfectly answers to your questions("any one explain me problem A , and approach in tutorial why is true?"). Obviously this is not what you wanted to get, but rather what you asked for. You have read the editorial. You don't understand some part of it. Do you expect professor Charles Xavier to come, read your comment and mind, see which part of the editorial was unclear to you and help you? Do you expect someone to come and explain every microscopic thing which could have possibly not been clear to you? Don't be lazy and have some respect towards people who are going to help you. Spend more time writing your questions. Otherwise you won't get any help.

→ Reply

4 years ago, # ^ |

-8

sorry , but it's clear from my question that i'm a beginner and i tried and don't understood the editorial , and beside that the editorial just 2 line almost and i said why approach is true what do you need me specify??!!!

→ Reply

4 years ago, # ^ |

← Rev. 2 →

why approach is true

$$$a_{i + 1} \ge 0 \ge a_i$$$, and thus $$$a_{i + 1} \ge a_i$$$, for $$$i = 2, 4, \dots, n - 1$$$.
$$$a_{i + 1} \le 0 \le a_i$$$, and thus $$$a_{i + 1} \le a_i$$$, for $$$i = 1, 3, \dots, n - 2$$$.

Giving at least $$$\frac{n - 1}{2}$$$ of each, as desired.

what do you need me specify
OK, let me be more concrete. Up to which sentence do you understand the editorial? 'Cause (don't understood the editorial) when you don't specify which part is unclear to you, I can't think of something but quoting the editorial.

→ Reply

4 years ago, # ^ |

-11

why are you so angry ???!!!!!! , I have not forced anyone to help me, if you do not like my question you can ignore it and thank you for your generosity !

→ Reply

4 years ago, # ^ |

← Rev. 3 →

+18

I am not angry :) Grand_Master369, it's not like I don't like your question. I am quite sure that nobody will answer to it. I am trying to help. So, answer, please, up to which sentence did you understand the editorial? Which sentence was unclear?

→ Reply

4 years ago, # ^ |

ok , i'm sorry again

→ Reply

4 years ago, # ^ |

This branch of comments is too long, already. PM me, I'll explain to you.

→ Reply

4 years ago, # ^ |

if you could please tell me 312->1 3 2 -> 1 2 3 why is this not a correct option in problem E..thanks for efforts

→ Reply

4 years ago, # ^ |

I'd strongly suggest, to read the statement once again very attentively before reading the answer. The statement is very clear and unambiguous. Not to understand it, you must either have extremely low English knowledge or put 0 efforts before flooding the comment section with your quite stupid question or be dumb.

Spoiler

→ Reply

4 years ago, # ^ |

hey EmilConst thanks for replying

the way enoone responded and the way you are responding i won't point out what's wrong with you it's just your humbleness that reflects your own true self ; U see i am just a pupil as of now and people do make mistakes so if you don't have patience to deal with "stupid " questions or dumb people like me so please don't claim that you want to help as you did in above comments , because if this is what you say helping is , believe me it's more of an inferiority complex and demotivation what you are providing, rather than helping out . try to "help" less

→ Reply

4 years ago, # ^ |

U see i am just a pupil

Being pupil is about CP skills. What I was talking about is problem statement reading skill. You can read more about it in Um_nik's post.To understand the examples of this problem, you just needed to understand the statement. To understand that clear, unambiguous statement, you need basic English knowledge, some time spent reading the statement attentively and some brains. In other words not to understand it, you must either have extremely low English knowledge or put 0 efforts before flooding the comment section with your quite stupid question or be dumb. And I think that you didn't think enough before asking a question.

more of an inferiority complex and demotivation
Are you demotivated, because I told you can't read problem statements?

→ Reply

4 years ago, # ^ |

alright ..... was just messing srry

→ Reply

walleeva

4 years ago, # |

In Case Anyone Need Detail Explanation(Not a video tutorial) For D Here

→ Reply

4 years ago, # |

Can someone explain how to solve problem E. I tried to understand the editorial but could not get any idea.

→ Reply

Which part didn't you understand? :( :( :(

4 years ago, # ^ |

+11

→ Reply

4 years ago, # ^ |

← Rev. 2 →

Actually, all of it, how are they using permutation for the proof etc. I am looking for a simple solution which might be easier to understand and if there isn't any better solution then if someone could explain this editorial in simpler terms.

→ Reply

4 years ago, # ^ |

← Rev. 3 →

Here I add some details to the parts of editorial that I think aren't clear enough. If you still have questions, feel free to ask.

In this problem we are only interested in the relative order of $$$a[1],a[2]...,a[n]$$$, not their exact values. $$$a={2,1,3}$$$, $$$b={7,6,8}$$$, $$$c={5,2,9}$$$ are the same for us($$$a[2]<a[1]<a[3]$$$, $$$b[2]<b[1]<b[3]$$$, $$$c[2]<c[1]<c[3]$$$).
Permutation is easier to think of, because there are no equal elements in it.
After using pairs in the order $$$(pos_{a_n+1},n),(pos_{a_n+2},n),...,(pos_n,n)$$$, relative order of the first $$$n-1$$$ numbers $$$a[1],a[2],...,a[n-1]$$$ doesn't change. $$$a[n]=n$$$, so it is in its place. There are no more pairs including nth element. Taking hold of this three facts, we see that we can just "throw away" nth number and recursively the problem for the first $$$n-1$$$ numbers.

→ Reply

4 years ago, # ^ |

I see. this way we can always achieve the sorted array, but how to come up with such a solution during contest, I would never have thought in this way.

→ Reply

4 years ago, # ^ |

+30

It could be something like this. Lets do some swaps and put the maximal number in the end. Then recursively solve the problem for the first $$$n-1$$$ numbers. This is quite common idea. Now, how could we do this? If we want to recursively move to the first $$$n-1$$$ numbers, then we must have no more pairs including $$$n-1$$$(otherwise, how could we ignore nth element, and recursively move to the first $$$n-1$$$ ones). Lets look at an example:
$$$a = {2, 8, 3, 8, 1}$$$
We must do swaps $$$(1, 5), (2, 5), (3, 5), (4, 5)$$$ in some order, so that $$$8$$$ is in the end. Lets do it in some way, and see what happens to the first $$$n-1$$$ elements.
$$$swap(1, 5)$$$
$$$swap(2, 5)$$$
$$$swap(3, 5)$$$
$$$swap(4, 5)$$$
$$$b =$$$ {$$$1, 2, 8, 3, 8$$$} $$$=$$$ {$$$a[5], a[1], a[2], a[3], a[4]$$$}

We can see that $$$a[5], a[1], a[2], a[3], a[4]$$$ are cyclically shifted. If you do the swaps on a paper, you'll see, that $$$a_n, a_{i_1}, a_{i_2}, a_{i_3}, a_{i_4}...$$$ are shifted, where $$$i_1, i_2, i_3, i_4...$$$ are the positions we swaped with $$$a_n$$$

$$$swap(a_{i_1}, a_n)$$$
$$$swap(a_{i_2}, a_n)$$$
$$$swap(a_{i_3}, a_n)$$$
$$$swap(a_{i_4}, a_n)$$$
$$$...$$$

Now lets return to our $$$b =$$$ {$$$1, 2, 8, 3, 8$$$}. There is one inversion in $$$b$$$, which is $$$(3, 4)$$$, but in the original array $$$a$$$ the only inversion was $$$(2, 3)$$$, so we must swap $$$(2, 3)$$$. Thus recursively moving to the first $$$n-1$$$ numbers will be quite problematic. Lets try doing swaps in such a way, that inversions remain the same. In this subproblem, we see that exact values of elements aren't important, there relative ordering is. Thus, thinking about a permutation may be easier. In short, we must swap numbers in increasing order. It is described in the editorial.

→ Reply

4 years ago, # ^ |

Wow, this is really impressive, by the way , thank you for helping me and putting so much effort in writing this comment

→ Reply

mynk322.0

4 years ago, # ^ |

I think I am doing the same thing here 86300926 but getting a WA for 7th test case. Can you help?

→ Reply

4 years ago, # ^ |

← Rev. 2 →

There are quite some ways to debug one's code. Read it very attentively. Put assertions and submit. Write a test generator, a checker and stress test your solution(get a small counter-test). Your first WA7 submission was 1 hour ago. I am quite sure you didn't try all this options. You'd better go try this out, before seeking help in comments section. Debugging is quite important skill one shouldn't neglect.
mynk322.0 I added stress testing part to your code here.

counter test

3
69 69 0

→ Reply

mynk322.0

4 years ago, # ^ |

Thanks, I am clear with my logic and have implemented it correctly. But I think I am misunderstanding the problem. Giving it another read :)

→ Reply

4 years ago, # |

for question E , why can 312->1 3 2 -> 1 2 3 not be done for the first test case ?

→ Reply

enoone

4 years ago, # ^ |

In case of $$$a=[3,1,2]$$$ the pairs that form inversion are $$$(1,2)$$$ and $$$(1,3)$$$. In your second step you swap the 2nd and 3rd values of the array, which is not allowed because $$$(2,3)$$$ does not form an inversion in array $$$a$$$.

→ Reply

confusedman

4 years ago, # |

The solution for F in the editorial is pretty elegant, it would be pretty useful to know how one should think during a contest in order to come up with that solution?

→ Reply

4 years ago, # ^ |

← Rev. 2 →

try the example, and find out why the second player lost.

→ Reply

alon276

4 years ago, # |

+16

Did anyone else feel this was one of the best written contests? Also, I personally felt that all the problems, even if some unsolvable for me, are very fun to read and very fun to think about.

→ Reply

Nobody4931

4 years ago, # |

-8

a much easier solution to problem B is to set the corners of the grid to 2, the edges of the grid to 3, and all other inner elements to 4. it will always work.

print "NO" only if the element you are trying to change is more than what you are trying to change it to.

use this for reference if you need it: my code

→ Reply

enoone

4 years ago, # ^ |

That's the same solution as the one described in the editorial.

→ Reply

mynk322.0

4 years ago, # |

-9

Can someone tell me why I am getting wrong in problem E in the 7th test case? 86297939 .

→ Reply

chiragbaid7

4 years ago, # |

Your text to link here... I am getting WA for Problem C.Plz help

→ Reply