MrDecomposition's blog

By MrDecomposition, history, 5 weeks ago, In English,
Problem A
Problem B
Problem C
Problem D
Problem E
Problem F
Problem G
Problem H
Problem I
 
 
 
 
  • Vote: I like it
  • +377
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +303 Vote: I do not like it

You guys should've read problem I first, smh

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

    86000122 You got a work to do;)

  • »
    »
    5 weeks ago, # ^ |
    Rev. 3   Vote: I like it +13 Vote: I do not like it

    Monogon adamant

    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, # ^ |
        Vote: I like it +13 Vote: I do not like it

      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, # ^ |
        Vote: I like it +21 Vote: I do not like it

      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:

      1. Swap second and third row;
      2. 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   Vote: I like it +13 Vote: I do not like it

        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, # ^ |
            Vote: I like it +13 Vote: I do not like it

          By irreducible I meant primitive there, sorry.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        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   Vote: I like it +23 Vote: I do not like it

          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, # ^ |
            Vote: I like it +20 Vote: I do not like it

          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   Vote: I like it +24 Vote: I do not like it

        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, # ^ |
            Vote: I like it +6 Vote: I do not like it

          Wow, nice observation, thanks!

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
          Rev. 2   Vote: I like it +8 Vote: I do not like it

          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, # ^ |
              Vote: I like it +8 Vote: I do not like it

            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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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   Vote: I like it +18 Vote: I do not like it
          1. 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$$$.)

          2. 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.

          3. Yup, $$$k > 1$$$ isn't important.

          4. Yeah, we don't really care about uniqueness, but it's nice to know.

          5. I think the cleanest view of the transformation is dividing by $$$1 + i$$$.

          6. It's important to avoid irrational coefficients so that our claims about Hurwitz quaternions hold.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      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:

      1. $$$q$$$ must right-divide each of the $$$a_i$$$, so $$$q$$$ right-divides $$$g$$$, i.e. $$$g = qh$$$ for some $$$h$$$.
      2. $$$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}$$$.
      3. $$$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.

      1. Compute $$$g = \operatorname{right-gcd}_i(a_i)$$$.
      2. 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)))$$$
      3. 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.
      4. Finally, compute $$$q = \operatorname{right-gcd}(g, r)$$$. As above, $$$\lVert q \rVert = r$$$.
      5. 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, # ^ |
          Vote: I like it +10 Vote: I do not like it

        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, # ^ |
      Vote: I like it -9 Vote: I do not like it
»
5 weeks ago, # |
  Vote: I like it +672 Vote: I do not like it

By the way it's my meme.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did not understand it

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # |
  Vote: I like it +5 Vote: I do not like it

what happened to "doomsday" and tester comments :O

»
5 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

tricky Questions!!

»
5 weeks ago, # |
Rev. 3   Vote: I like it +17 Vote: I do not like it

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, # ^ |
      Vote: I like it +55 Vote: I do not like it

    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, # ^ |
      Vote: I like it +29 Vote: I do not like it

    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, # ^ |
        Vote: I like it +7 Vote: I do not like it

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

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        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, # ^ |
            Vote: I like it +1 Vote: I do not like it

          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, # ^ |
        Vote: I like it +28 Vote: I do not like it

      Sometimes it feels like someone telepatically gives me random hints.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Or Maybe you are John Wick of Coding. #QuesKiller

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Your name is quite original.

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      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, # ^ |
          Vote: I like it +2 Vote: I do not like it

        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   Vote: I like it 0 Vote: I do not like it

          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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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
»
5 weeks ago, # |
  Vote: I like it +176 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
Rev. 3   Vote: I like it -23 Vote: I do not like it

[deleted]

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it +2 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -15 Vote: I do not like it

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

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
          Vote: I like it -6 Vote: I do not like it

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

»
5 weeks ago, # |
Rev. 4   Vote: I like it -148 Vote: I do not like it

~~~~~ 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; }
  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Please use Spoiler and Block to comment your code here.

    How to share your code
»
5 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Thank you very much for this round :p

»
5 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

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, # ^ |
      Vote: I like it +42 Vote: I do not like it

    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, # ^ |
      Vote: I like it +15 Vote: I do not like it

    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, # ^ |
      Vote: I like it -6 Vote: I do not like it

    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, # ^ |
      Vote: I like it +7 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      this is very good point I think which should be noted by contest makers

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I was destroyed by this contest!

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 )

      1. Now we know that number goes from 1 to n , so we iterate from 1 to n ( small to large )

      2. During every iteration , if current number if at the rightmost spot, then you cannot convert this array , else continue.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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??

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Here I think.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    read comments above! its actually same as a[n] — a[1] ! proof given above by kuroni.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Another submission is here 85961984

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

keep make like this announcements

they keep Cowards away

»
5 weeks ago, # |
  Vote: I like it +23 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

Don't look at it for too long
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for such a wonderful contest! Thank_u

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

drunk coordinator

»
5 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

Thanks anthoctryhardO_o for this beautiful round!!

»
5 weeks ago, # |
  Vote: I like it +101 Vote: I do not like it

Welcome to the new era of AdHocForces

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

Typical adamant problem)

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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 :) :)

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How can number of neighbours be 0 in B bro ?

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # |
  Vote: I like it +8 Vote: I do not like it

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, # |
  Vote: I like it +12 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve D for minimum number of operations?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Your text to link here...

can anyone tell me why it is not accepting

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

i loved the c problem great set

»
5 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

Problem A was too hard than expectations.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can the number of neighbours be 0 in B ?

»
5 weeks ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

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

Let me know if you find this helpful :)

»
5 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

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

[problem:C] 85966335

»
5 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

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!!

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Yes. That is what a lot of people did.

»
5 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    We need data structures and algorithms based problems.

»
5 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

_

»
5 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

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.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    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*}

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

I have never ever seen a problem set like this.

»
5 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

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

»
5 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yeah yeah.. quite extraordinary.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1375/submission/86018399 . Can some help me why my submission fails.

»
5 weeks ago, # |
  Vote: I like it +33 Vote: I do not like it

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, # ^ |
      Vote: I like it +7 Vote: I do not like it

    can you please explain a little bit more?

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      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, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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;
    }
    
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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   Vote: I like it -16 Vote: I do not like it

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, # ^ |
      Vote: I like it +18 Vote: I do not like it

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

»
5 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Looks like I was the only one used BIT for C.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

B and C is easier wrt to A, maybe I read those first:(

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it
Problem D

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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   Vote: I like it +18 Vote: I do not like it

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, # |
  Vote: I like it +4 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +32 Vote: I do not like it

    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, # ^ |
    Rev. 2   Vote: I like it +19 Vote: I do not like it

    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, # ^ |
        Vote: I like it +38 Vote: I do not like it

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Got scared after reading your first comment. However, got it. Thank you :)

»
5 weeks ago, # |
  Vote: I like it -38 Vote: I do not like it

Can someone explain me this? How is this the video of the day?

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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, # |
  Vote: I like it +5 Vote: I do not like it

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, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

A and C problems are so tricky more than implementation or mathematics.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

Code -> https://codeforces.com/contest/1375/submission/86049770

As there is no condition on a cell with '0'

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

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   Vote: I like it +4 Vote: I do not like it

Looking forward to AC4

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it +22 Vote: I do not like it

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   Vote: I like it +10 Vote: I do not like it

    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, # ^ |
      Vote: I like it +61 Vote: I do not like it

    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)

»
5 weeks ago, # |
Rev. 7   Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

I should read F and G first Hmmmmm :((

»
5 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

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, # |
  Vote: I like it -16 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +25 Vote: I do not like it
    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.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      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   Vote: I like it +9 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it -11 Vote: I do not like it

          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   Vote: I like it +18 Vote: I do not like it

            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, # ^ |
                Vote: I like it -21 Vote: I do not like it

              OK,so tell me how to become candidate master quickly XD

            • »
              »
              »
              »
              »
              »
              »
              5 weeks ago, # ^ |
                Vote: I like it +8 Vote: I do not like it

              ok , i'm sorry again

              • »
                »
                »
                »
                »
                »
                »
                »
                5 weeks ago, # ^ |
                  Vote: I like it +3 Vote: I do not like it

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

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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
        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          hey EmilConst thanks for replying

          the 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, # ^ |
              Vote: I like it +5 Vote: I do not like it

            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?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it
    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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   Vote: I like it +6 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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, # ^ |
              Vote: I like it +30 Vote: I do not like it

            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.

            • »
              »
              »
              »
              »
              »
              »
              5 weeks ago, # ^ |
                Vote: I like it +8 Vote: I do not like it

              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, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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   Vote: I like it +4 Vote: I do not like it

                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
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 weeks ago, # ^ |
                    Vote: I like it +6 Vote: I do not like it

                  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, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # |
  Vote: I like it 0 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

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, # |
  Vote: I like it -8 Vote: I do not like it

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, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it -9 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +18 Vote: I do not like it

    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   Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

Why my code is not working can someone please help!! https://codeforces.com/contest/1375/submission/86348444

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem E — Editorial Solution Coded in a simple and elegant way

https://codeforces.com/contest/1375/submission/86442236

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Solving problem E requires two observations-

    1. We have to put largest element at position n, second largest element at position n-1

    2. 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<=n

    and swap pairs as listed in editorial to prevent losing inversion

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Example — 1 8 1 6 1 1 8 6 -> 1 , 2, 3, 4

      1,8,1,6 -> 1,4,2,3

      1 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   Vote: I like it 0 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

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<n;i++)
       {
           cin>>a[i];
       }
       int mex=0;
       unordered_set<int> s;
       vector<int> v;
      for(int i=0;i<n;i++)
      {
          mex=0;

          int m=i;
          for(int j=i;j<n;j++)
          {
              if(a[m]>a[j])
                m=j;
              if(j+1<n && a[j]>a[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<a[m])
          {
              s.erase(s.find(a[i]));
              v.push_back(i+1);
              a[i]=mex;
              continue;
          }
          else{if(mex<a[m])
            {
                s.erase(s.find(a[i]));
                a[i]=mex;
                v.push_back(i+1);
            }
                else{s.erase(s.find(a[i]));
                a[i]=a[m];
                a[m]=mex;
                v.push_back(m+1);
                v.push_back(i+1);}

          }
          sorted=true;
      }

      cout<<v.size()<<endl;;
      for(int i=0;i<v.size();i++)
        cout<<v[i]<< " ";
      cout<<endl;
      for(int i=0;i<n;i++)
        cout<<a[i]<< " ";
      cout<<endl;
  }
return 0;
}
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How do I remove the element in constant time in Problem C