「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[1,m]k \in [1, m] bk=max(ai,k,aj,k)b_k = \max(a_{i, k}, a_{j, k}) .

Your goal is to choose 𝑖𝑖 and 𝑗𝑗 so that the value of minmink=1mbk\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 1198D」 Rectangle Painting 1

There is a square grid of size n×nn \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)\max(h, w) to color a rectangle of size h×wh \times w. You are to make all cells white for minimum total cost.

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

「CodeForces 1215F」 Radio Stations

In addition to complaints about lighting, a lot of complaints about insufficient radio signal covering has been received by Bertown city hall recently. 𝑛 complaints were sent to the mayor, all of which are suspiciosly similar to each other: in the 𝑖-th complaint, one of the radio fans has mentioned that the signals of two radio stations 𝑥𝑖 and 𝑦𝑖 are not covering some parts of the city, and demanded that the signal of at least one of these stations can be received in the whole city.

「CodeForces 1277F」Beautiful Rectangle

You are given 𝑛 integers. You need to choose a subset and put the chosen numbers in a beautiful rectangle (rectangular matrix). Each chosen number should occupy one of its rectangle cells, each cell must be filled with exactly one chosen number. Some of the 𝑛 numbers may not be chosen.