### MrDecomposition's blog

By MrDecomposition, history, 5 weeks ago, ,
Problem A
Problem B
Problem C
Problem D
Problem E
Problem F
Problem G
Problem H
Problem I

• +377

 » 5 weeks ago, # |   +303 You guys should've read problem I first, smh
•  » » 5 weeks ago, # ^ |   +27 86000122 You got a work to do;)
•  » » » 5 weeks ago, # ^ |   +43 Very interesting that they have a similar coding style. Probably just a coincidence.
•  » » » » 5 weeks ago, # ^ |   +12
•  » » » » » 5 weeks ago, # ^ |   -19 LOL
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   +13 I think the last paragraph of the I editorial assumes that if $x$ is primitive and $x$ divides $\lVert q\rVert$ then $\lVert x\rVert$ divides $\lVert q\rVert$. Is this true? (Also, Monogon's solution seems to assume that the transformation is in the form $v\to q\cdot v\cdot \overline{q}$ for some Hurwitz quaternion $q$?)
•  » » » 5 weeks ago, # ^ |   +13 I have not looked through the proofs, but I can confirm that my solution assumes the transformation is in that form, without the factor of $1/2$.
•  » » » 5 weeks 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).
•  » » » » 5 weeks 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?
•  » » » » » 5 weeks ago, # ^ |   +13 By irreducible I meant primitive there, sorry.
•  » » » » 5 weeks 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.
•  » » » » » 5 weeks 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.
•  » » » » » 5 weeks 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.
•  » » » » 5 weeks 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$.
•  » » » » » 5 weeks ago, # ^ |   +6 Wow, nice observation, thanks!
•  » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +8 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^*$.
•  » » » » » » 5 weeks ago, # ^ |   +8 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!
•  » » » » 5 weeks ago, # ^ |   0 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.
•  » » » » » 5 weeks 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.
•  » » » 4 weeks 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.
•  » » » » 4 weeks 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.
•  » » 5 weeks ago, # ^ |   -9
 » 5 weeks ago, # |   +672 By the way it's my meme.
•  » » 5 weeks ago, # ^ |   0 I did not understand it
•  » » » 5 weeks ago, # ^ |   0 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 . . .
 » 5 weeks ago, # |   +5 what happened to "doomsday" and tester comments :O
 » 5 weeks ago, # |   +20 tricky Questions!!
 » 5 weeks 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
•  » » 5 weeks 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.
•  » » » 5 weeks ago, # ^ |   +35 thanks
•  » » 5 weeks 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.
•  » » » 5 weeks ago, # ^ |   +7 just observed from the test cases, don't know how that happened.I am just starting with cp.
•  » » » » 5 weeks ago, # ^ |   +6 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.
•  » » » » » 5 weeks ago, # ^ |   +1 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.
•  » » » 5 weeks ago, # ^ |   +28 Sometimes it feels like someone telepatically gives me random hints.
•  » » » » 5 weeks ago, # ^ |   +5 Or Maybe you are John Wick of Coding. #QuesKiller
•  » » » » 5 weeks ago, # ^ |   +3 Your name is quite original.
•  » » » 5 weeks ago, # ^ | ← Rev. 3 →   0 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).
•  » » » » 5 weeks ago, # ^ |   +2 Yeah but how do they even come up with that? Like does your brain just generate random algorithms and you type them up?
•  » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Well, they come up with that by finding the answer to some cases. They take some test cases and think what if the answer if the case is like this, like that and finally come up with a solution that may be passed all the system tests.Even sometimes for very easy problems, they guess like "oh yes, the answer may be (n/2) or the answer is "YES" if (n&1)" and something like that and submit for taking less time to that problems.etc.Of course, I also do it sometimes.
•  » » 5 weeks ago, # ^ |   0 eventually as you sum up the differences you are actually justing subtracting last element from first which is the actual solution! a — b + b- c + c -d = a -d
 » 5 weeks ago, # |   0 https://codeforces.com/contest/1375/submission/85969397 can u please tell me what's going wrong in this??
•  » » 5 weeks ago, # ^ |   0 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 Case161 2 3 6 5 4
 » 5 weeks ago, # |   +176 Extremely liked problems C & F, thanks a lot for such a nice trolling!
•  » » 5 weeks ago, # ^ |   0 Could you give an intuition for how you came up with a solution for F?
•  » » » 4 weeks ago, # ^ |   0 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)$ :)
 » 5 weeks ago, # |   0 Thanks for the interesting round and editorial!!! now I can solve the problem e, f
 » 5 weeks ago, # |   0 https://codeforces.com/contest/1375/submission/85968188 why this is getting TLE ? I think the complexity in O(nlogn) which is enough :/
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 My solution using BruteForce with stack to do simulation, and the time complexity is $O(N)$.Let's define $x$ is a element you want to push into stack.If the top element in stack smaller than $x$, we pop all the top which small then $x$, and record the last-pop element, and finally we can put the last-pop element into stack, mean we remove the number $x$.If top element is bigger then $x$, we push $x$ into stack.85967462
 » 5 weeks ago, # |   0 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
•  » » 5 weeks ago, # ^ |   +1 0653443 -> 0153443 -> 0123443 -> 0123453 -> 0123463 -> 0123465
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 hey dorijanlendvaj thanks for pointing out this worked only thing I changed was changing a[i] in issorted function to i+1,
 » 5 weeks ago, # | ← Rev. 3 →   -23 [deleted]
•  » » 5 weeks ago, # ^ |   0 did same it worked like charm
•  » » 5 weeks ago, # ^ |   +22 What's the difference with the solution described in the editorial?
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   -17 [deleted]
 » 5 weeks ago, # | ← Rev. 2 →   0 I can't find what's wrong with my code. Please help me to find out the wrong.#B https://codeforces.com/contest/1375/submission/85999401
•  » » 5 weeks ago, # ^ |   0 you miss the cases (i==m and j==1) or (i==n and j==1) while checking the condition
•  » » 5 weeks ago, # ^ |   0 You haven't checked for a[n][1] > 2 or a[1][m] > 2 here also f = 0 (i.e. all the four corners should have value 2), thats why your code is giving WA.
•  » » » 5 weeks ago, # ^ |   0 Got it.Thank You..
•  » » 5 weeks ago, # ^ |   0 https://codeforces.com/contest/1375/submission/85999401 You have only checked two corners, but you have to check all four corners n*m matrix.
 » 5 weeks ago, # |   +2 Why so many wrong submissions for C even by red coders.
•  » » 5 weeks ago, # ^ |   -15 It was too simple for a C problem. (ig)
•  » » » 5 weeks ago, # ^ |   0 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.
•  » » » » 5 weeks ago, # ^ |   -6 I meant the implementation of it, not the problem itself. Lol i couldn't solve it during contest either.
 » 5 weeks ago, # | ← Rev. 4 →   -148 ~~~~~ There also exists O(n) solution for d #include #include #include 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 #define tup tuple #define ve vector #define vep vector #define mod 1000000007 #define maxn 2e5+5 #define ld long double #define in insert #define fr(i,a,b) for(int i=a;i>n; int a[n]; forn(i,n) cin>>a[i]; map 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 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<>t; while(t--) { solve(); } return 0; } 
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Please use Spoiler and Block to comment your code here. How to share your code
 » 5 weeks ago, # |   +6 Thank you very much for this round :p
 » 5 weeks 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
•  » » 5 weeks 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.
•  » » » 5 weeks ago, # ^ |   +22 Another shirt color change, nice!!
•  » » 5 weeks 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 ..
•  » » 5 weeks ago, # ^ |   -6 Really, for ex: I didnt found this solution for problem A.. So made some algo with random change of sign and Its working :D
•  » » 5 weeks ago, # ^ |   +7 Yes! Div2AB hatters don't understand, that keeping first problem easy (or seems to be easy) is key for right rating correlation.
•  » » » 5 weeks ago, # ^ |   0 this is very good point I think which should be noted by contest makers
•  » » 5 weeks ago, # ^ |   0 I was destroyed by this contest!
 » 5 weeks ago, # | ← Rev. 2 →   0 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 arrayNow largest is n and smallest is 1, start from either largest and smallest and check above condition.
•  » » 5 weeks ago, # ^ |   0
•  » » » 5 weeks ago, # ^ |   0 HereThe 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 arraycnt 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.
 » 5 weeks ago, # |   0 I did C in different way: for(int i=0;i
•  » » 5 weeks ago, # ^ |   +6 Here I think.
•  » » » 5 weeks ago, # ^ |   +3 Ohh yes, thanks for the explaining.
•  » » 5 weeks ago, # ^ |   0 read comments above! its actually same as a[n] — a[1] ! proof given above by kuroni.
•  » » 5 weeks ago, # ^ |   0 Another submission is here 85961984
•  » » 5 weeks ago, # ^ |   0 It's exactly the same thing, notice that every element cancels out except for the first and the last but interesting nonetheless
 » 5 weeks ago, # |   0 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."
•  » » 5 weeks ago, # ^ |   0 It means that if a cell has a number k then that implies that exactly k neighbors of that cell are non zero.
•  » » 5 weeks ago, # ^ |   +3 It says that out of 4 possible neighbours, there should be only k neighbours who have number > 0.
 » 5 weeks ago, # |   +2 keep make like this announcementsthey keep Cowards away
 » 5 weeks ago, # |   +23 Well, I see that those testers comment were not lying, tho
 » 5 weeks ago, # |   +3 A crazy $\textbf{D&C}$ solution for A : Don't look at it for too long#include 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 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; }   
•  » » 5 weeks ago, # ^ |   0 what D&C means?
•  » » » 5 weeks ago, # ^ |   +25 Divide and Conquer, I solved A like that after 1 hour of struggling . . .
•  » » » » 5 weeks ago, # ^ |   0 from which account?
•  » » » » » 5 weeks ago, # ^ |   +20 I'm a tester.
•  » » » » » » 5 weeks ago, # ^ |   +31 Now I can feel how these Round Feedback was compiled from the opinion of testers :p
 » 5 weeks ago, # |   0 Thanks for such a wonderful contest! Thank_u
 » 5 weeks ago, # |   +3 drunk coordinator
 » 5 weeks ago, # |   +18 Thanks anthoctryhardO_o for this beautiful round!!
 » 5 weeks ago, # |   +101 Welcome to the new era of AdHocForces
 » 5 weeks ago, # | ← Rev. 2 →   0 https://codeforces.com/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.
•  » » 5 weeks ago, # ^ |   +1 3 6 5 2 1 4 Try this permutation. Answer should be YES while yours give NO.
•  » » » 5 weeks ago, # ^ |   0 Thanks! I got it.
 » 5 weeks ago, # |   0 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
•  » » 5 weeks ago, # ^ |   0 Using stack missed some cases this problem can be handled in adhog way try this-Link
•  » » 5 weeks ago, # ^ |   0 Your code fails on this sample test case: array = {8,6,12,11} correct answer:yes your code answer:no {8,6,12,11} ---> {8,12,11} ---> {8,11} ---> {11} or {8}
•  » » » 5 weeks ago, # ^ |   0 thanks !!!!
•  » » 5 weeks 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
•  » » » 5 weeks ago, # ^ |   0 Thanks man!!! I thought stack approach will work in some way..
 » 5 weeks ago, # |   0 Typical adamant problem)
 » 5 weeks ago, # |   0 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 explanationso i have prepared visual explanation and solution of problem A,B,C as i was able to get them under controlLinks: -Problem AProblem BProblem CI 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 JourneyHope it helps :) :) Waiting for valuable feedback :) :)
•  » » 5 weeks ago, # ^ |   0 How can number of neighbours be 0 in B bro ?
•  » » » 5 weeks ago, # ^ |   0 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
•  » » » » 5 weeks ago, # ^ |   0 https://codeforces.com/contest/1375/submission/86019209Can you check where i am wrong?
•  » » » » » 5 weeks ago, # ^ |   0 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
•  » » » » » » 5 weeks ago, # ^ |   +1 yeah got it. Thanks
 » 5 weeks ago, # |   +8 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...
•  » » 5 weeks ago, # ^ |   0 What is your approach??
•  » » » 5 weeks ago, # ^ |   0 It supposed to be simple DFS, but I thought it was some hardcore shit DP.
 » 5 weeks ago, # |   +12 These days I dream of codeforces' contest with problems based on algorithms and data structures. DREAMS.
 » 5 weeks ago, # |   +5 How to solve D for minimum number of operations?
 » 5 weeks ago, # |   0 Your text to link here...can anyone tell me why it is not accepting
•  » » 5 weeks ago, # ^ |   0 Your link doesn't work, try to use a submission link.
 » 5 weeks ago, # |   0 Although i understand the tutorial but i m unable to find wrong in my submission for problem C.. need help.. thank you here's my submission failed in Test case 5
 » 5 weeks ago, # |   0 i loved the c problem great set
 » 5 weeks 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.
•  » » 5 weeks ago, # ^ |   0 It depends on your thought process, but I solved C and D with data structures.
•  » » » 5 weeks ago, # ^ |   0 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.
•  » » » » 5 weeks ago, # ^ |   0 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.
•  » » 5 weeks ago, # ^ |   0 Some Data structures and algorithms are too hard to understand, that's why we need an understanding level to know that.I think it is a reason for what they give ad-hoc, greedy, math, brute force, etc. problems upto C/D.
 » 5 weeks ago, # |   0 Problem A was too hard than expectations.
 » 5 weeks ago, # |   0 Can the number of neighbours be 0 in B ?
 » 5 weeks ago, # | ← Rev. 2 →   +2 Here is my approach for Problem C(using stack) : https://youtu.be/xOFkewgFhjALet me know if you find this helpful :)
•  » » 5 weeks ago, # ^ |   0 Understood. Thanks for the video!
 » 5 weeks ago, # | ← Rev. 2 →   +3 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".
•  » » 5 weeks ago, # ^ |   0 I did the same:)
 » 5 weeks ago, # |   0 problem C, sum of differences of all consecutive numbers in the array equals (a[n]-a[1]).[problem:C] 85966335
 » 5 weeks ago, # |   -11 Can anyone believe todays problem C was just one if-else!!! :Dif(a[0]
•  » » 5 weeks ago, # ^ |   +12 Yes. That is what a lot of people did.
 » 5 weeks ago, # |   +2 These days there is a trend of Adhoc problems on codeforces.
•  » » 5 weeks ago, # ^ |   -13 We need data structures and algorithms based problems.
 » 5 weeks ago, # | ← Rev. 3 →   0 _
 » 5 weeks ago, # |   +6 Here's another (almost equivalent) solution for C.It is easy to see that $a_1a_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  » 5 weeks ago, # | 0 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.com/contest/1375/submission/85968254 is the solution link. •  » » 5 weeks ago, # ^ | +1 86013495 You forgot to check whether$a[i][j] > 4$•  » » » 5 weeks ago, # ^ | 0 Thank you so much it's because of people like you that CodeForces is so good.  » 5 weeks ago, # | ← Rev. 4 → 0 85986603I am curious about the correctness of my submission in problem DMy 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. •  » » 5 weeks ago, # ^ | +25 I don't count cycles of length 1Let'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*} •  » » » 5 weeks ago, # ^ | 0 Wow, I made it too complicated.  » 5 weeks ago, # | +8 I have never ever seen a problem set like this.  » 5 weeks ago, # | +14 When I saw the tester comments I thought they were joking but now I know they weren't （  » 5 weeks ago, # | ← Rev. 3 → 0 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. •  » » 4 weeks ago, # ^ | 0 yeah yeah.. quite extraordinary.  » 5 weeks ago, # | 0 https://codeforces.com/contest/1375/submission/86018399 . Can some help me why my submission fails.  » 5 weeks 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. •  » » 5 weeks ago, # ^ | +7 can you please explain a little bit more? •  » » » 5 weeks ago, # ^ | +6 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. •  » » 5 weeks ago, # ^ | 0 why swapping the pair whose corresponding difference is 1 is answer? please explain a little bit more •  » » 5 weeks ago, # ^ | +8 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> 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; }  •  » » » 5 weeks ago, # ^ | 0 I understood it. You keep all inversions by moving in increasing order of a[i]. Your idea is naturally described. Great. •  » » » 5 weeks ago, # ^ | 0 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.  » 5 weeks 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 •  » » 5 weeks ago, # ^ | +18 I checked your submissions for problem D. None of them got accepted. Did you solve D using your idea??? •  » » » 4 weeks ago, # ^ | 0 Sorry but actually not  » 5 weeks ago, # | ← Rev. 2 → +3 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. •  » » 5 weeks ago, # ^ | +3 I did exactly the same, but i struggled to get AC.  » 5 weeks ago, # | 0 Looks like I was the only one used BIT for C.  » 5 weeks ago, # | 0 B and C is easier wrt to A, maybe I read those first:(  » 5 weeks ago, # | 0 How to prove that in problem D any array will take at most 2n operations. I went through editorial but could not get it. Any Help will be appreciated.  » 5 weeks ago, # | 0 Problem DLines from the editorialIt was not necessary under the given constraints, but one can notice that if mex=n, the current array is a permutation, and that solving a cycle will take size+1 operations. Hence, the described algorithm use in fact at most 1.5n operations, the worst case being [1,0,3,2,5,4,…] when there are a lot of 2-cycles.how the author directly arrives at the conclusion that above algorithm will take at most 1.5n operations. Can someone elaborate? •  » » 5 weeks ago, # ^ | +3 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.  » 5 weeks 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  » 5 weeks ago, # | +4 Is there any way to recompute MEX in less than O(n) time?? Problem D. •  » » 5 weeks 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. •  » » » 5 weeks ago, # ^ | 0 Thank you. got it :) •  » » 5 weeks 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. •  » » » 5 weeks 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)$. •  » » » » 5 weeks ago, # ^ | 0 Got scared after reading your first comment. However, got it. Thank you :)  » 5 weeks ago, # | -38 Can someone explain me this? How is this the video of the day?  » 5 weeks ago, # | +3 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$.  » 5 weeks ago, # | +5 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. •  » » 5 weeks ago, # ^ | +3 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.  » 5 weeks ago, # | 0 A and C problems are so tricky more than implementation or mathematics.  » 5 weeks ago, # | 0 How does one come up with a solution for problem D? I would really appreciate if someone could explain their solving experience.  » 5 weeks ago, # | 0 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?  » 5 weeks ago, # | 0 https://codeforces.com/contest/1375/submission/86033992 Getting runtime error, don't know why! •  » » 5 weeks ago, # ^ | 0$0≤a_i≤n$, so the size of "temp" should be n+1  » 5 weeks ago, # | 0  » 5 weeks ago, # | 0 Can somebody look at my code(Problem B), as online judge shows error -> wrong answer Final grid cannot be obtained by applying operations. (test case 15)As there is no condition on a cell with '0'  » 5 weeks ago, # | +1 Can someone explain or give an idea on how to solve the problem E Inversion Swapsort? I don't quite understand the editorial above.  » 5 weeks ago, # | 0 https://codeforces.com/contest/1375/submission/86052005 what is wrong in this solution for test case 4 it will give "0 1 2 3 4 5 5 6 7" it is showing wrong  » 5 weeks ago, # | 0 Hi! Can someone please point out the error in my solution to problem D. https://codeforces.com/contest/1375/submission/86057277  » 5 weeks ago, # | ← Rev. 2 → +4 Looking forward to AC4  » 5 weeks ago, # | 0 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!  » 5 weeks ago, # | +22 antontrygubO_o Could you explain general way how to aproach problems like F? How did you come up with the solution? •  » » 5 weeks 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. •  » » 5 weeks 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
•  » » » 5 weeks ago, # ^ |   +3 Very well explained
 » 5 weeks ago, # | ← Rev. 7 →   0 Can someone please explain why this https://codeforces.com/contest/1375/submission/86075419 getting TLE while this https://codeforces.com/contest/1375/submission/86004375 got accepted?i just changed the order of nested if's conditions.-
 » 5 weeks ago, # |   0 can someone explain why a simple bubble sort for problem E is wrong answer? it will give u,v with au>av.
•  » » 5 weeks ago, # ^ |   0 because the first two conditions of question are not met, only the third condition is satisfied
 » 5 weeks ago, # |   0 For problem E,could anyboy tell me why it's wrong when I just simple swap the biggest number each time .86083757
 » 5 weeks ago, # |   0 I should read F and G first Hmmmmm :((
 » 5 weeks ago, # |   +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 \log n + q \log^2 n)$My submission
 » 5 weeks ago, # |   -16 any one explain me problem A , and approach in tutorial why is true?
•  » » 5 weeks ago, # ^ |   +25 SpoilerNotice that $a_{i + 1} - a_i \ge 0$ is equivalent to $a_{i + 1} \ge a_i$. Similarly $a_{i + 1} - a_i \le 0$ is equivalent to $a_{i + 1} \le a_i$. Flip the signs in such a way that $a_i \ge 0$ for odd $i$, while $a_i \le 0$ for even $i$. Then $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.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.
•  » » » 5 weeks 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??!!!
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +9 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 specifyOK, 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.
•  » » » » » 5 weeks 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 !
•  » » » » » » 5 weeks 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?
•  » » » » » » » 5 weeks ago, # ^ |   -21 OK,so tell me how to become candidate master quickly XD
•  » » » » » » » 5 weeks ago, # ^ |   +8 ok , i'm sorry again
•  » » » » » » » » 5 weeks ago, # ^ |   +3 This branch of comments is too long, already. PM me, I'll explain to you.
•  » » » 5 weeks ago, # ^ |   0 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
•  » » » » 5 weeks ago, # ^ |   0 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$a[] = 3, 1, 2$$a[1]>a[2], 1<2$$a[1]>a[3], 1<3$Thus, you must swap positions $(1, 2)$ and $(1, 3)$.$3 1 2$ -> $1 3 2$ -> $1 2 3$First you swap positions $(1, 2)$, then positions $(2, 3)$.
•  » » » » » 5 weeks ago, # ^ |   +3 hey EmilConst thanks for replyingthe way MrDecomposition 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
•  » » » » » » 5 weeks ago, # ^ |   +5 U see i am just a pupilBeing 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 demotivationAre you demotivated, because I told you can't read problem statements?
•  » » » » » » » 5 weeks ago, # ^ |   +5 alright ..... was just messing srry
 » 5 weeks ago, # |   0 In Case Anyone Need Detail Explanation(Not a video tutorial) For D Here
 » 5 weeks ago, # |   0 Can someone explain how to solve problem E. I tried to understand the editorial but could not get any idea.
•  » » 5 weeks ago, # ^ |   +11
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 5 weeks ago, # ^ | ← Rev. 3 →   +6 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] •  » » » » » 5 weeks ago, # ^ | 0 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. •  » » » » » » 5 weeks 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_nswap(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. •  » » » » » » » 5 weeks ago, # ^ | +8 Wow, this is really impressive, by the way , thank you for helping me and putting so much effort in writing this comment •  » » » » » » » 5 weeks ago, # ^ | 0 I think I am doing the same thing here 86300926 but getting a WA for 7th test case. Can you help? •  » » » » » » » » 5 weeks ago, # ^ | ← Rev. 2 → +4 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 test3 69 69 0  •  » » » » » » » » » 5 weeks ago, # ^ | +6 Thanks, I am clear with my logic and have implemented it correctly. But I think I am misunderstanding the problem. Giving it another read :)  » 5 weeks ago, # | 0 for question E , why can 312->1 3 2 -> 1 2 3 not be done for the first test case ? •  » » 5 weeks ago, # ^ | 0 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$. •  » » » 5 weeks ago, # ^ | 0 thanks .. . . 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 this works out only thing i've changed is making a change in issorted function where i am forcing the elements to be like 0,1,2,3,....n-1 where previously issorted function will suffice if the array is increasing and not of the form 0,1,2,3.....  » 5 weeks ago, # | 0 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? •  » » 5 weeks ago, # ^ | ← Rev. 2 → 0 try the example, and find out why the second player lost.  » 5 weeks 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.  » 5 weeks 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 •  » » 5 weeks ago, # ^ | +5 That's the same solution as the one described in the editorial. •  » » » 5 weeks ago, # ^ | 0 oh sorry, the editorial was a bit hard to understand for me and i thought you were actually checking to generate a matrix like the one found in the example input/output on the problem page  » 5 weeks ago, # | 0 For G, how does one decide to think about bipartiteness? Is there an indication in the problem statement that makes you want to think of this, or is this just a random observation that reveals a property you can use to solve the problem?  » 5 weeks ago, # | -9 Can someone tell me why I am getting wrong in problem E in the 7th test case? 86297939 .  » 5 weeks ago, # | 0 Your text to link here... I am getting WA for Problem C.Plz help •  » » 5 weeks ago, # ^ | ← Rev. 2 → +18 Why do you think it should get AC? Have you proven your idea? Your idea is very similar to the one in the editorial, but it's incomplete. Read the editorial.  » 5 weeks ago, # | ← Rev. 4 → 0 A simpler algorithm for C — repeat until there is only one element left:Pick any index$i$such that$a_i < a_{i+1}$and remove$a_i$if$i>1$or$a_{i+1}$otherwise. If we always choose the smallest$i\$ that would be equivalent to the algorithm given in the editorial.
 » 5 weeks ago, # |   0 Why my code is not working can someone please help!! https://codeforces.com/contest/1375/submission/86348444
 » 4 weeks ago, # |   0 Problem E — Editorial Solution Coded in a simple and elegant wayhttps://codeforces.com/contest/1375/submission/86442236
•  » » 4 weeks ago, # ^ |   +3 Solving problem E requires two observations- We have to put largest element at position n, second largest element at position n-1 Since we have to include all inversions in the list we cannot simply swap it to the last position as we will lose inversions/list wrong inversions. In order to prevent losing inversions when placing largest element at n we list all inversion of n i.e. all pairs (i,a[n]) such that i>a[n] and i<=nand swap pairs as listed in editorial to prevent losing inversion
•  » » » 4 weeks ago, # ^ |   0 Example — 1 8 1 6 1 1 8 6 -> 1 , 2, 3, 41,8,1,6 -> 1,4,2,31 4 2 3 is a permutation 1 4 2 3 we look for all numbers greater than 3 and swap as mentioned in editorial in ascending order 1 3 2 4 we look for all numbers greater than 2 and swap as mentioned in editorial in ascending order 1 2 3 4
 » 4 weeks ago, # | ← Rev. 2 →   0 For Problem C and for input is 5 4 1 6 2 3, the actual Output must be YES,right?. But according to explained algo it's NO. Correct me if i am wrong. Edit: i got the question, i am sorry for my ignorance;
 » 4 weeks ago, # | ← Rev. 2 →   0 I can't get what's the issue with my code ,although it sorts the array in non decreasing ,i'm getting Wrong answer....,please help me out signed main() { int t; cin>>t; while(t--) { bool sorted=true; int n; cin>>n; int a[n]; for(int i=0;i>a[i]; } int mex=0; unordered_set s; vector v; for(int i=0;ia[j]) m=j; if(j+1a[j+1]) sorted=false; s.insert(a[j]); } if(sorted) break; while(s.find(mex)!=s.end()) mex++; if(m==i && mex>a[m]) continue; else if(m==i && mex
 » 3 weeks ago, # |   0 How do I remove the element in constant time in Problem C