ko_osaga's blog

By ko_osaga, history, 19 months ago,

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

• +191

 » 19 months ago, # |   +50 When I open the editorial for problem E, I see the editorial for problem C instead. Can the author fix this, please?
•  » » 19 months ago, # ^ |   +4 Sorry, it's fixed now.
•  » » » 16 months ago, # ^ |   0 Challenge of problem E is nice, but i have no idea how to solve it. Could you provide the solution?
 » 19 months ago, # |   +5 You got it wrong for E.
 » 19 months ago, # |   0 Really liked problems B and C :)
•  » » 10 months ago, # ^ |   0 Can you explain the last line of the editorial's code for B ?
 » 19 months ago, # |   +86 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.
•  » » 19 months ago, # ^ |   0 Can you please give some good resources about scanline?
•  » » » 19 months ago, # ^ |   +4
•  » » 19 months ago, # ^ |   +33 That was the original formulation. I came up with the conference statement to make this problem much natural ;)
•  » » » 19 months ago, # ^ |   0 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 :)
•  » » » » 19 months ago, # ^ | ← Rev. 2 →   +1 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.
•  » » 18 months ago, # ^ |   0 I used it too :)
 » 19 months ago, # |   +76 When will we be able to submit?
•  » » 19 months ago, # ^ |   -38 In most contests, submission window opens 2 hours after the contest I guess.
•  » » » 19 months ago, # ^ |   -10 Why people downvote this?
•  » » » » 19 months ago, # ^ |   +22 Because it isn't true. Usually you can submit a few minutes after system tests are over.
•  » » 19 months ago, # ^ |   +9 Now submission is open.
•  » » » 19 months ago, # ^ |   +48 Exactly 2 hours :)
 » 19 months ago, # |   +5
•  » » 19 months ago, # ^ |   +59 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...
•  » » » 19 months ago, # ^ |   0 how do you calculate the xor of the intersections?
•  » » » » 19 months ago, # ^ | ← Rev. 2 →   +25 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.
•  » » » » » 19 months ago, # ^ |   0 yeah I did same thing but i get wa-6
•  » » » » » 19 months ago, # ^ |   0 the WA is not because of hash collision you missed the case when 2 intervals completely overlap
•  » » » » » » 19 months ago, # ^ |   0 Not really, I just made a silly typo in my segment tree code... I got it accepted now: 68205086
•  » » » » » » » 18 months ago, # ^ |   -10 Segment Tree is more popular way than multiset for this problem, I think.
•  » » » » 19 months ago, # ^ |   +13 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
•  » » » » » 19 months ago, # ^ |   0 Can you tell me where can I learn this stuff about graphs? It would be really helpful of you.
•  » » » » 19 months ago, # ^ |   0 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.
•  » » » » 19 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 19 months ago, # ^ | ← Rev. 2 →   +14 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$.
•  » » » » 19 months ago, # ^ |   0 yeah me too but i got wa-6
•  » » » » » 19 months ago, # ^ |   0 Maybe my code will be helpful: 68181544It doesn't use any data structures. Only two scan lines.
•  » » » » » » 19 months ago, # ^ |   0 thanks
•  » » » 19 months ago, # ^ |   0 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
•  » » » 19 months ago, # ^ |   0 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
•  » » 19 months ago, # ^ |   0 Me too.
•  » » » 19 months ago, # ^ |   0 My randomised solution also passed.
 » 19 months ago, # | ← Rev. 2 →   +26 Thank you for setting these wonderful problems. Unlike other geometry probs, E is so beautiful that I was impressed :D
•  » » 19 months ago, # ^ |   -29 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.
•  » » » 19 months ago, # ^ |   +62 I don't get the point. If you failed to find good solution, then it's our fault?
•  » » » 19 months ago, # ^ | ← Rev. 2 →   0 Well, I found it really interesting what you can solve it in $O(n^2)$. 1146H - Сатанинская паника is really similar problem and I believe it can only be solved in $O(n^3)$.
•  » » » » 19 months ago, # ^ |   0 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.
•  » » » » » 19 months ago, # ^ |   +5 After I found $3x_3+4x_4+5x_5$ I thought I need $x_5$... After 4 TLE attempts, I saw the magic :D
 » 19 months ago, # |   -15 Seems like you don't understand what "right after" means.
•  » » 19 months ago, # ^ |   -16 Right after systest. I'm sorry for F.
 » 19 months ago, # |   0 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).
•  » » 19 months ago, # ^ |   0 Actually, nevermind, this just doesn't work
 » 19 months ago, # |   0 When the codes will be available?
•  » » 19 months ago, # ^ |   0 Code is available now.
 » 19 months ago, # |   +12 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.
•  » » 19 months ago, # ^ |   +10 Sadly this proof gives no clue on how to find the matching
•  » » » 19 months ago, # ^ |   0 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.
 » 19 months ago, # |   +20 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
•  » » 19 months ago, # ^ |   0 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.
•  » » 19 months ago, # ^ |   0 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.
•  » » 19 months ago, # ^ |   0 You can do binary lifting and dsu, which is much more easier to code than LCT/HLD
•  » » » 19 months ago, # ^ |   0 I had the same, but tbh in such contests it would be more preferable to just copy LCT.
•  » » 19 months ago, # ^ |   +20 I updated my solution to F. It is my favorite in this problem set. Hope you liked it too!
 » 19 months ago, # |   +61 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)$.
•  » » 19 months ago, # ^ | ← Rev. 2 →   +10 This solution works for any size of polygon right? For example if the problem was about triangles instead of quadrilateralsthanks for sharing it btw
•  » » » 19 months ago, # ^ |   0 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.
•  » » 19 months ago, # ^ |   +10 Where can I learn more about cross products of vectors and how they can be used in geometry problems?
•  » » » 19 months ago, # ^ |   0 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.
•  » » 19 months ago, # ^ | ← Rev. 2 →   +10 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.
 » 19 months ago, # |   0 Can someone please explain for B34 2 0 2 06 9 9 8 8 7 71 6how is it 7?
•  » » 19 months ago, # ^ |   0 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.
•  » » 19 months ago, # ^ |   0 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.
•  » » » 19 months ago, # ^ |   0 I'm struggling to understand what does "but pairs (2,2),(2,1) has ascent" mean. Can you please elaborate? Thanks!
•  » » » 19 months ago, # ^ |   0 Thanks I got it!
•  » » 19 months ago, # ^ |   0 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.
•  » » 19 months ago, # ^ |   0 Got it guys. Thanks a lot.
 » 19 months ago, # | ← Rev. 2 →   +3 For D, removing operation is at time ea_i + 1 ?UPD: It's fixed.
 » 19 months ago, # | ← Rev. 4 →   0 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_overlappingeg: 1 2 3 4 3 4 4 5 4 5 6 7In 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
•  » » 19 months ago, # ^ |   0 codingkshatriya 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?
•  » » » 19 months ago, # ^ |   0 Sry there was a typo,now corrected
•  » » » » 19 months ago, # ^ |   0 Still can you explain that point about removing some lectures?
•  » » » » » 19 months ago, # ^ |   0 Consider the above example,which I gave 31 2 3 43 4 4 54 5 6 7Now,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
 » 19 months ago, # |   +5 The test cases in D were very "weak". My solution : 68205621For 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.
•  » » 14 months ago, # ^ |   0 but how will you calculate the intersections in O(n) time.Can you explain once more??
 » 19 months ago, # |   +10 Can you share other solutions to E? Except Gassa's (above)
•  » » 19 months ago, # ^ | ← Rev. 3 →   +45 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.
•  » » » 19 months ago, # ^ |   0 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.
•  » » » 19 months ago, # ^ |   +10 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?
•  » » » » 19 months ago, # ^ | ← Rev. 3 →   +13 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
 » 19 months ago, # |   +3 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 difficultLot of people solved it,is there any other idea?
•  » » 19 months ago, # ^ |   +2 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
•  » » » 19 months ago, # ^ |   0 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?
•  » » » » 19 months ago, # ^ |   0 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
 » 19 months ago, # |   0 So, i'm fairly new to Cp and problems involving combinatronics. So can people please help me with valuable resources to learn combinatronics for competitive coding? Thank you :)
 » 19 months ago, # | ← Rev. 3 →   +16 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. 68207409I'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.
•  » » 19 months ago, # ^ |   +1 I made the same mistake. I tried to find a test case where this is not true, but I could not. Thanks you
 » 19 months ago, # | ← Rev. 4 →   0 Solution for B [Best :- O(n) Worst :- O(nlogn)]https://codeforces.com/contest/1284/submission/68210022The condition for a non-ascent sequence a and a non-ascen sequence b to form an ascenting sequence ismin(a)
•  » » 19 months ago, # ^ | ← Rev. 6 →   0 Involving sort gives already nlogn solution) - my code — P. S. I have similar solution, but simpler.
•  » » 19 months ago, # ^ |   0 You use "sort", the complexity is already get O(nlogn).
•  » » » 19 months ago, # ^ |   0 But if all elements have ascent there will be no elements left to sort. That's why O(n) in best case.
 » 19 months ago, # |   0 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.
•  » » 19 months ago, # ^ |   0 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.
 » 19 months ago, # |   0 Can anyone explain to me the solution of problem C in a better and intuitive way?
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 I have tried to explain in my comment : https://codeforces.com/blog/entry/72804?#comment-570899. I hope it's helpful
•  » » 19 months ago, # ^ |   0 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
•  » » » 13 months ago, # ^ |   0 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.
 » 19 months ago, # |   0 If in question C, we have given a permutation of length n then we need to find happiness... Anyone want to share their approaches ..
•  » » 19 months ago, # ^ |   0 I have tried to explain in my comment : https://codeforces.com/blog/entry/72804?#comment-570899. I hope it's helpful
•  » » » 19 months ago, # ^ |   0 What I'm saying is that permutation is fixed, i.e permutation of length n is given then we have to find the happiness. Sry if I don't understand what u r trying to say..
 » 19 months ago, # |   +4 Shouldn't it be eai + 1 in D tutorial?
 » 19 months ago, # |   0 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
 » 19 months ago, # |   0 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
•  » » 19 months ago, # ^ |   0 Sorry, fixed.
 » 19 months ago, # |   +8 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)$
•  » » 19 months ago, # ^ |   0 Yeah, the same idea with you!
•  » » 19 months ago, # ^ |   0 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.
•  » » » 19 months ago, # ^ |   0 Yeah that's true, the editorial's solution is more general for that same reason
•  » » 19 months ago, # ^ |   0 Can you explain what is an ascent sequence? With an example.
•  » » 19 months ago, # ^ |   0 I cant understand the minfreq[i]=minfreq[i−1]+minfreq[i] . can you explain me
•  » » » 19 months ago, # ^ |   0 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
 » 19 months ago, # |   0 How to count different quadrilaterals in problem E?
•  » » 19 months ago, # ^ |   0
•  » » 19 months ago, # ^ |   +3 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$.
 » 19 months ago, # |   +1 Auto comment: topic has been updated by ko_osaga (previous revision, new revision, compare).
 » 19 months ago, # |   +4 Could anyone give me a more elaborated explanation for problem D, I didn't grasp the editorial at all.
 » 19 months ago, # |   +1 Expected a matroid problem, as ko_osaga took matroid class last semester XD
•  » » 19 months ago, # ^ |   +1
 » 19 months ago, # |   0 Hack Test for D 1284D - Новый год и конференция4 1 10 51 60 2 20 44 52 3 40 43 45 42 45 50 50
 » 19 months ago, # |   0 can someone please explain this problem (New year and conference(1284D) in simple words ).can't get it.what we are ought to do in this problem?
 » 19 months ago, # | ← Rev. 2 →   +10 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
 » 19 months ago, # |   0 Could anyone explain the solution to 1284D, the set S for time points is not clear to me at all, kindly explain the question in your words too, i'd appreciate it.
 » 19 months ago, # |   0 Is there anyone who solved D using coordinate compression and prefix sum ? If so, could you please share your submission.
 » 19 months ago, # |   0 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.
 » 19 months ago, # |   -19 MikeMirzayanov may as well check how many visits were made to this page and later to this page in contest time
•  » » 19 months ago, # ^ |   -7 How does that problem help?
 » 19 months ago, # |   +17 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!
 » 19 months ago, # |   0 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 68294866Please someone enlighten me where I am misunderstanding.
 » 19 months ago, # |   0 can some one explain me the editorial of E . I did not got the explanation.THANKS.
 » 19 months ago, # |   +18 2020 begins with two matroid problems. XDbtw, Challenge in Problem F is called Strong Basis Exchange as in here.
 » 19 months ago, # |   0 I am not able to understand problem B's solution.. can anyone please help me out..??
 » 19 months ago, # | ← Rev. 2 →   0 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 - Новый год и конференция. EDIT: Ok, I just didn't notice the part of the code where he does the same thing but reversed.
 » 19 months ago, # |   0 What is the hash approach for the problem D?
 » 18 months ago, # |   0 there is a proof for C solution ?
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 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 is 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)!
 » 18 months ago, # |   0 This is my approach to solved D problem : 1.Check venue A,whether there is exist overlap lectures 2.Check venue B,whether there is exist overlap lectures 3.isOverlap(A) XOR isOverlap(B). But.. why i got wrong answer in test case 5 ?? this is my source code https://codeforces.com/contest/1284/submission/69873534
 » 15 months ago, # |   0 In problem C , do we consider that the numbers inside a particular segment [l,r] could be different such that, max-min = r-l
 » 13 months ago, # |   0 Those who are facing problem in understanding the solution of Problem B ( New Year and Ascent Sequence ), can refer to my solution : My Solution.
 » 11 months ago, # | ← Rev. 2 →   0 Problem C: Let len=r−l+1. We have len! possible orders inside the segment.Why we don't care about the numbers in that range?
 » 11 months ago, # |   0 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/91535000Can 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?
•  » » 11 months ago, # ^ |   0 Never Mind I made a silly typo in the cmp2 function.
 » 8 months ago, # |   0 Hi, I am not able to understand the editorial for problem C. can anyone break it down in easy way please ?
 » 7 months ago, # |   +91 Hello, this seems to be broken (perhaps a sign of how the year 2020 has been so far)
•  » » 7 months ago, # ^ |   0 MikeMirzayanov please take a look, thanks!
 » 7 months ago, # | ← Rev. 2 →   0 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?
 » 7 months ago, # |   0 Editorials that didn't age well...
 » 7 months ago, # |   +21 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.
 » 2 months ago, # | ← Rev. 2 →   0 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.