We need intersection between official contest and round because we want to prevent cheating from onsite participants.

yes, is very good

Good Luck!

I'm sorry.This sentence was sent by my classmates.

Bless all of you!

Div-2 rounds are held with extended ACM-ICPC rule, so there is no point distribution.

-_- sad -_-

If you are registered onto the contest you are participating.

But until you did any submissions the rating wouldn't count for you

Time to read comments Credit : Adibov

on amoo_safar arm

C137 where is your Morty?

We want a 'Rick and Morty' special CF Round :D

Silly me just looked at submission counts now, I spent most time on E thinking it might be not too hard :P

6th pretest may be 2 2 <= <<

output is Yes

3 3
<<<
<<=
<<=

Answer:

Yes
1 2 2 
3 3 2

try this 4 0 0 1 1 1 1 2 2

I fixed this case to pass test 4)

make the dsu tree and do a preorder traversal

You can do it using only vectors. In order to unite 2 sets just append shortest vector to the longest one. Overall complexity will be O(nlogn).

i think sort -> element reallocation 0>0, 1>n-1, 2>1, 3>n-2, ...

2, 4, ... , n — 3, n — 1, n, n — 2, n — 4, ... , 3, 1

1. sort the array in decreasing order(array a).
2. take another array(array b).
3. b[n/2] = a[0]; p1 = n/2, p2 = n/2;
4. for(i = 1; i;){ p1++, p2--; if(p1 < n){ b[p1] = a[i]; i++; } if(p2 >= 0){ b[p2] = a[i]; i++; } }
5. print b;

C: https://www.hackerearth.com/practice/algorithms/greedy/basics-of-greedy-algorithms/practice-problems/algorithm/hunger-games/description/

Would you prefer if two harder problems used math rather than two easier problems?

That's exactly how I wrote during contest!

My submission's here

#define int long long int

They overflowed but then returned back. It's like you calculate answer modulo 2³¹. Since it's always less than 2³¹ it will be correct in the end.

I am not sure, but in those particular cases the compiler could be doing some optimizations by removing the multiplication (it is possible).

Even if that isn't the case, it still works. Consider that overflow is actually predictable. For example in this particular case:

(10^7+2)*(10^7+2) - (10^7) * (10^7) = 316447236 - 276447232 = 4 * 10^7 + 4 as expected. The thing here is that when it overflows, you get "wrapped" around, i.e similar to taking modulo 2^32. For ex. 102 - 100 = 2 = 102 - 100 (mod 70), but 150 - 60 = 90 != 150 - 60 (mod 70) = 20. When the difference is small enough (smaller than the mod) you still get a valid result for the difference, no matter whether you take the mod (or overflow) or not.

Of course you shouldn't rely on that because it is still UB per the C++ specification, but still.

No. Of points such that x = y between coordinates (a,b) and (c,d) are max(0,min(c,d) — max(a,b) + 1). Just make sure to handle duplicates coordinates properly.

q1: YES

There exist a seq such that any gap will be at most 2 element, say a[7], a[5], a[3], a[1], a[2], a[4], a[6], call it (*).

The largest difference in (*) is a[2] - a[1] or a[n] - a[n - 1] or a[i] - a[i - 2]. For the first two its clear that any sequence must be a difference larger of equal of that. For the last cases, if we don't want a[i] - a[i - 2] to appear, then we should insert something between them. Note it is a circle so we need consider transverse in clockwise and anticlockwise. Say if we insert a[i - 1] in one direction, then we must have a[j < i - 2] and a[k > i] meet somewhere in another direction. The difference a[j < i - 2] and a[k > i] is larger in that the largest difference in (*).So we cannot construct any better solution and (*) will be optimal.

e.g. a[] = {1, 2, 3, 4, 100, 101, 102} we can write in 102, 100, 3, 1, 2, 4, 101. The largest difference is (100, 3). If we put 4 between them we get 102, 100, 4, 3, 1, 2, 101. Note the gap in another direction is bad and the largest difference is 101 - 2 = 99 > 100 - 3

A funny solution: Binary search for the answer and use the Hungarian algorithm to check.

Probably cause there is no test like

150000 
2 1
3 4
4 1
5 6
5 1
...

Which should result in TLE. Though you can easily make this solution O(nlogn) by merging smaller vector to larger instead of second one to first one

no cuz D is very standard.

And there is a lot of problems similar to F

D can be easily solved using DSU and Topology sorting.

I think the difficulty of problem D is around D div 2 of usual Div-2 contests with 5 problems.

It's O(n*α(n)),btw I am the same solution

Actually union find set with only path compression has the conplexity O(nlogn).

D can be solved using DSU and Topology sorting.

Firstly, if a(i, j) = '=' then join i and j + n to the same set. Thus, there can be at most n + m sets. Let's create a directed graph with n + m vertices, each vertex represents a set. Now if a(i, j) = '<' then connect an edge from head of set i to head of set j, a(i, j) = '>' otherwise. If we can't toposort this graph (i.e, this graph has cycles), then the answer is No. Also if two element i and j in the same set but a(i, j) != '=' then the answer is also No. Otherwise you can toposort the graph and find the answer easily.

Also logN in overall complexity could be avoided by making a graph EQ with only '=' edges and finding CC's there instead of DSU.

You should merge to the cell with higher size.

Also, vector::clear() doesn't free memory, if you want to to that, use

vector<int> vec = {1,2,3};
vector<int>().swap(vec); //free memory from vec

Congratulations！

By your check function, you decides that, sorting the array then destributing the elements with the way you mentioned, is the optimal way to reach the minimum discomfort value. So, firstly, you don't need to binary-search for the answer (mid value doesn't have effects on the work of the check function).

The proof of the greedy method of the check function can be found in the editorial (or above in comments)