Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

kefaa2's blog

By kefaa2, 6 months ago, translation, In English,

We hope you liked problems!

We are sorry for some passing wrong solutions for problems G & H.

Tutorial is loading...

Solution

Tutorial is loading...

Solution

Tutorial is loading...

Solution 1

Solution 2

Tutorial is loading...

Solution

Tutorial is loading...

Solution

Tutorial is loading...

Solution

Tutorial is loading...

Solution

Tutorial is loading...

Solution

Tutorial is loading...

Solution

You can also check ivan100sic comment for other variant of this solution

Tutorial of Good Bye 2019
 
 
 
 
  • Vote: I like it
  • +278
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it +63 Vote: I do not like it

nice problemset, me likey

»
6 months ago, # |
Rev. 2   Vote: I like it -44 Vote: I do not like it

Can you please add implementation of described approaches?

Del

»
6 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Thanks for very good contest and very fast editorial!

»
6 months ago, # |
Rev. 3   Vote: I like it +27 Vote: I do not like it

I wrote a segment tree solution for H and it seems that in some cases it will become $$$O(qn)$$$. However, it passed the main tests.

After the contest, I fixed it and it should be $$$O(n+q \log^2 n)$$$ now. May explain it later. (need to sleep now XD)

Wrong ( UPD: Correct ) solution: 67927407

Fixed solution: 67931310

UPD:

I figured out that my original solution was correct. You don't need to see the fixed solution, just see the original one. It has a time complexity of $$$O(n+q \log^2 n)$$$ in the worst case. It works fast because of the small constant factor, especially in the random cases. :D

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

    I also write a $$$O(q \log^2 n)$$$ solution. So in this problem, $$$O(q \log^2 n)$$$ solutions may be faster than $$$O(q \log n)$$$.

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

      Not necessarily, my $$$\mathcal{O}(q \log^{2} n)$$$ solution (67941714) took 6925 ms after lots of constant optimisation :Dd

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

        My solution is $$$O(q \sqrt n )$$$ (67924579). After checking TL, I didn't think there would be any log time complexity solution :D

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

        Can you explain your idea?

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

          Build a segment tree on the numbers. For every edge between two positions $$$x < y$$$, there is some node in the segment tree such that the left interval contains $$$x$$$ and the right interval contains $$$y$$$. Hence we can maintain all edges by maintaining for every segment tree node the edges between its left interval and right interval.

          To do this for some segment tree node, find minimum in left interval $$$\min(L)$$$ and maximum in right interval $$$\max(R)$$$. If $$$\min(L) > \max(R)$$$, there are no such edges. Otherwise, find leftmost $$$x$$$ in $$$L$$$ where $$$a[x] < \max(R)$$$, and rightmost $$$y$$$ in $$$R$$$ where $$$a[y] > \min(L)$$$. This can be done in $$$\mathcal{O}(\log n)$$$. Then all numbers in the interval $$$[x, y]$$$ must be in the same component: if $$$y' \leq y$$$, then either $$$y' < \min(L) < a[y]$$$ and $$$y', y$$$ are in the same component, or $$$y' > \min(L)$$$, then the minimum in $$$L$$$ has an edge to both $$$y$$$ and $$$y'$$$, hence $$$y', y$$$ are in the same component. Finally, there is an edge between the minimum in $$$L$$$ and maximum in $$$R$$$. This also proves all segments consist of consecutive elements.

          In another segment tree, we will maintain values $$$v[i]$$$ s.t. $$$a$$$ and $$$b$$$, $$$a < b$$$ are in the same component iff $$$\min_{v}([a+1, b]) > 0$$$. Then the number of components is the number of zeroes in this segment tree. To count the number of zeroes, just store range minimum and count of minimum ($$$v[i]$$$ will never be negative). To update the values $$$v$$$, whenever we find $$$x, y$$$ in the first segment tree, add $$$-1$$$ to $$$[px+1, py]$$$ and $$$1$$$ to $$$[x+1, y]$$$, where $$$px, py$$$ is the previous pair of $$$x, y$$$ for that node. This operation also takes $$$\mathcal{O}(\log n)$$$ time.

          Whenever we make an update, for each of $$$\mathcal{O}(\log n)$$$ segment tree nodes we do $$$\mathcal{O}(\log n)$$$ work in the form of three segment tree queries, hence the time complexity is $$$\mathcal{O}(q \log^{2} n)$$$.

»
6 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Did anyone solve E by considering a graph? please share your solution if you did.

  • »
    »
    6 months ago, # ^ |
    Rev. 3   Vote: I like it -32 Vote: I do not like it

    Well, i kinda did, I believe I have an $$$O(n^3)$$$ randomized solution that passes in 982ms :p (cant prove it though)

    The solution exists, so there are at least $$$n - 1$$$ blue edges(connecting points from different groups), so we can pick a random edge, the expected number of tries unitll we hit a correct one is $$$O(n)$$$. From there we pick all the edegs that have the same length and do a dfs to divide points between two groups, then just check if the conditions are met in $$$O(n^2)$$$.

    code

    edit: it doesn't work, bad tests

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My solution is in the same spirit as the editorial. Compute all pairwise distances. While they're all even, divide the distances by 2. Finally, take all the edges mod 2.

    Then we have a complete graph with each edge either 0 or 1. Find a 2 coloring of this graph and output it. This is way more complex than the editorial solution, but still passes systests.

    My code also doesn't handle the case when every distance is odd. Is that possible? Pls hack.

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it +35 Vote: I do not like it

    I did, consider the squares of all distances and calculate their gcd. Now if $$$dist ^ 2 / gcd \equiv 0 (mod 2)$$$ two points must be in the same component. Now there are at least 2 groups because after dividing all sq. distances by their gcd there is at least one which is odd and there are at most two groups because if the distances $$$(AB ^ 2 / gcd) \cdot (BC ^ 2 / gcd) \equiv (AC ^ 2 / gcd) (mod 2)$$$, where A, B and C are some points.

    UPD: Downgrading the color didn't go as planned. The code for this solution is stupid short and the complexity is $$$O(n + logC)$$$, which is better than the editorial. 67939313

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Damn your mathematics!!!Nice Work!

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

      First. It's important to note, that you don't consider all distances. You consider distances from first point to all other. After division of distances by $$$gcd$$$ you indeed will have at least one odd distnace. Otherwise, they all even after division, and it's contradiction.

      Second. I don't understand your formula with A, B, C. Also, I don't see how it leads to pairwise distances.

      Finally: complexity is $$$O(n \log(C))$$$, because you do $$$gcd$$$ $$$n$$$ times.

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

        No, complexity is really O(N + log(C)). Not all gcd calls are made equal! You can think like this: there will be at most log(C) times that G will be reduced to a divisor of G in gcd, the rest of the time gcd(something, G) will return G directly.

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Alright, thanks. Interesting stuff. Question about A, B, C is still up.

          • »
            »
            »
            »
            »
            »
            6 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Imagine that $$$AB^2, BC^2$$$ and $$$AC^2$$$ are all divisible by some number $$$g$$$ (which can be at most their gcd). Then the formula will work for any three points A, B and C no matter what (it's easy to prove looking at the coordinates parity). So the final observation is this — if we have at least one odd edge we can go through it and end up in a different component.

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

              I think, I finally got what you said.

              Too long details
              • »
                »
                »
                »
                »
                »
                »
                »
                6 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                It's not about what my code does, it's about the proof. So this fact is true for any three points, but my code does something a little different to be faster. You can proceed to see the $$$O(n^2+logC)$$$ code 67922484. I think I can write a little more on it and maybe even write an entry.

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

    Consider the different graphs with edges only of a specific length. If one of those graphs is not bipartite, we know that all vertices that are connected by an edge in that graph should be in the same component. That's our first observation. The second one is that if we have a bipartite graph, we can colour every connected component in it and then the vertices that are coloured the same will always be in the same component (note that we consider every connected component separately).

    Well with these two observations we can easily create a 2-sat like approach with dsu. You can check my solution for some more details.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      "If one of those graphs is not bipartite, we know that all vertices that are connected by an edge in that graph should be in the same component."

      I'm not sure I understand this. If you have 4 points in a square, there are 4 distances equal to the side length, therefore we have a graph with 4 vertices and 4 edges: (1,2), (2,3), (3,4) and (4,1).

      We can put points 1 and 3 in component A and points 2 and 4 in component B. Then all the 4 edges are "yellow" (i.e. the two endpoints of the edge are in different groups) and it's ok.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      There are no regular polygon with all vertices on lattice points (except square itself), stands as a reason that every graph will be bipartite right ?

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    This is what I did:

    1. Initially, all nodes are uncolored. We will try to color them with either $$$0$$$ (group A) or $$$1$$$ (group B).
    2. Sort all edges in ascending order (the order doesn't actually matter, it's just meant to group edges with same value)
    3. Process all edges with same value each time. If there is only 1 edge, we don't have to do anything. Otherwise, build a graph with these edges.
    4. For each edge $$$(x, y)$$$, there are 3 cases:
      • Type 1: both $$$x$$$ and $$$y$$$ have already been colored.
      • Type 2: either one of them is colored.
      • Type 3: neither are colored.
    5. Now we have to determine if our edges should be between nodes of same color or of different colors. If there exists at least 1 edge of type 1, we make our decision based on the colors of its nodes (this solution will fail if it encounters a case where there are 2 edges of type 1 such that one of them is between nodes of same color and the other is between those with different colors). Otherwise, our choice is different color.
    6. Loop through all edges of type 2 and assign colors accordingly using DFS.
    7. Loop through all edges of type 3, color one node with the color whose current count is less and just do similarly to the last step.
    8. At the end, if there are any uncolored nodes, color them with the color whose current count is less.

    You can see there are a couple of assumptions and greediness in this solution. I would appreciate if someone can uphack this 67920620.

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

      Hacked. I thought about that test during the contest a lot, 2/2 heuristic solutions I found seem to fail it...

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks! The test is simpler than what I originally thought it would be. This seems to be a downside of such ad-hoc problem because there might be many unpredictable approaches and some of them might end up slipping through.

»
6 months ago, # |
  Vote: I like it +37 Vote: I do not like it

The solution to G seems magic. It'd be nice if somebody could share how they came up with the solution.

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

    I can xD.

    First if we order the elements in some order we can calculate prefix sums and if two of them turn out to be equal then we simply have a subsequence with sum 0.

    Now run this algorithm on elements in the order they are in the input, sort them by value, absolute value, append first smallest positive and then until not all elements are in the sequence if current sum is positive append largest negative (by absolute value) such that sum stays nonnegative, or smallest (by absolute value) if it's impossible and if the sum is negative choose a positive element in a similar manner, do the same but start with smallest negative (by absolute value) and finally: if none of that worked random shuffle positive, negative, run through all of elements and if current sum is positive append the first negative element, and if not the first positive element.

    How to come up with this? It's quite simple. Just add more and more different orders until you can't find a countertest neither by hand nor with a script running random tests.

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

      I wish there could be a haha react on CF

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Got uphacked :(. Well done Radewoosh. Apparently need more heuristics. Added removing elements if their absolute value is greater than absolute value of sum of all elements of opposite sign and basic dp on bitset that finds an answer as long as at no point absolute value of sum exceeds 250. Hopefully now it's unhackable.

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it +31 Vote: I do not like it

      Your idea of ordering elemens to find two equal prefix sums actually can give a solution. One common way to ensure there are two equal prefix sums is to ensure that all $$$n+1$$$ prefix sums fall into a range of length $$$n$$$.

      If we pick the range to be $$$0..n-1$$$, then we require that:

      $$$0 \le pref_{i+1} = pref_i + a_{k_i} \le n-1 \iff -pref_i \le a_{k_i} \le n-pref_i - 1$$$

      This is almost exactly the condition we're given! In particular, picking

      $$$k_i = n - pref_i$$$

      exactly satisfies this inequalty. This gives rise to the same cycle-finding problem as the editorial.

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

    Indeed. aryanc403 can you please share how did you came up with this idea

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone suggest alternate solution for B?

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

    What I did: First, we can restrict to find a subarray where the maximum and minimum are its endpoints, this is so easy to prove. So, we must find a subarray $$$[a, b]$$$ such that $$$A[b]-A[a] > b-a$$$ or $$$A[a]-A[b] > b-a$$$. This is the same as $$$A[b]-b > A[a]-a$$$ and $$$A[a]+a > A[b]+b$$$, respectively. So, for each position $$$b$$$, we find a position $$$a: a \le b$$$ with minimum value $$$A[a]-a$$$ and the position $$$c: c \le b$$$ with maximum value $$$A[c]+c$$$. If $$$A[a]-a < A[b]-b$$$, then the range $$$[a, b]$$$ is interesting. If $$$A[c]+c > A[b]+b$$$, then the range $$$[c, b]$$$ is interesting.

»
6 months ago, # |
  Vote: I like it +44 Vote: I do not like it

Problem F has O(n (log n)^2) solution! 67930797

In my code, m <= 2*n/i (for i >= 1) after removing redundant segments.

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

    Can you please explain your solution?

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

      gs12117 asked me to translate his solution written in korean.

      Given a binary string, think of a path in a grid where you go (x, y)->(x+1, y) if current character is 1 and (x, y)->(x, y+1) otherwise. For two distinct points u and v along this path, if the slope of the line joining u and v is an integer, they correspond to an awesome substring. So I counted, for each slope in range 0 to n, the number of intersection points.

      Suppose we're currently checking slope >= k for some integer k. I claim that that we only have to check O(m/k) distinct number of x coordinates where m is the number of 1s.

      First observe that in order to have two distinct points u and v with x-coordinates differing by p produce an awesome substring, we need at least k * p number of 0s. Now build a graph where each node represents an x-coordinate and two nodes c and d (c < d) are connected by an edge if and only if the slope of the line joining the the point(in the initial grid) with the smallest y-coordinate with x-coordinate c, and the point(in the initial grid) with largest y-coordinate with x-coordinate d, is equal or greater than k. ( Note that if two points are not connected by an edge, it's not possible to produce an awesome substring with the corresponding pair of x-coordinates in the first place )

      Let A be one of the connected components of this graph with |A| >= 2. Note that A is always an interval. It turns out that each A requires at least k * |A| / 2 number of 0s. Here is the proof. Let a_0 -> a_1 -> ... -> a_p be a directed path where a_0 is the leftmost point and a_p is the rightmost point in A. Define b_1 = a_1 and b_i = (the leftmost point greater than b_(i-1)), and c_i = (the starting point of the directed edge in the directed path having b_i as its endpoint). Then c_(i+1) <= b_i and b_(i-1) < c_(i+1). Now for two sequences of directed edges {[c_1, b_1], [c_3, b_3], ...} and {[c2, b2], [c4, b_4], ...}, the edges in a sequence are non-overlapping for both of the sequences, and taking the union yields the entire range [a_0, a_p]. Therefore, at least one of them must contain k * (a_p — a_0) / 2 = k * |A| / 2 number of zeroes due to our initial observation.

      Now sum of all k * |A| / 2 over all A should be equal or less than n and, therefore, the sum of |A| should be equal or less than 2 * n / k.

      My solution now calculates for each of these x-coordinates in A the answer in O(log n), resulting in O(n log^2 n) complexity.

»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Where can we read more about those Lemmas from?

»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

in Problem E i can't understand why we should subtract 1 from odd coordinates and then divide by two and why doing this we're guarantee ending up with more than 1 group. Can someone explain this, please?

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

    We can move coordinate system so that one of the points becomes origin (0, 0). This point will belong to $$$A_{00}$$$ no matter how many times we will divide coordinates by 2. If all other points also belong to $$$A_{00}$$$, divide coordinates until there is a point with an odd coordinate.

»
6 months ago, # |
  Vote: I like it +14 Vote: I do not like it

If anyone is interested in the problem C solution that requires only 1 integer, then the answer would be to reason as follows: We shift X to the left, and add a zero in the end, since it is being multiplied by two. The last bit in S must be equal to the last bit in shifted xor (which is certainly zero). If we are to add an element, it will only affect the last bit in the sum, and cannot affect the last bit of the shifted xor; it affects the second to last bit (since it is shifted). If the last bit of the sum is 1, then the element must have a 1 in the last bit, since we need to make the last bit of the sum match the 0 of the xor. This 1 flips the second to last bit in the xor, and throws a carry to the second to last digit of the sum. If the sum has 0 as its last digit, the element too must have 0. We move on to the 2nd to last bits to determine the 2nd to last bit of the added element. As in the previous case, the 2nd to last bit of the element only affects the 2nd to last bit of the sum and not the xor; in fact it will affect the 3rd to last bit of the xor due to shifting. We force that bit of the sum to match the xor by setting the element second to last bit appropriately. We then flip the 3rd to last xor bit if necessary (if the element 2nd to last bit is a 1), and we make sure to ripple the carry if present. We keep doing this until all bits are matching.

I wonder if any of you guys went through the pain of thinking about and implementing this in contest... I certainly should have payed attention to the more relaxed constraints; as I would have saved a lot of time. But I am not very strong with bit arithmetic, so the smarter editorial methods did not come to my mind.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes I did. It didn't be hard. 67895496

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I had also done it exactly like you but did not know 1<<j will lead to an overflow even if j is long long. 1LL<<j is the only mistake in the code I submitted. A great question indeed. Super interesting to see so many approaches!

      I also am one of those who could not figure out the neat approaches in the editorial.

      Each bit can be determined and it is possible to construct the final xor and final sum values bit by bit.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I thought this way. But I couldn't come up with an appropriate solution. So I have to leave the problem sadly.

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

    Yes I also did the same way . As we try to match the next bit of the cumulative xor to previous bit of the cumulative sum , the number of bits in the final answer can go maximum upto 2 more bits than maximum of number of bits in cumulative xor and sum. Link -> https://codeforces.com/contest/1270/submission/67925984

»
6 months ago, # |
  Vote: I like it +25 Vote: I do not like it

$$$C$$$ answer for challenge is $$$1$$$ ($$$0$$$ if sequence is already good ofc). Observe that multiplying the xor by $$$2$$$ is just shifting its binary representation to the left by $$$1$$$ bit.

As $$$2 \cdot \text{xor} = \text{sum}$$$, the last bit of the sum must be $$$0$$$. Now, calculate the value of last bit of the sum by adding all the given numbers. If it is $$$1$$$, put $$$1$$$ as the last bit of the new number otherwise put $$$0$$$. Now, find xor of all these last bits of numbers including the number you just added. This must be the value of the second bit from the end of the sum. Keep repeating this process. Each time you fix the $$$i$$$ th bit of the new number, you xor all the $$$i$$$ th bits to get the $$$i+1$$$ th bit of the sum and hence you can fix the next bit.

Prove that this process cannot go on forever.

Complexity: $$$O(n\log{n})$$$

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    if s was odd why add a large odd num , why not smaller one

»
6 months ago, # |
  Vote: I like it +4 Vote: I do not like it

I thought my solution to C was a very stupid solution. Checking the editorial, I found it as Solution 1 :D

Anyone came up with that solution?

  • »
    »
    6 months ago, # ^ |
    Rev. 9   Vote: I like it 0 Vote: I do not like it

    Yes I did the same and added 10^15,10^15+1 although I dont know why adding 10^16,10^16+1 gave me WA on tc 2 as it will not be exceeding 10^18

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I did added 10^16 and it got AC!

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Ok my bad using pow was the cause of error pow(10,16)+1 returning 10^16 pow returns incorrect results for greater values than of order 15 beacuse of double precision

»
6 months ago, # |
  Vote: I like it +84 Vote: I do not like it

I thought about 1270E - Divide Points a slightly different way.

I divide the points by the parity of $$$x+y$$$. If this results in two non-empty sets, then we're done. If all the parities are even, then the points are all within a $$$45^\circ$$$-rotated lattice that's also scaled up by $$$\sqrt{2}$$$, so we can reduce the problem by rotating all points around the origin and scaling down by $$$\sqrt{2}$$$. This is easy to do with the mapping

$$$(x,y) \mapsto \left(\frac{x+y}{2}, \frac{x-y}{2}\right).$$$

If $$$x+y$$$ is odd, we can just shift everything over by $$$(1, 0)$$$ before dividing (just to avoid any issues with integer division/rounding).

Submission:

Sample code
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    hi, thanks for sharing! can you explain more what exactly the mapping is doing?

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i observed that the mapping is bringing the point (x,y) closer the origin by a factor of 2, but what i'm unsure of is if integer division messes up distances to other points in the process.

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it +14 Vote: I do not like it

      (Replying to both your comments here.)

      Yes, the mapping rotates the points clockwise by $$$45^\circ$$$, and scales all distances down by a factor of $$$\sqrt{2}$$$. Either all $$$x+y$$$ and $$$x-y$$$ are even or all of them are odd, so we can safely divide by 2 (or shift everything over by $$$1$$$ to make them even and then divide by 2), to ensure there are no integer division issues (see my sample code).

      To try a couple examples, this mapping maps $$$(1, 1)$$$ to $$$(1, 0)$$$ and maps $$$(3, 5)$$$ to $$$(4, -1)$$$. If you draw a shape or polygon on a grid and transform every point, you'll be able to see clearly that we're rotating and scaling (but by a factor of $$$\sqrt{2}$$$, not $$$2$$$).

      I made a quick diagram of the 2nd sample test case. "BEFORE" is the original square, "AFTER" is the transformed square including the shift to keep the coordinates integers. The unlabeled blue square is the transformation without the shift.

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        gotcha, i see now what you mean by doing the shift to maintain integer coordinates. the blue points are equivalent to the green points.

        are all the points rotated CW by $$$45 ^{\circ}$$$? for example, $$$(1,0)$$$ maps to $$$(0.5, 0.5)$$$ which seems CCW to me.

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

          Oh, I'm not sure. I might have been a little sloppy with my transformation, since all I care about is preserving similarity -- I think maybe it rotates and reflects the points? But it serves the same purpose. :)

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    great solution!

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Isn't that mapping rotates the point counter clockwise?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If all the parities are even, then the points are all within a 45∘-rotated lattice that's also scaled up by √2. Can someone please explain this?

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it +11 Vote: I do not like it

      Try drawing every point $$$(x,y)$$$ such that $$$x+y$$$ is even, or is odd. Then turn your head 45 degrees. :)

      Here is a picture, the blue circles are $$$x+y$$$ even and the red crosses are $$$x+y$$$ odd.

      If you turn your head and look at only the red crosses, you can see it looks the same as the original full lattice but with a bigger spacing between points.

»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Heh, solution 2 for c was so easy! I thought so hard. But I missed such easy thinking.

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

Can someone please explain why am i getting TLE in my code for solution B.Time complexity seems to be O(n (log n)^2) which should have passed in 2 sec?(I have used binary search and segment trees).

Here is the submission:67897851

»
6 months ago, # |
Rev. 3   Vote: I like it -8 Vote: I do not like it

Disappointing contest I have no idea why problems B and C was very difficult for me Anyone see a connection between the two problems ?

Please, someone tell me how many people solve it ? I was stuck for a bout 30 min then just guessed the solution.

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

    _Disappointing contest I have no idea why problems B and C was very difficult for me _

    Ok. I don't want to troll again. Lmao ... but your (actual) color says it all.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In my solution for problem B, I have taken max(a)-min(a),checked if greater than array size and printed their positions. What is wrong in this logic. This my solution67923904.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    1 5 1 2 2 3 5 check fo this testcase. your logic is completely wrong. you need to find any subarray for which max-min>=n. but you are finding only for l=0,r=n-1.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What intution does exactly require one to solve d problem

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

    I did solve during round but haven't found bug. Shame, I just thought that server reply value first.

    The way of my thinking was following. You have $$$n$$$ and $$$k$$$. You look at range of $$$k$$$. It can be in range $$$[1,n-1]$$$. Alright, you think $$$1$$$ and $$$n-1$$$ are cornercases, but I wan't general case. It was hard to avoid this thinking, but as soon as I tried to solve cornercases, it worked. For $$$k=1$$$ it's easy. The only possible $$$m$$$ is $$$1$$$. How about $$$n-1$$$? You have $$$n$$$ possible queries. They are defined by missing number in query. This has link with restriction on maximum number of queries. Can you answer what is $$$m$$$ based on all those $$$n$$$ queries? It turns out: yes. But also, you can tell it by statement of problem. It says that you can always do that in this restrictions.

    How to do that? Just imagine all $$$n$$$ elements. Now, you have $$$m$$$-th element in it. Request with gap is identical to all elements without some element. If you remove element behind $$$m$$$-th or $$$m$$$-th element itself, you'll get element right after it. If you remove element after it, you'll get $$$m$$$-th element itself. So, cases are devided into two outcomes. One of them happens $$$m$$$ times and other happens $$$n-m$$$ times.

    From that on, you can try apply similar method by moving gap along array, with no result. Very important thing is left, and hard to came up with it. I spent at least half of hour for this part. And this thing, is the only thing that is left, is key observation. What if you can find out m for shorter array? Then... You did it! Who cares about rest of array? That's it! Just cut off all elements from a in such way that $$$n-1 = k$$$. Done. Honestly, I solved cornercase when I realized that you can cut array first. For the whole before, I knew that $$$k = n-1$$$ is solvable by moving gap, but didn't dig into details and was trying to move gap for smaller $$$k$$$.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Will anyone explain me the solution 1 for 1270C Make Good? Why are we adding 2^50 as one of the number?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Could you please explain 1270C — Make Good logic in easy terms ?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Solution 2 works like this: We have the sum as S and xor as X. Adding X as one number modifies the sum as (S + X) and xor as (0) [xor with itself gives 0] Now add (S + X) as another number, sum becomes 2(S + X) and xor becomes (S + X) [0 xor any number is that number] So we add 2 numbers, X and (S + X)

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I saw this $$$O(N)$$$ solution for E. Is this correct?

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

    That's $$$O(N \log N)$$$ because each gcd call is $$$O(\log N)$$$. Actually, in this problem it can be proven to take only $$$O(N + \log \max a_i)$$$ -- check out this comment below https://codeforces.com/blog/entry/72611?#comment-569387.

    However, there is an $$$O(N)$$$ solution. Doing the transformation twice is equivalent to dividing both coordinate by 2 (ignoring the 90 degree rotation), and it's possible to compute the number of division by 2 required using bitwise operations, after that the maximum number of operations necessary is at most 1.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh, I see. Would you mind writing an explanation for your $$$O(N)$$$ solution. Thanks in advance!

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

        I just implemented it. 67969860

        We divide only when all points are in same group. This means, that up to some moment, all their parity match. First, solve easier problem: how many times parity match when you divide array by two? Answer is equal to the number of common least significant bits of all numbers within array. Let say $$$f(a,b)$$$ is number of same least significant bits. Then, number of times to divide by two until we have different parity within array is equal to $$$\min\limits_{i,\,j} f(a_i,a_j)$$$. Then $$$a_1$$$ should also have same least bits, so it's just $$$\min\limits_i f(a_1,a_i)$$$. Bitwise $$$\mathbb{xor}$$$ will tell us where are the different bits. So, $$$f(a,b) = g(a\,\mathbb{xor}\,b)$$$ where $$$g(a)$$$ is position where least significant bit that is set. To find out least significant bit of $$$x$$$, you just subtract one from it, it should turn lowest one into zero, and replace all zero below into ones. Now, if we make bitwise and of result and $$$x$$$, we will have $$$x$$$ without least one. So, formula is $$$h(x) = x - (x\,\mathbb{and}\,(x-1))$$$. Probably you may simplify it, but for sake of easy explanation I'll leave it as is. Now, what's important. First, if there is no $$$1$$$ in binary, then it'll return $$$0$$$. Second: it's a bit. So, it's $$$2^k$$$. But we want to divide $$$k$$$ times, so this is exactly what we need. And, $$$\min$$$ in formula will assist. Now, back to points with two coordinates. Divisor is equal to $$$\min(\min\limits_i h(x_1\,\mathbb{xor}\,x_i) , \min\limits_i h(y_1\,\mathbb{xor}\,y_i))$$$

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

          Wow! You thought so much to just make it $$$O(N)$$$ from $$$O(NlogN)$$$. Thanks a lot for the reply!

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

      Actually, that solution isn't O(N*logN) but O(N + logA). There will be at most O(N + logA) iterations of the gcd since for each 2 iterations in the same call the gcd will be scaled down by at least a factor of 1/2.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it -27 Vote: I do not like it

      using gcd will result in $$$O(n + log)$$$ not $$$O(n.log)$$$. please don't say this shits anywhere else.

  • »
    »
    6 months ago, # ^ |
    Rev. 4   Vote: I like it -15 Vote: I do not like it

    $$$O(N + log N)$$$

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain me in C solution 1 why S <= 2 * 2 ^ 50 <= X ?

»
6 months ago, # |
  Vote: I like it -10 Vote: I do not like it

please someone help me to understand how they approached F awesome strings problem?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain what is that thing with dividing by 2 in Problem E I am not getting How to Solve this problem ! Please Help me out !

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    According to editorial we are just scaling down our plane as it all depends upon making a group of points such that points from two different sets don't have distance equal to what two points in a group can have. To target that inequality we are focusing on parity of sum of co-ordinates, because if we make a group of points which have odd coordinate sum then square of intra group distances will always be odd and inter group distances will be even. Thus we can create a partition successfully if we have points whose co-ordinate sum is odd, but all N points must not possess this property because they all will fall in same group. Now, only two cases remain

    Case 1 : You have zero points with odd co-ordinate sum.

    Case 2 : You have N points with odd co-ordinate sum. First case can be handled by scaling down the plane by one-fourth i.e. divide points by two, because it occured due to even sum , at some point of time its co-ordinate sum will change its parity if you keep dividing the points by two. Same parity change can be induced for handling second case.

    Instead of dividing the plane rotating the axes by 45 degree is safer and more elegant.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That was very a nice explanation! Thanks budyy for making it so damn crystal clear ! Kudos ! Add me in your friends :) :)

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

IDK why, the tutorial has clear proof but I still can't understand the logic for problem — B. Why are we checking if |ai+1−ai|≥2 ? Why is it working?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In B problem, Why you have considered max>min always?(it might happen that index of maximum element is lower than minimum element)

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's assumed without loss of generality, i.e. there is a symmetry argument. In this case, the same argument will hold if you reverse the array and look at that sequence, but in this new array, the max/min elements are on opposite sides.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me why is MrDindows mentioned in the editorial for problem? I don't know the story around him and bruteforces.

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

In E problem

I didn't get the "divide by 2" part,for eg:if points are (1,1),(3,3),(5,5)...all odd nos,how will we proceed? We can't just take the floor of all points right,odd numbers will be scaled down by 2.5 and even nos will be scaled down by 2?

example:(1,2) becomes (0,1),and (2,1) becomes (1,0),the ratio by which they shrank is different right?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Assume all of points are in $$$A_{ij}$$$ then you may subtract vector $$$(i,j)$$$ from all of them, and they will be in group $$$A_{00}$$$ and distances won't change. Now, notice that $$$(x - (x\,\mathbb{mod} \,2))\,\mathbb{div}\,2 = x\,\mathbb{div}\,2$$$. So, you may just divide by two. Notice, solution from editorial adds 1e6 to avoid negative coordinates, because in c++ division of -1 by 2 is still -1.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a lot got it now

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      In editorial code they are saying, clubbing A00 with A01 and A11 with A10 produces the right answer.

      But if you see dist(A01, A11) ==> ODD where as dist(A11, A10) ==> ODD

      Is it not possible that blue distance equals yellow distance?

      Also are you sure about -1/2 = -1, I tried it on GNU G++ it is 0.

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Okay got it they are checking that when there is only odd sum cords or only even sum cords.

        Seems like I mis read their code.

        NVM

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me understand, how would someone get an idea of how to solve C? (talking about solution 2)

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I was thinking like this. Lets say $$$a$$$ is input array, and $$$b$$$ is what we add. First obvious thing: sum(a and b) is sum(a)+sum(b). Next, a little less known, but also very known fact, that xor(a and b) is xor(xor(a),xor(b)). A little more about this fact. In bitwise operations (except shifts and rotates) all bits are independent. So, if property holds for one bit, then it holds for all. Property xor(a and b) is xor(xor(a), xor(b)) for single bit comes from fact that for single bit $$$a \,\mathbb{xor}\,b = (a+b)\,\mathbb{mod}\,2$$$

    Now, first idea comming from facts above: we have $$$x = sum(a)$$$ and $$$y = xor(a)$$$. So, instead of array, we have two numbers. Alright, we have three numbers to 'spend'. Words in your head "too hard", lets get rid of $$$y$$$. How? With easiest way, just add $$$y$$$, and sum will turn into $$$x+y$$$ and xor will turn into zero. Observation: xor by zero doesn't do anything. So, once we add something, xor will have this number. Now: hmmm, we have question, what value $$$z$$$ to add to some value $$$s$$$ to have $$$s + z = 2z$$$. Easy! Just $$$s$$$ itself.

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

In Editorial of problem E is is written "From now on we suppose that at least two groups are nonempty". How to prove this ?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    if some number is even then it will come down to 2 eventually and then come down to 1 by further division by 2.

    Now the case of odd numbers. After dividing them again and again you can make them zero so they become even.

    Hence you can always change the parity and form two groups.

»
6 months ago, # |
  Vote: I like it +36 Vote: I do not like it

kefaa2 Quadratic solution in F passed: 67995161 :D

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

    Wow, it's unexpected :(

    During testing, danya.smelskiy found bruteforce solution, which passed initially. It was basically this 68008487 (I added a few more pragmas). So, challenge is to find difference with 68008440.

    So, maybe it's good that we didn't find this solution :) (well, of course is bad, but it would be really hard to cut this solution from slow solution with correct asympotics without setting constraints very high).

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

      Crucial part is avx2, gather operations work much faster than avx

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can u tell me in the solution of this question how X⊕X⊕(S+X)=(S+X) this is possible and for S+X+(S+X)=2(S+X) S+X+(S+X)=2(S+X) we have to find S⊕X⊕(S+X)

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I did not fully understood editorial of F , can some one help me

»
6 months ago, # |
Rev. 2   Vote: I like it +36 Vote: I do not like it

The editorial for problem I is a bit hard to understand, anyway, here's how I solved it. Let $$$n = 2^k$$$, let $$$B$$$ be the matrix which describes all moves made, $$$B(i,j)$$$ will be equal to the xor of all $$$w$$$ such that a move $$$(i,j,w)$$$ was done. Clearly, there's no need to do more than one move on the same pair $$$(i,j)$$$. We're also given a matrix $$$F$$$ with $$$t \leq 99$$$ 1-entries, all others are zero ($$$t$$$ is odd). We can think of this problem in terms of cyclic matrix convolutions modulo 2. The problem asks us to find a matrix $$$B$$$ with the minimum number of non-zero entries such that $$$B * F = A$$$. The solution consists of two parts. First, finding the inverse element $$$F^{-1}$$$. Second, finding the product $$$A * F^{-1} = B$$$. Surprisingly, the first part can simply be done by finding $$$F^{n-1}$$$, this can be done efficiently using bitsets, by multiplying the identity element by $$$F$$$ a total of $$$n-1$$$ times, each multiplication can be done in time $$$O(tn^2/32)$$$, this part has complexity $$$O(tn^3 / 32)$$$.

Here's proof that $$$F^n = I$$$, where $$$I$$$ is the identity matrix for cyclic convolutions, i.e. the matrix $$$I$$$ has $$$I_{0,0} = 1$$$ and all other entries equal to $$$0$$$. This also implies that the matrix $$$B$$$ always exists and is unique!

It's sufficient to check that $$$F^2$$$ has nonzero entries only where both $$$i,j$$$ are even. By definition, $$$(F^2)_{i,j} = \sum_{x=0}^{n-1} \sum_{y=0}^{n-1}F_{x,y}F_{i-x,j-y}$$$. Notice that, whenever at least one of $$$i,j$$$ is odd, not a single element of $$$F$$$ is paired with itself in the sum, so each pair will appear exactly twice, so the sum is $$$0$$$. The main result follows by induction, we can kick out all odd-numbered rows and columns after one squaring. We will end up with $$$I$$$ because each squaring does not change the fact that $$$F$$$ has an odd number of ones (this is easy to verify).

The second part can be done as follows. First of all, we need to compute the product $$$A * F^{-1}$$$ for each bit position. Each multiplication can be done using 2D-FFT in time $$$O(n^2 \log n)$$$. It's better to use complex numbers because we only need results accurate to around $$$20$$$ binary digits. Also, we can cut the constant factor from $$$60$$$ to $$$30$$$ by making use of both real and imaginary parts (real part for one bit-position, imaginary part for another bit-position). This part has complexity $$$O(n^2 \log n \log M)$$$ but with a much worse constant factor.

Overall the solution barely passes the time limit.

There's another solution which just computes $$$A * F^{n-1}$$$ by repeatedly multiplying $$$A$$$ with $$$F$$$, it has time complexity $$$O(tn^3)$$$ but it is unfortunately not fast enough (but it's close).

Edit: As suggested by kefaa2, all powers of $$$F$$$ are sparse, i.e. have no more than $$$t$$$ nonzero entries. This allows fast multiplications by arbitrary powers of $$$F$$$ in $$$O(n^2 + t^2)$$$ and eliminates the need for using FFT for the final multiplication with $$$A$$$.

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

    I want to correct this last statement. It isn't true that all powers of $$$F$$$ are sparse — $$$F^{511}$$$ is dense (about 1/2 of all entries are 1 and 1/2 are 0) even for a random set of $$$7$$$ initial cells. However, what's true is that $$$(F^a)^2$$$ is only as dense as $$$F^a$$$, since any $$$(F^a)_{i,j} = 1$$$ contributes $$$1$$$ to $$$(F^{2a})_{2i,2j}$$$, so all powers to powers of $$$2$$$ of $$$F$$$ have at most $$$t$$$ non-zero entries and we can efficiently multiply $$$A$$$ by $$$F^1$$$, $$$F^2$$$, etc. up to $$$F^{2^{k-1}}$$$.

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

      I think I wanted to say that all iterated squares of $$$F$$$ are sparse. Thanks for claryfing this!

»
6 months ago, # |
Rev. 2   Vote: I like it -40 Vote: I do not like it

can anyone tell what's the problem in this code for Q2

include<bits/stdc++.h>

using namespace std; int main() { int t;cin>>t;

while(t--)

 {
     int n;cin>>n;
     vector<long long>v(n);
     int  k;
     for(int i=0;i<n;i++)cin>>v[i];
     long long maxidx=max_element(v.begin(),v.end())-v.begin();

     long long minidx=min_element(v.begin(),v.end())-v.begin();

     long long idx=max(minidx,maxidx);
     k=idx+1;

     for(int i=0;i<idx;i++)
     {
         if( abs(v[idx]-v[i])>=k)
         {
             cout<<"YES"<<endl;
             cout<<i+1<<" "<<idx+1<<endl;
             break;
         }
         else
         {
             k--;
         }
     }
     if(k==1)
     {
         cout<<"NO"<<endl;
     }


 }

}#include<bits/stdc++.h> using namespace std; int main() { int t;cin>>t; while(t--) { int n;cin>>n; vectorv(n); int k; for(int i=0;i<n;i++)cin>>v[i]; // long long r=*max_element(v.begin(),v.end()); // long long l= *min_element(v.begin(),v.end()); // long long f = r-l; long long maxidx=max_element(v.begin(),v.end())-v.begin(); long long minidx=min_element(v.begin(),v.end())-v.begin(); long long idx=max(minidx,maxidx); k=idx+1; for(int i=0;i<idx;i++) { if( abs(v[idx]-v[i])>=k) { cout<<"YES"<<endl; cout<<i+1<<" "<<idx+1<<endl; break; } else { k--; } } if(k==1) { cout<<"NO"<<endl; }

}

}

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E , when the elements belongs to groups say A00 and A11 only then how can we say that when we will take elements from different groups i.e. A00 and A11 then it's sum will always give remainder 2 when divided by 4 but not zero?? is there any proof of it?? .

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain problem F editorial or some another solution? I have been at it for 2 days.

»
6 months ago, # |
  Vote: I like it -9 Vote: I do not like it

Where can I see solutions on Python? I found link with only C++ solutions.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm trying to solve problem F without looking at the solution. I have to say, it's a beautiful problem, at least for a weakling like me.