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://mirror.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.

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)

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