**New Year and Naming**

**New Year and Ascent Sequence**

**New Year and Permutation**

**New Year and Conference**

**New Year and Castle Construction**

**New Year and Social Network**

This problem can be cracked in polynomial time with various approaches. I'll introduce a few of them.

#### $$$O(n^3)$$$

As stated in the problem, this problem is a straightforward bipartite matching problem. With a simple DFS or union-find, you can construct a bipartite graph in the statement, and use well-known maximum matching algorithm.

#### $$$O(n^{1.5}\log n)$$$

By using a similar solution to Codeforces 786E: ALT, you can reduce the time complexity to $$$O(n^{1.5}\log n)$$$. The author didn't manage to squeeze this approach in time.

#### $$$O(n^2)$$$:

By looking at the sample, it seems that $$$m = n-1$$$ always holds for some reason. In other words, the given graph always has a perfect matching. It turns out that this guess is true. Let's try to prove it using induction.

#### Inductive Proof. Attempt 1

We induct on the quantity $$$|E(T_1) - E(T_2)|$$$. If the quantity is zero, then we can find an obvious bijection. Otherwise, we can find some edge $$$e \in E(T_1) - E(T_2)$$$. Since our goal is to reduce the difference, it would be reasonable to replace this edge to some other edge $$$f \in E(T_2) - E(T_1)$$$. Hopefully, we can show the following:

**Lemma 1.** For any $$$e \in E(T_1) - E(T_2)$$$, there exists some edge $$$f \in E(T_2) - E(T_1)$$$ such that $$$T_1 - {e} + {f}$$$ is a tree.

**Proof.** $$$T_1 - {e}$$$ have two components. If there exists an edge $$$f$$$ that connects these two parts, we are done. Otherwise, $$$T_2$$$ has no edges connecting these parts, finding a cut.

Then, we can simply add the bijection $$${e \rightarrow f}$$$, replace the edge $$$e$$$ with $$$f$$$ in $$$T_1$$$, and continue. Right? Sadly, this is wrong as it is changing the tree $$$T_1$$$. Although we found the pair of tree $$$(T_1 - {e} + {f}, T_2)$$$ with less value $$$|E(T_1) - E(T_2)|$$$, finding a bijection over $$$T_1 - {e} + {f}$$$ to $$$T_2$$$ is a different story, thus the proof fails.

#### Inductive Proof. Attempt 2

It would be good to make $$$T_1$$$ static, since otherwise our induction will fail. Then, what about repeating induction over $$$(T_1, T_2 + {e} - {f})$$$? Everything is good, but then we should also guarantee $$$T_2 + {e} - {f}$$$ is a tree. Is it possible?

**Lemma 2.** For any $$$e \in E(T_1) - E(T_2)$$$, there exists some edge $$$f \in E(T_2) - E(T_1)$$$ such that $$$T_1 - {e} + {f}$$$ and $$$T_2 + {e} - {f}$$$ is a tree.

**Proof.** $$$T_2 + {e}$$$ has exactly one cycle $$$C$$$. Since $$$T_2 + {e} - {f}$$$ should remain acyclic, $$$f \in C$$$ should hold. The cycle consists of edge $$$e$$$ and path from $$$T_2$$$, we should find such $$$f$$$ from the path in $$$T_2$$$, such that its endpoint connects two different component of $$$T_1 - {e}$$$. Label the vertices in the path by its component membership of $$$T_1 - {e}$$$. Since $$$e$$$ itself connects the different component, there should exist a edge in the path, which connects different component. Take it.

Now, as $$$T_1 - {e} + {f}, T_2 - {f} + {e}$$$ is both acyclic, we can create the bijection $$${e \rightarrow f}$$$, and also take $$$(T_1, T_2 - {f} + {e})$$$ for the induction stage. This proof also gives a straightforward $$$O(n^2)$$$ algorithm for finding the answer.

#### $$$O(n\log n)$$$

When we fix $$$e \in E(T_1) - E(T_2)$$$, finding the component where each vertices lie is easy: This can be done by preprocessing $$$T_1$$$ with a single depth-first search. Using this to find the $$$f$$$ is a different story: We have dynamically changing tree of $$$T_2$$$, which is hard to maintain.

On the other hand, since Lemma 2 is symmetric, we can rather fix $$$f \in E(T_2) - E(T_1)$$$ and find $$$e$$$ instead. In this case, if we can know which subtree that a vertex belongs for $$$T_2 - {f}$$$:

- If $$$f = {u, v}$$$, find the path between $$$u \rightarrow v$$$ in $$$T_1$$$
- If $$$LCA(u, v)$$$ belongs to same component in $$$u$$$, then find $$$f$$$ in path $$$v \rightarrow LCA(u, v)$$$. Otherwise, find $$$f$$$ in path $$$u \rightarrow LCA(u, v)$$$.
- Now, you can find $$$e$$$ using binary search on paths, which can be implemented with binary lifting

Since $$$T_1$$$ is static, we can afford all these operation in $$$O(n \log n)$$$ time preprocessing. Now the point is to maintain $$$T_2$$$ to support subtree membership query. This can be done straightforwardly using Link-Cut tree or Euler Tour tree using $$$O(\log n)$$$ query time, which results in $$$O(n\log^2 n)$$$ time, but this is too slow (at least for us) to pass.

Now from this point, we will assume $$$E(T_1) \cap E(T_2) = \emptyset$$$. We have a freedom over choosing $$$f$$$, so let's choose the $$$f$$$ as the edge connecting the leaf. The good property of leaf is that the subtree membership query is very easy: You can simply compare the vertex number. So, if we choose such $$$f$$$, we can find $$$e$$$ easily.

What about changing the tree $$$T_2$$$ to $$$T_2 - {f} + {e}$$$ ? Note that, After $$$T_2$$$ becomes $$$T_2 - {f} + {e}$$$, we don't have to care about $$$e$$$ because it's in the intersection of $$$T_1$$$ and $$$T_2$$$. We can think about **contracting** the edge $$$e$$$: After adding an edge $$$e$$$ we can not delete, so in the component point of view, they are always in the same component: So we can remove the leaf edge $$$f$$$, and contract the ends of $$$e$$$. For the data structure to maintain these components, we can use Union-Find.

Writer: ko_osaga

**Challenge:** Lemma 2 works for the general matroid base set. So for any pair of matroid base set from same ground set, perfect matching exists in the exchange graph. Prove it.

**Seollal**

Writer: ko_osaga

**Trivia 1:** This problem's working name was "yet-another-nowruz". You may want to compare the statement of this problem and IOI 2017 Nowruz ;)

**Trivia 2:** Huge applause to kriii who created amazing tests to break random solutions of G. We were very afraid of random solutions because of the huge difficulty gap between ABCDE/FG. Hopefully, the first 80 tests were good enough for the contest. But that's not the end of the story: we have 140 tests ;)

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

Sorry, it's fixed now.

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

You got it wrong for E.

Really liked problems B and C :)

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.

Can you please give some good resources about scanline?

Topcoder Tutorials

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

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.

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

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.

I used it too :)

When will we be able to submit?

In most contests, submission window opens 2 hours after the contest I guess.

Why people downvote this?

Because it isn't true. Usually you can submit a few minutes after system tests are over.

Now submission is open.

Exactly 2 hours :)

Randomised sol for D

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

how do you calculate the xor of the intersections?

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.

yeah I did same thing but i get wa-6

the WA is not because of hash collision

you missed the case when 2 intervals completely overlap

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

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

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

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

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.

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

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

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

yeah me too but i got wa-6

Maybe my code will be helpful: 68181544

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

thanks

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

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

Me too.

My randomised solution also passed.

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

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.

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

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)$$$.

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.

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

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

Right after systest. I'm sorry for F.

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

Actually, nevermind, this just doesn't work

When the codes will be available?

Code is available now.

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.

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

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.

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

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.

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.

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

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

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

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'tform 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)$$$.

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

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

convexpolygons, it gets trickier, even with quadrilaterals.Where can I learn more about cross products of vectors and how they can be used in geometry problems?

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.

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.

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?

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.

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.

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

Thanks I got 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.

Got it guys. Thanks a lot.

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

UPD: It's fixed.

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

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

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?

Sry there was a typo,now corrected

Still can you explain that point about removing some lectures?

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

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.

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

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

I'll put it short:

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.

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?

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.

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

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?

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

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?

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

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

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

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)

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

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

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

`cnt = cnt + 2*n-1`

`n--;`

because that sequence will form 2n-1 sequences on concatenationSort the max and min vectors then use two pointer approach.

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

You use "sort", the complexity is already get O(nlogn).

But if all elements have ascent there will be no elements left to sort. That's why O(n) in best case.

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.

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.

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

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

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

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.

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

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

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

Shouldn't it be

eai + 1in D tutorial?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

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

Sorry, fixed.

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

Yeah, the same idea with you!

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.

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

Can you explain what is an ascent sequence? With an example.

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

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

How to count different quadrilaterals in problem E?

1146H - Satanic Panic

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

Auto comment: topic has been updated by ko_osaga (previous revision, new revision, compare).Could anyone give me a more elaborated explanation for problem D, I didn't grasp the editorial at all.

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

matroid fan club!

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

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?

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

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.

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

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.

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

How does that problem help?

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!

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.

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

can some one explain me the editorial of E . I did not got the explanation.THANKS.

2020 begins with two matroid problems. XD

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

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

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.

What is the hash approach for the problem D?

there is a proof for C solution ?

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

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