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

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.

When will we be able to submit?

Randomised sol for D

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

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

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

When the codes will be available?

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.

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

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

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?

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

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

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.

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

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

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

https://codeforces.net/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.

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.

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

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

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

Насчет E. Мне кажется, основное решение должно быть наиболее понятным, а не "наиболее красивым по мнению автора"

Привет. Я новичок и не дается с первого десятка раз и самостоятельно. Прошу помочь (тыкнуть пальцем), что именно влияет на сложность программы ( по времени ) , облегчил то, чем подсказали и что знал. Язык Python. n, all, h = int(input()), [], 0

for _ in range(n):
    a = list(map(int, input().split()))
    b = a[1:]
    if b + b != sorted(b + b)[::-1]:
        h += 1
    for i in all:
        if i + b != sorted(i + b)[::-1] and len(all) > 0:
            h += 1
        if b + i != sorted(b + i)[::-1] and len(all) > 0:
            h += 1
    all.append(b)
 
print(h)

Что еще возможно?

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

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

How to count different quadrilaterals in problem E?

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

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

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.net/contest/1284/submission/68215804

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

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.

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 ?

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

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.net/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?

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

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

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?

Editorials that didn't age well...

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.

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.

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