Hello, welcome to the OIE!
The first problem we present is: given a word $$$s$$$, determine if $$$s$$$ is a permutation of the word hola.
We say that a word is a permutation (or an anagram) of another if it has the same letters regardless of the order. For example, loha, ohal, and hola are three permutations of hola, but ola, holaa, and holi are not.
The first line of the input contains an integer $$$T$$$, the number of cases.
Following this, there are $$$T$$$ words formed by lowercase letters of the English alphabet, each on a new line.
For each case, write a line with "SI" or "NO" (without quotes).
$$$1 \leq T \leq 50$$$.
$$$1 \leq |s| \leq 5$$$ (the words are at most 5 letters long).
100 points: No additional restrictions.
6 hola ola ohal loha holaa holi
SI NO SI SI NO NO
We say that a set of integers is closed by subtraction if, for every pair of distinct numbers in the set $$$a, b$$$, at least one of the two values $$$(a-b)$$$, $$$(b-a)$$$ also belongs to the set.
Given a set of integers, determine if it is closed by subtraction.
The first line contains an integer $$$T$$$, the number of test cases.
For each case, there is a line with an integer $$$n$$$, the number of elements in the set, followed by another line with $$$n$$$ integers $$$a_1, \ldots, a_n$$$, the numbers in the set. The $$$a_i$$$ are all distinct.
For each case, write a line with "SI" if the set is closed by subtraction and "NO" otherwise.
$$$1 \leq T \leq 100$$$.
$$$2 \leq n \leq 5 \cdot 10^5$$$, the sum of $$$n$$$ for all cases is less than $$$2 \cdot 10^6$$$.
$$$-10^9 \leq a_i \leq 10^9$$$ for $$$1 \leq i \leq n$$$.
40 points: $$$n \leq 100$$$, the sum of $$$n$$$ for all cases is less than $$$2000$$$.
25 points: $$$n \leq 2000$$$, the sum of $$$n$$$ for all cases is less than $$$2 \cdot 10^4$$$.
35 points: No additional restrictions.
5 3 1 2 3 4 5 4 0 2 3 -1 0 1 5 -4 -2 -6 -10 -8 2 1000000000 0
SI NO NO SI SI
Juan's notebook has horizontal lines. On a page, it has $$$m$$$ horizontal lines, each separated by one centimeter from the previous one. However, Juan prefers notebooks with a grid pattern. Therefore, he has drawn $$$n$$$ vertical lines on a page of his notebook at the horizontal coordinates $$$a_1, a_2, \ldots, a_n$$$, meaning that the distance from the $$$i$$$-th line to the left edge of the page is $$$a_i$$$ centimeters. Both the horizontal lines and the lines drawn by Juan extend across the entire page.
Now Juan wonders how many squares can be formed with vertices at the intersections of the lines in the notebook. Help Juan count the number of squares.
The first line of the input contains an integer $$$T$$$, the number of cases.
The first line of each case contains two integers $$$m$$$ and $$$n$$$. The second line contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$.
For each case, print a line with the number of squares.
$$$1 \leq T \leq 30$$$.
$$$2 \leq m \leq 10^6$$$.
$$$2 \leq n \leq 10^6$$$, the sum of $$$n$$$ for all cases is less than $$$2 \cdot 10^6$$$.
$$$1 \leq a_1 \lt a_2 \lt \ldots \lt a_n \leq 10^9$$$.
26 points: $$$n, m, a_n \leq 100$$$. The sum of $$$n$$$ for all cases is less than $$$500$$$.
16 points: $$$n \leq 2000$$$. The sum of $$$n$$$ for all cases is less than $$$7000$$$.
11 points: $$$m = 2$$$, the sum of $$$n$$$ for all cases is less than $$$2 \cdot 10^5$$$.
18 points: $$$a_i = i$$$ for $$$1 \leq i \leq n$$$, the sum of $$$n$$$ for all cases is less than $$$2 \cdot 10^5$$$.
29 points: No additional restrictions.
3 4 3 1 3 4 3 2 1 5 2 2 1 2
6 0 1
In a region with $$$n$$$ villages, after a heavy snowfall, all $$$m$$$ roads have been blocked. Each of these roads connects two villages, and it will take $$$h_i$$$ hours to reopen the $$$i$$$-th road. These times are independent of each other; work is done on all roads simultaneously.
What is the minimum number of hours that must pass for the villages to be connected? That is, for any pair of villages, there exists a route between the two villages that passes through one or more roads that have already been opened.
It is guaranteed that, after enough hours for all roads to be usable, there is a route between every pair of villages.
The first line of the input contains an integer $$$T$$$, the number of test cases.
For each case, there is a line with two integers $$$n$$$ and $$$m$$$, the number of villages and the number of roads. This is followed by $$$m$$$ lines, each with three integers $$$u, v, h_i$$$, representing that there is a road between the $$$u$$$-th village and the $$$v$$$-th village that will take $$$h_i$$$ hours to open. The roads are bidirectional.
For each case, print on a line the number of hours that must pass for the villages to be connected.
$$$1 \leq T \leq 100$$$
$$$2 \leq n \leq 10^5$$$
$$$1 \leq m \leq 5 \cdot 10^5$$$
$$$1 \leq h_i \leq 10^6$$$
$$$0 \leq u, v \leq n-1$$$
The sum of $$$n+m$$$ for all cases is at most $$$10^6$$$.
It is guaranteed that if all roads can be used, there is a route between every pair of villages.
52 points: $$$n, m, h_i \leq 1000$$$, the sum of $$$n+m$$$ for all cases is at most $$$10^4$$$.
17 points: $$$m = n-1$$$.
31 points: No additional constraints.
2 3 3 0 1 10 0 2 20 1 2 30 4 3 0 1 10 0 2 20 0 3 30
20 30
María has a board with $$$n \times m$$$ square cells distributed in $$$n$$$ rows and $$$m$$$ columns.
María wants to paint the cells in black and white such that the following two properties are satisfied:
- The number of white cells must be equal to the number of black cells.
- The number of pairs of adjacent cells of the same color must be equal to the number of pairs of adjacent cells of different colors. (Two cells are considered adjacent if they share a side).
Can you help María paint her board?
The first line contains an integer $$$T$$$, the number of test cases.
Each case consists of a line with two integers $$$n$$$ and $$$m$$$.
For each test case, the output should contain a first line with the word "SI" if it is possible to paint the board in a way that satisfies the conditions, and with the word "NO" if it is not possible. If the answer is "SI", the output should include $$$n$$$ more lines with $$$m$$$ characters each describing a possible way to paint the board that satisfies the properties, indicating with "." the cells painted white and with "#" the cells painted black. If there are multiple possible solutions, any of them can be provided.
$$$1 \leq T \leq 50$$$.
$$$1 \leq n, m \leq 1000$$$, the sum of $$$n \cdot m$$$ for all cases is less than $$$2 \cdot 10^6$$$.
20 points: $$$n, m \leq 6$$$, $$$T \leq 20$$$.
20 points: $$$n, m \leq 20$$$, the sum of $$$n \cdot m$$$ for all cases is less than $$$2000$$$.
15 points: $$$n = 2$$$, the sum of $$$n \cdot m$$$ for all cases is less than $$$2 \cdot 10^4$$$.
15 points: $$$n = m$$$.
30 points: No additional restrictions.
3 2 4 3 3 4 6
SI ##.. .##. NO SI ###..# #..#.# ..#... ####..
Pablo has a grid formed by $$$n$$$ horizontal segments and $$$m$$$ vertical segments. Viewed in Cartesian coordinates, the $$$i$$$-th horizontal segment has one endpoint at the point $$$(0, i)$$$ and the other at the point $$$(a_i, i)$$$, while the $$$j$$$-th vertical segment has one endpoint at the point $$$(j, 0)$$$ and the other at the point $$$(j, b_j)$$$.
Pablo wants to paint each segment of his grid in a color such that if two segments intersect, they must be painted the same color. What is the maximum number of distinct colors that the segments of the grid can have?
The first line of the input contains an integer $$$T$$$, the number of test cases.
For each case, there is a line with two integers $$$n$$$ and $$$m$$$. This is followed by a line with $$$n$$$ integers $$$a_1, \ldots, a_n$$$ and then another line with $$$m$$$ integers $$$b_1, \ldots, b_m$$$.
For each case, print on a line the maximum number of distinct colors.
$$$1 \leq T \leq 100$$$.
$$$1 \leq n \leq 5 \cdot 10^5$$$.
$$$1 \leq m \leq 5 \cdot 10^5$$$.
$$$1 \leq a_i, b_j \leq 5 \cdot 10^5$$$ for $$$1 \leq i \leq n$$$, $$$1 \leq j \leq m$$$.
The sum of $$$n+m$$$ for all cases is less than $$$2 \cdot 10^6$$$.
27 points: $$$n, m \leq 100$$$, the sum of $$$n+m$$$ for all cases is less than $$$1000$$$.
19 points: $$$n, m \leq 2000$$$, the sum of $$$n+m$$$ for all cases is less than $$$2 \cdot 10^4$$$.
21 points: $$$b_j = j$$$ for $$$1 \leq j \leq m$$$, the sum of $$$n+m$$$ for all cases is less than $$$3 \cdot 10^5$$$.
33 points: No additional restrictions.
4 4 6 2 1 3 5 1 2 4 3 4 4 1 1 1 1 5 5 1 1 1 1 1 1 1 1 1 1 5 5 1 2 3 4 5 1 2 3 4 5
5 1 9 5