## 「CodeForces 1288E」 Messenger Simulator

Polycarp is a frequent user of the very popular messenger. He's chatting with his friends all the time. He has 𝑛 friends, numbered from 1 to 𝑛.

Recall that a permutation of size 𝑛 is an array of size 𝑛 such that each integer from 1 to 𝑛 occurs exactly once in this array.

## 「CodeForces 1288D」 Minimax Problem

You are given 𝑛 arrays 𝑎1, 𝑎2, ..., 𝑎𝑛; each array consists of exactly 𝑚 integers. We denote the 𝑦-th element of the 𝑥-th array as 𝑎𝑥,𝑦.

You have to choose two arrays 𝑎𝑖 and 𝑎𝑗 (1≤𝑖,𝑗≤𝑛, it is possible that 𝑖=𝑗). After that, you will obtain a new array 𝑏 consisting of 𝑚 integers, such that for every $k \in [1, m]$ $b_k = \max(a_{i, k}, a_{j, k})$ .

Your goal is to choose $𝑖$ and $𝑗$ so that the value of min$\min \limits_{k = 1}^{m} b_k$ is maximum possible.

## 「CodeForces 1198E」 Rectangle Painting 2

There is a square grid of size 𝑛×𝑛. Some cells are colored in black, all others are colored in white. In one operation you can select some rectangle and color all its cells in white. It costs min(ℎ,𝑤) to color a rectangle of size ℎ×𝑤. You are to make all cells white for minimum total cost.

The square is large, so we give it to you in a compressed way. The set of black cells is the union of 𝑚 rectangles.

## 「CodeForces 1198F」GCD Groups 2

You are given an array of 𝑛 integers. You need to split all integers into two groups so that the GCD of all integers in the first group is equal to one and the GCD of all integers in the second group is equal to one.

## 「CodeForces 1198D」 Rectangle Painting 1

There is a square grid of size $n \times n$. Some cells are colored in black, all others are colored in white. In one operation you can select some rectangle and color all its cells in white. It costs $\max(h, w)$ to color a rectangle of size $h \times w$. You are to make all cells white for minimum total cost.

## 「CodeForces 1198C」 Matching vs Independent Set

You are given a graph with 3⋅𝑛 vertices and 𝑚 edges. You are to find a matching of 𝑛 edges, or an independent set of 𝑛 vertices.

A set of edges is called a matching if no two edges share an endpoint.

A set of vertices is called an independent set if no two vertices are connected with an edge.

## 「CodeForces 1284D」New Year and Conference

Filled with optimism, Hyunuk will host a conference about how great this new year will be!

The conference will have 𝑛 lectures. Hyunuk has two candidate venues 𝑎 and 𝑏. For each of the 𝑛 lectures, the speaker specified two time intervals [𝑠𝑎𝑖,𝑒𝑎𝑖] (𝑠𝑎𝑖≤𝑒𝑎𝑖) and [𝑠𝑏𝑖,𝑒𝑏𝑖] (𝑠𝑏𝑖≤𝑒𝑏𝑖). If the conference is situated in venue 𝑎, the lecture will be held from 𝑠𝑎𝑖 to 𝑒𝑎𝑖, and if the conference is situated in venue 𝑏, the lecture will be held from 𝑠𝑏𝑖 to 𝑒𝑏𝑖. Hyunuk will choose one of these venues and all lectures will be held at that venue.

Two lectures are said to overlap if they share any point in time in common. Formally, a lecture held in interval [𝑥,𝑦] overlaps with a lecture held in interval [𝑢,𝑣] if and only if max(𝑥,𝑢)≤min(𝑦,𝑣).

## 「CodeForces 1270G」Subset with Zero Sum

You are given 𝑛 integers 𝑎1,𝑎2,…,𝑎𝑛, such that for each 1≤𝑖≤𝑛 holds 𝑖−𝑛≤𝑎𝑖≤𝑖−1.

Find some nonempty subset of these integers, whose sum is equal to 0. It can be shown that such a subset exists under given constraints. If there are several possible subsets with zero-sum, you can find any of them.