When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

ko_osaga's blog

By ko_osaga, history, 4 years ago, In English

Since the Polygon tutorial system is currently broken, I will replace the editorial with PDF format. Sorry for the inconvenience!

Solution PDF

Problem A was authored by ko_osaga. Code

Problem B was authored by ko_osaga. Code

Problem C was authored by ko_osaga. Code

Problem D was authored by nong. Code

Problem E was authored by ckw1140. Code

Problem F was authored by ko_osaga. Code

Problem G was authored by ko_osaga. Code

Tutorial of Hello 2020
  • Vote: I like it
  • +191
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it +50 Vote: I do not like it

When I open the editorial for problem E, I see the editorial for problem C instead. Can the author fix this, please?

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

    Sorry, it's fixed now.

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

      Challenge of problem E is nice, but i have no idea how to solve it. Could you provide the solution?

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

You got it wrong for E.

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

Really liked problems B and C :)

»
4 years ago, # |
  Vote: I like it +86 Vote: I do not like it

Problem D is a lot more intuitive if you interpret the input as a collection of rectangles, where you are asked if there is a pair of rectangles that overlaps on one axis but not the other. Then a scanline solution is obvious.

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

    Can you please give some good resources about scanline?

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

    That was the original formulation. I came up with the conference statement to make this problem much natural ;)

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

      This was eye-opening ! So, the input format is $$$x_1, x_2, y_1, y_2$$$ and we have to look for $$$2$$$ rectangles such that their $$$x$$$-axes coincide but their $$$y$$$ do not or the other way around.

      First time, we sort by $$$x$$$ and for every new line segment we process, we keep track of all the line segments it inserts with. We will check if the corresponding $$$y$$$ of the line segment fits in the bounds of all the line segments it has intersected so far.

      • $$$y_1$$$ should not be greater than the smallest $$$y_2$$$ seen so far.
      • $$$y_2$$$ should not be lesser than the greatest $$$y_1$$$ seen so far.

      If you could include this interpretation in the editorial, it would help in understanding a lot :)

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it +1 Vote: I do not like it

        To be honest, I think it very much depends on what you're comfortable with (Specifically, users who love geometry would love this interpretation). For me, it was easier to visualize the problem in the current format (interval format), whereas it took me a while to grasp the rectangle interpretation. It is interesting to see how the problem can be solved in so similar ways for seemingly different interpretations.

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

    I used it too :)

»
4 years ago, # |
  Vote: I like it +76 Vote: I do not like it

When will we be able to submit?

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

    There is another randomized approach involving hashes. You may assign random number to each lecture and then calculate for each interval the xor of numbers assigned to intervals it intersects. Now you should check that every lecture has same hashes in first and second places...

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

      how do you calculate the xor of the intersections?

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it +25 Vote: I do not like it

        I think, scan-line should work. When the interval $$$[l_i,r_i]$$$ opens, you put $$$h_i$$$ in the position $$$r_i$$$ and when this interval closes you take the xor of all numbers on the $$$[l_i, \infty)$$$.

        It should look like this, but it gets WA-6 and I'm to sleepy to debug it properly.

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

          yeah I did same thing but i get wa-6

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

          the WA is not because of hash collision
          you missed the case when 2 intervals completely overlap

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

            Not really, I just made a silly typo in my segment tree code... I got it accepted now: 68205086

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

              Segment Tree is more popular way than multiset for this problem, I think.

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

        It can also be treated as hashing all maximal cliques of the interval graph which should be sufficient for checking the equality of the graphs as the graph is chordal. My code for reference 68181402

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

          Can you tell me where can I learn this stuff about graphs? It would be really helpful of you.

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

        You can look at my submission, I kept two segment trees — in one i put the value of the lecture on the beggining of the lecture and in the other on the end. Then, for each lecture i checked for lectures than do not intersect, so lectures that have end before the current beggining and the same for other side.

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

        I have a rather neat code doing this that might help: 68239280. I used the formula:

        $$$\{\text{Lectures that intersect lecture $$$l$$$}\} = \{\text{Lectures that start before $$$l$$$ ends}\} \setminus \{\text{Lectures that end before $$$l$$$ starts}\}$$$

        . Note that if a lecture ends before $$$l$$$ starts, then it also begins before $$$l$$$ ends so in the subtraction every element of the latter set is contained in the former set. Also note that we do a XOR both when we add and when we remove a set.

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

      My solution uses hashes also :)

      Let's calculate value $$$sumA=\sum_{i \, intersects \, j}(h_i\cdot h_j)$$$ by some modulo for segments in A and the same $$$sumB$$$ for segments in B. Here, $$$h_i$$$ are some random values. This can be calculated with scanline. The answer is "YES" iff $$$sumA=sumB$$$.

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

        yeah me too but i got wa-6

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

          Maybe my code will be helpful: 68181544

          It doesn't use any data structures. Only two scan lines.

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

      You can just treat intersections as long number in binary notification (zero means no intersection with given index's segment, one means intersection) and use its remainder as hash. See my submission https://codeforces.com/contest/1284/submission/68191562

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

      I just leave it here. I also assign random number to each lecture, and then calculate some hashes. But to avoid cases when one segment completely inside in other, I just took complement approach. I get hash of all segments that doesn't intersect with selected. They are those who ends before selected, or starts after selected. So, I have two BIT for each place: one for lectures ending at time X and one for lectures starting at time X. This is done with packed coordinates and four BIT for each set of random identifiers. 68198554

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

    Me too.

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

      My randomised solution also passed.

»
4 years ago, # |
Rev. 2   Vote: I like it +26 Vote: I do not like it

Thank you for setting these wonderful problems. Unlike other geometry probs, E is so beautiful that I was impressed :D

  • »
    »
    4 years ago, # ^ |
      Vote: I like it -29 Vote: I do not like it

    Just what part of E do you think is beautiful? I agree that the model solution doesn't seem bad, but that is only in comparison to how painful writing code for the not-totally-magic solutions is. A problem with many easy to find ugly solutions does not turn good from the existence of a beautiful solution that is very difficult to find.

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

      I don't get the point. If you failed to find good solution, then it's our fault?

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

      Well, I found it really interesting what you can solve it in $$$O(n^2)$$$. 1146H - Satanic Panic is really similar problem and I believe it can only be solved in $$$O(n^3)$$$.

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

        OnionPringles told me about the $$$O(n^2\log n)$$$ solution of that problem. Of course, it's much harder than our problem's solution, in any aspect.

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

          After I found $$$3x_3+4x_4+5x_5$$$ I thought I need $$$x_5$$$... After 4 TLE attempts, I saw the magic :D

»
4 years ago, # |
  Vote: I like it -15 Vote: I do not like it

Seems like you don't understand what "right after" means.

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

Does the following flow solution for F run in time?

Create three sets of nodes A, B, and C. A represents the first set of edges, C represents the second set of edges. We need to match as many nodes in A as we can with nodes in C. Set B represents all the nodes in the tree. Each node in A and C will be connected to the two nodes that the edge it represents in connected to. We then run flow from the nodes in A to the nodes in C.

This graph has O(n) edges and a max flow of O(n).

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

When the codes will be available?

»
4 years ago, # |
  Vote: I like it +12 Vote: I do not like it

For F we can prove that answer always equals $$$n - 1$$$ easily using Hall theorem. Pick any $$$k$$$ edges in first tree, we want to prove that there are at least $$$k$$$ edges in the second tree which can be used to replace at least one of picked edges. Let's remove all picked edges from the tree, then it splits to $$$k + 1$$$ components. For each edge in the second tree let's draw an edge between components containing endpoints of the edge. Since the tree was connected before compressing edges it is still connected now, which means it has at least $$$k$$$ edges which are not self-loops, which means there are at least $$$k$$$ edges which can be used to replace one of picked edges.

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

    Sadly this proof gives no clue on how to find the matching

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

      In my solution (tl;dr here), it just turns out while I'm looking for some characteristics of the matching that it is perfect, and the argument for that is kinda similar to Hall's theorem — it also deals with sets of edges in T2 and adjacent edges in T1. It doesn't seem to be particularly useful for finding a way to compute a matching quickly, though.

»
4 years ago, # |
  Vote: I like it +20 Vote: I do not like it

My solution of F:

Pick a 1 edge (u, v) from the T1, s.t. u is the leaf in T1. We consider a path(u, v) in T2, and take a nearest edge of u in this path(we let (u, w)) (step A). We can find matching, (u, v) in T1 & (u, w) in T2, and remove those edges. For all x($$$x \neq w$$$), if there is a edge (u, x) in T2, we change u to v. it means, remove (u, x) and add(v, x) (step B). As a result, we can remove vertexes u and reduce problem size by one(after operate, T2 remained as tree).

How to simulate? Bottleneck is the step B, changing (u, x) to (v, x). Therefore we don't change all edges, but simply remove (u, w) and add dummy edge (u, v). We have to find nearest non-dummy edge in step A, but it's all. We can easily do it by Link-Cut Tree

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

    We consider a path(u, v) in T2, and take a nearest edge of u in this path(we let (u, w)) (step A).

    Tbh when you have this, there's no need for further tricks or LCT. Just HLD over T1, store not yet taken edges in each path in a set (ordered by depth), DFS over T2 and use HLD to simulate the process for each edge in T2. That's my solution.

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

    I solved step B by merging u,v in T2 by implementing union-find structure on LCT nodes. When merging u and v, cut all preferred children of u and v so that the children can go through union-find structure when they try to access the unpreferred parent. I think it is easy if you have a pre-written LCT code.

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

    You can do binary lifting and dsu, which is much more easier to code than LCT/HLD

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

      I had the same, but tbh in such contests it would be more preferable to just copy LCT.

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

    I updated my solution to F. It is my favorite in this problem set. Hope you liked it too!

»
4 years ago, # |
  Vote: I like it +61 Vote: I do not like it

Here is a more intuitive explanation for E. Sorry if it's mentioned already.

Fix the point $$$p$$$. Translate everything such that $$$p$$$ coincides with the origin. Sort all the other points counter-clockwise. We shall now find the number of quadruples of points that don't form a polygon containing $$$p$$$.

Now consider some point $$$s$$$. Consider the half-plane $$$H$$$ of points $$$t$$$ such that the cross product $$$s \wedge t$$$ is positive. For a quadrilateral with $$$s$$$ to contain $$$p$$$, it has to have at least one point from $$$H$$$ and at least one point not from $$$H$$$. Conversely, we will count the number of quadruples $$$(s, t_1, t_2, t_3)$$$ such that $$$t_1, t_2, t_3 \in H$$$. It is just the binomial coefficient $$$|H| \choose 3$$$.

Now do that for all $$$s$$$ and all corresponding $$$H$$$, in linear time, using the two pointers method.

With iterating over all $$$p$$$ and sorting, the complexity is $$$O (n^2 \log n)$$$.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    This solution works for any size of polygon right? For example if the problem was about triangles instead of quadrilaterals

    thanks for sharing it btw

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

      Looks like, yeah, the same argument about all points being in one half-plane would work for pentagons and more.

      Now, if the problem asks for convex polygons, it gets trickier, even with quadrilaterals.

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

    Where can I learn more about cross products of vectors and how they can be used in geometry problems?

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

      Basically, scalar product and cross product are similar in behavior to cosine and sine of angle between vectors, respectively. Their signs behave the same.

      The upside is that, more often than not, we are given coordinates of points as integers (or rationals). And computing scalar and cross products can be done using integers only. So we don't have to resort to floating point and then deal with a whole additional class of errors because of loss of precision.

      As for more general overview, a Google search lands some nice articles on the first page.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    How can I actually easily find the sign of the cross product between two vectors? I got an idea of how to do it with the angle between them, but it seems ugly and probably prone to bugs.

    Edit: I found a way on Wikipedia, scroll down to the Computation Geometry section.

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

Can someone please explain for B

3

4 2 0 2 0

6 9 9 8 8 7 7

1 6

how is it 7?

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

    Let's say a = [2,0,2,0], b = [9,9,8,8,7,7], c = [6], then the answers are: aa, ab, ac, ba, bb, ca, and cb.

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

    since 2 0 2 0 has an ascent.so total pairs are 3. 2 nd sequence does not have an ascent but pairs (2,2),(2,1) has ascent. similarly for 3rd sequence pairs(3,1) and(3,2) has ascent. so total 7 pairs are possible.

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

      I'm struggling to understand what does "but pairs (2,2),(2,1) has ascent" mean. Can you please elaborate? Thanks!

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

      Thanks I got it!

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

    Let 1, 2, 3 — indexes of arrays. Here is "1 + 2"

    "1 + 3"

    "1 + 1"

    "2 + 2"

    "2 + 1"

    "3 + 1"

    "3 + 2"

    At all — answer 7.

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

For D, removing operation is at time ea_i + 1 ?

UPD: It's fixed.

»
4 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

D can be solved using "Job scheduling " algorithm. Initially we check all the intervals for both the venues individually,whether they overlap,if we get different answer,answer is "NO".

If we get same answer and both timings of both venues don't overlap,then answer is "YES".

If we get "over-lap" for both,there is a possibility that removing some lectures might make one venue overlapping and other non_overlapping

eg: 1 2 3 4

3 4 4 5

4 5 6 7

In this case,we use job scheduling algorithm to find the largest no of lectures that can be present such that,lecture timings don't overlap for venue A.

Keep only those lectures for B,check if answer is different for both venues,do the same thing for venue B.

68206806

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

    AjaySabarish Hi, can you please explain the part about "non over-lap" in a little detail?How is there a possibility that removing some lectures might make one venue overlapping and other non_overlapping? I also thought about job scheduling algo but as mentioned in comments, did not consider such cases like finding interval in a and then checking them in b and vice versa. Do they both not give same result?

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

      Sry there was a typo,now corrected

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

        Still can you explain that point about removing some lectures?

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

          Consider the above example,which I gave

          3

          1 2 3 4

          3 4 4 5

          4 5 6 7

          Now,the timings overlap for both venues,but if you remove lecture 3,timings dont overlap for venue A but overlap for venue B.

          This is the last case which I was talking about,now you have to use job scheduling to find the answer.

          Find the highest number of non overlapping segments for A,it is lecture 1,2.

          Now keep only these lectures for both venues,now the segments for B should also not overlap for "not venue sensitive". But it is overlapping,so it is venue sensitive

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

The test cases in D were very "weak". My solution : 68205621

For very large N, it's enough to only check if each of the lectures have the same number of intersections in A and B. Taking advantage of the fact that it's hard to put up a test case that avoids being fooled that way.

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

    but how will you calculate the intersections in O(n) time.Can you explain once more??

»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Can you share other solutions to E? Except Gassa's (above)

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +45 Vote: I do not like it

    I'll put it short:

    • (By kdh9949 jihoon) Find $$$f(p)$$$ for each point. You can see that the set can enclose $$$p$$$ iff its convex hull contains $$$p$$$. Checking the containment is hard, so sort by angle, and eliminate the set that does not contain $$$p$$$, which reduces to almost similar sweep with model code. I think this is the easiest solution to come up with.
    • (By molamola.) The answer depends on the 2 * (number of convex quadrilaterals) + (number of concave quadrilaterals). We denote this number $$$A$$$. I think the answer is $$$(A - 2\binom{n}{4}) \times (n-4)/2$$$, or something like that. This problem is bit harder, so you need another type of angular sweep like JOI Open 2017 Bulldozer. I think this is more involved to code, but our great tester molamola. took exactly 12 minutes to AC this.
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My solution is pretty much the same as molamola's solution and I think it is not necessary to do a cool angular sweep:
      Let $$$X$$$ be the number of $$$((A,B,C),D)$$$ such that $$$D$$$ lies in $$$ABC$$$ and $$$(A,B,C)$$$ is an unordered tuple. The answer is $$$(n-4)X/2$$$.
      $$$X$$$ can be counted easily: fixing $$$D$$$ and sort other points by the angles, then do a bunch of lower bound.

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

      Thanks for sharing. The solution in Editorial really beautiful, but I don't know. Is that possible to came up with such solution in ~1 hour?

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

        Actually my solution submitted during the contest is exactly same as the tutorial solution. In fact, I tried to compute all of $$$x$$$, $$$y$$$, and $$$z$$$, so I double-counted not only the edges of the convex hull but also the diagonal edges, to obtain three linear equations.

        $$$ x + y + z = {n \choose 5} \\ 5x + 4y + 3z = sth \\ 5x + 6y + 7z = sth $$$

        Unfortunately, this linear system was undetermined, and all I can get was $$$(y + 2z)$$$. That was when I felt quite disappointed. But surprisingly, the answer to the problem happened to be exactly $$$(y + 2z)$$$, so I could finally solve the problem.

        At first, I thought I was lucky enough to find a solution with such unsolvable system. So I headed to this tutorial to read the "official" solution, only to find my solution again. Thanks to your question, I found it in the comments :-)

        68196878

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Just curious,did everyone who solved C in contest,prove the solution?It was not so obvious to me,deciphering and processing what a "framed segment" is,took a lot of time.

Finding pattern was quite difficult,as manually generating test case even for n=4 is difficult

Lot of people solved it,is there any other idea?

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

    Hi, If you now know what a "framed segment" is, then try to formulate number of "framed segment" of a particular length for a given n. For example: if we want to count "framed segement" of length 1. Let's first consider all "framed segment" containing only digit 1. For this "framed segment" to be at leftmost, there are (n — 1)! permutations. Similar argument goes for its other positions as well. This gives us count : (n — 1)! * n. Now, there are total of n single digits like "1" which can make single length "framed segement". Thus now count for all single length "framed segement" is : (n — 1)! * n * n (something missing?). I have tried to explain the solution with single length fragment above with some details missing which I think you will figure out. Please try to come-up with a general formulation for any "framed segment"length x for a given n. Summing it all up will give you the answer. Link to my submission : Here

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

      Thanks a lot,I get the solution,but I am just curious about the high number of submissions,was it so obvious?did everyone actually prove it or used their intuition to get it?

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

        I guess that depends on one's way of counting up to the answer. And from the number of submissions, it feels like people are actually good at counting..:P

»
4 years ago, # |
Rev. 3   Vote: I like it +16 Vote: I do not like it

Hi, I think I found a test case for problem D where my solution gets accepted but it should be incorrect.

5
1 10 1 10
2 20 11 30
11 30 2 20
21 40 21 40
31 50 31 50 

I've checked with the code given in the tutorial, the answer is NO, but my solution gives YES. 68207409

I've modeled it as a graph and put an edge (u, v) if lecture u and v meet. I thought it would be enough to check two things for graph A and B (venue A and B)

  • the number of degrees for each lecture
  • the lecture set of each component

I've submitted it after the contest so it doesn't effect my ratings, but I thought it was worth mentioning.

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

    I made the same mistake. I tried to find a test case where this is not true, but I could not. Thanks you

»
4 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Solution for B [Best :- O(n) Worst :- O(nlogn)]

https://codeforces.com/contest/1284/submission/68210022

The condition for a non-ascent sequence a and a non-ascen sequence b to form an ascenting sequence is

min(a) <max(b)

  1. First traverse the lists and store max and min in two separate vectors.
  2. if a sequence has ascent ie if an element greater than current min or current max occurs then that sequence will always give an ascenting sequence hence do cnt = cnt + 2*n-1 n--; because that sequence will form 2n-1 sequences on concatenation
  3. Sort the max and min vectors then use two pointer approach.

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

    Involving sort gives already nlogn solution) - my code — P. S. I have similar solution, but simpler.

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

Someone please explain me the meaning of the last statement in C. "By observing that there exist exactly n−len+1 pairs with 1≤l≤r≤n,r−l+1=len, we can simply multiply this number for each length, giving a O(n) time solution." Please give any example.

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

    Example of what is it about:

    Consider n of 5 and len of 3

    • 1 2 3

    • 2 3 4

    • 3 4 5

    Permutate each of them, and you will get all framed subarrays for n and len of the example.

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

Can anyone explain to me the solution of problem C in a better and intuitive way?

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

    I have tried to explain in my comment : https://codeforces.com/blog/entry/72804?#comment-570899. I hope it's helpful

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

    let's take n = 5. ar = [1,2,3,4,5] . Now iterate for all possible length of sub-array and count number of good sub-array for that length. k = 1, 2, 3 and so on.

    let take say k = 2 and n = 5. So there are n-k+1 position possible to place k elements i.e If we consider [1,2] then we can place [1,2] in position _ 3 _ 4 _ 5 _ and you can select (n-k+1) elements from n elements to i.e [1,2] , [2,3] , [3,4] and [4,5] . So this is how we got (n-k+1) * (n-k+1) and now we just have to count number of possible permutation of k and (n-k) elements left which is nothing but k! and (n-k)! .** (n-k+1) * (n-k+1) * k! * (n-k)!** is the total answer

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

      But would that not lead to overcounting.
      Consider the case 3 (1 2) 4 5 and 3 1 2 (4 5).
      These 2 permutations are same and will be counted twice, once when we consider 1,2 together and second when 4,5 are taken together.

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

If in question C, we have given a permutation of length n then we need to find happiness... Anyone want to share their approaches ..

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

Shouldn't it be eai + 1 in D tutorial?

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

I had a overkill solution for $$$D$$$ which led to a good data structures problem. While, others have provided much more elegant solutions, this reduced version is a good problem on its own and worth sharing.

Here's the problem:

You are given two sequences $$$a_i$$$ and $$$b_i$$$ of length $$$2N$$$ each. Each number from $$$1$$$ to $$$N$$$ appears exactly twice in both the sequences. You have to solve $$$Q$$$ queries of the following kind:

Given $$$l$$$, $$$r$$$, $$$x$$$ and $$$y$$$, find the set of distinct elements in $$$(l, r)$$$ in $$$a$$$ is exactly equal to the set of distinct elements in $$$(x, y)$$$ in $$$b$$$. That is, any number $$$u$$$ has an appearance in segment $$$(l, r)$$$ in $$$a$$$ if and only if it has an appearance in segment $$$(x, y)$$$ in $$$b$$$. Try to solve this online in $$$O((N+Q)\log(N))$$$.

Think of how you can reduce today's $$$D$$$ into this problem.

My code for today's D: 68189310

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

In D: "Event removing interval [sbi, ebi] from S at time ebi+1."

ko_osaga, I think you made an error here, it should be eai + 1 instead

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Problem B can also be solved in $$$O(n)$$$. Be $$$asc$$$ the number of sequences that have an ascent. For each sequence, check if it's non-increasing. If it isn't any concatenation we do will have an ascent, so we can add $$$n$$$ to our answer and $$$1$$$ to $$$asc$$$. Now be $$$s$$$ a non-increasing sequence and let's set it as the right part of the concatenation. We will only have an ascent in the concatenation if the left part already has an ascent or has an element smaller than any element in $$$s$$$, specially it's maximum. We have $$$asc$$$ sequences of the first type, so that's easy, and for the second part we can precalculate it by creating an array $$$minfreq$$$ where we store the minimum of each non-increasing sequence in it's position (as $$$s_{i,j} < 10^6$$$) and do a sweep from $$$1$$$ to $$$10^6$$$ to accumulate our sum ($$$minfreq[i] = minfreq[i-1] +minfreq[i]$$$). Now we have our answer for the second part in position $$$minfreq[max(s)-1]$$$, and we can just add both parts to our answer. Since we can precalculate $$$minfreq$$$, $$$max(s)$$$ and $$$asc$$$ in $$$O(n)$$$ and the answer can be calculated in $$$O(1)$$$ using our precalculations total complexity is $$$O(n)$$$

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

    Yeah, the same idea with you!

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

    I did the same, but this is not O(N). The time Complexity will be O(n + maxELE) where maxELE is the largest sequence element seen in input.

    We were lucky that the constraint on that wasn't 10^9.

    Also consider cases in which n = 5 but the elements are still very large, our code would still take lot of time to execute.

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

      Yeah that's true, the editorial's solution is more general for that same reason

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

    I cant understand the minfreq[i]=minfreq[i−1]+minfreq[i] . can you explain me

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

      It's called accumulated sum. Basically we want minfreq[i] to be the frequency of all numbers $$$\leq$$$ to i, so we need to push our previous array position to our current one, so that we also take into account the occurences of numbers < i, and not just equal to i

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

How to count different quadrilaterals in problem E?

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

    For example, for each pair of points $$$(i, j)$$$, we can find the number of points on one side of the line i-j ($$$a$$$), the number of points on the other side ($$$N-2-a$$$), sum that up, divide by 2 and subtract $$$2{N\choose 4}$$$. Why? For each 4-tuple of points, if one of them is inside the triangle formed by the other 3 (their convex hull is a triangle), we get 3 lines (inner point, some other point) that are counted here, and when their convex hull is a quadrilateral, we get 2 such lines — its diagonals; we subtract (2 * number of 4-tuples) to get the number of 4-tuples where one point is inside.

    How to find these $$$a$$$ for each pair $$$(i, j)$$$ fast? Let's say that $$$i$$$ is fixed, sort all remaining points by their angle around point $$$i$$$, then consider a line that crosses $$$i$$$, start rotating it and whenever it crosses one of these points, update the current value of $$$a$$$.

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

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

Could anyone give me a more elaborated explanation for problem D, I didn't grasp the editorial at all.

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Expected a matroid problem, as ko_osaga took matroid class last semester XD

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

Hack Test for D 1284D - New Year and Conference

4 1 10 51 60 2 20 44 52 3 40 43 45 42 45 50 50

»
4 years ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

Actually, Problem G can be solved easily by matroid intersection. Consider two matroid M1(S,I),M2(S,I), S is the set of wall, M1 is a graph matroid , M2 is a matroid which any black cell has at least to side without wall. Code: https://codeforces.com/contest/1284/submission/68215804

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

Is there anyone who solved D using coordinate compression and prefix sum ? If so, could you please share your submission.

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

Why does D need to check in two directions? If I check in one direction, I get wrong answer at 9th point. But I think it is appropriate to check in only one direction.

»
4 years ago, # |
  Vote: I like it -19 Vote: I do not like it

MikeMirzayanov may as well check how many visits were made to this page and later to this page in contest time

»
4 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Re: "Hopefully, the first 80 tests were good enough for the contest."

My random solution fails on test 87 :) Great job making the tests indeed!

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

In Problem D, why does this solution not work? My Solutions is this.

Sort lectures according to their start-ending time in both venue, Then decide every lecture if it intersects with others in their own venue.

If there is at least one lecture that make difference in intersecting in both venue, then Subset can not be made. So the answer is no. If every problem either intersects in both venue or does not intersect in both venue then answer is yes. Here is my implementation 68294866

Please someone enlighten me where I am misunderstanding.

»
4 years ago, # |
  Vote: I like it -13 Vote: I do not like it

In problem D, I got wrong answer on test case 14. Can somebody please help.

»
4 years ago, # |
  Vote: I like it +18 Vote: I do not like it

2020 begins with two matroid problems. XD

btw, Challenge in Problem F is called Strong Basis Exchange as in here.

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

I am not able to understand problem B's solution.. can anyone please help me out..??

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

Why don't we have to consider the case when there's some period intersecting in A and not intersecting in B? Doesn't that mean that sometimes our code will say 'YES' but the answer is 'NO'. Why? 1284D - New Year and Conference. EDIT: Ok, I just didn't notice the part of the code where he does the same thing but reversed.

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

What is the hash approach for the problem D?

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

there is a proof for C solution ?

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

    Here is something, that I could think of.

    For each permutation, we have the same $$$r-l$$$. This value varies from $$$0$$$ to $$$n-1$$$ for all $$$n$$$. Now let us consider $$$r-l=d$$$, as a general case.

    For each $$$n$$$, we have $$$n-d$$$ pairs of $$$[l, r]$$$, where $$$r-l=d$$$. Also for all numbers from $$$1$$$ to $$$n$$$, we have $$$n-d$$$ pairs of type $$$[i, j]$$$ such that $$$j-i=d$$$.

    For a segment to be framed, all the other places for each $$$[l, r]$$$ must be occupied by each integer from $$$[i, j]$$$. Therefore, we have $$$d+1$$$ numbers to be arranged in this interval $$$[l, r]$$$ and $$$n-d-1$$$ to be arranged in $$$[1, l-1]$$$ and $$$[r+1, n]$$$. This can be done in $$$(d+1)! * (n-d-1)!$$$ ways.

    But we have $$$n-d$$$ pairs of $$$[l, r]$$$ and $$$n-d$$$ pairs of $$$[i, j]$$$, each of which can occupy this segment. Therefore the answer becomes summation over all $$$d$$$ from $$$0$$$ to $$$n-1$$$: $$$ans = ans + (n-d) * (n-d) * (d+1)! * (n-d-1)!$$$

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

In problem C , do we consider that the numbers inside a particular segment [l,r] could be different such that, max-min = r-l

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

In Problem D I added elements in the segment tree in the decreasing order of eai and then I queried for the previous range if the min of the ls and the maxr intersect with the particular index of a I am addding . I am getting a WA at Test Case 7 for this submission.

This is my submission link: https://codeforces.com/contest/1284/submission/91535000

Can somebody help me with this solution where I went wrong?

Or is there anyway I can look at the whole testcase then please reply here about how can I do that?

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

    Never Mind I made a silly typo in the cmp2 function.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, I am not able to understand the editorial for problem C. can anyone break it down in easy way please ?

»
3 years ago, # |
  Vote: I like it +91 Vote: I do not like it

Hello, this seems to be broken (perhaps a sign of how the year 2020 has been so far)

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

This question relates to problem B. I have a question with the second example input. Here is the input:

3
4 2 0 2 0
6 9 9 8 8 7 7
1 6

I believe all arrays have an ascent. In the first array, the pair $$$(i, j) = (3, 4)$$$ works. ($$$a_3 = 0, a_4 = 2.$$$) In the second array, the pair $$$(i, j) = (1, 2)$$$ works. ($$$a_1 = 6, a_2 = 9.$$$) In the third array, the pair $$$(i,j) = (1, 2)$$$ works. ($$$a_1 = 1, a_2 = 6.$$$)

Thus, shouldn't all pairs of arrays in this case work? There are $$$9$$$ such pairs, but the answer to this should be $$$7.$$$ What is wrong with my reasoning here?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Editorials that didn't age well...

»
3 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Sorry for the issue with editorials. I think there is a timeout issue from Polygon. Since I can't resolve it, I will just rewrite it as a PDF form and upload here.

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

Weak test cases for D. Consider the following test case

3
1 3 1 2
4 6 4 5
5 7 2 3

My accepted solution gives YES but the answer is NO.

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

In case someone needs help with problem B, this might help.