At a recent social gathering, \(N\) people sit around a circular table, where \(N\) is even. The seats are numbered clockwise from \(1\) to \(N\). Each person is wearing a hat with a number on it. Specifically, the person at seat \(i\) is wearing a hat with the number \(H_i\) on it.
Each person looks at the person who is directly across (diametrically opposite) them in the circle.
Determine the number of people who see someone with a hat with the same number as their own.
The first line of input will consist of one even positive integer \(N\), representing the number of people at the social gathering.
The next \(N\) lines each contain a single non-negative integer \(H_i\), representing the hat number of person \(i\).
The following table shows how the available \(15\) marks are distributed:
| Marks | Description | Bounds on \(N\) | Bounds on \(H_i\) |
|---|---|---|---|
| \(2\) | Very small number of people; only two hat numbers | \(N \le 4\) | \(H_i \leq 1\) |
| \(1\) | Only one hat number | \(N \le 100\) | \(H_i = 1\) |
| \(2\) | People in even numbered seats have hat number 1; people in odd numbered seats have hat number 0 | \(N \le 100\) | \(H_i \leq 1\) |
| \(5\) | Medium number of people | \(N \le 2\,000\) | \(H_i \leq 4\,000\) |
| \(5\) | Large number of people and hat numbers | \(N \le 1\,000\,000\) | \(H_i \le 2\,000\,000\) |
Output a single integer representing the number of people who see their hat number on the person directly across from them.
4
0
1
0
1 4
The four seats around the table are shown below. Hat numbers are shown inside each seat and seat numbers are shown beside each seat.
Notice that every person sees their hat number. The people in seats \(1\) and \(3\) both see hat number \(0\), and the people in seats \(2\) and \(4\) both see hat number \(1\).
4
1
0
0
1 0
The four seats around the table are shown below. Hat numbers are shown inside each seat and seat numbers are shown beside each seat.
Notice that no person sees their hat number. The people in seats \(1\) and \(4\) both see hat number \(0\), and the people in seats \(2\) and \(3\) both see hat number \(1\).
In a string containing only lowercase letters of the alphabet ("a" through "z"), we say a letter is heavy if it appears more than once in the string, and light otherwise.
We will be given a number of strings. For each string, we would like to determine whether the letters of the string alternate between light and heavy.
The first line of input will consist of two positive integers \(T\) and \(N\), representing the number of strings and the length of each string.
The next \(T\) lines each contain a sequence of \(N\) lowercase letters of the alphabet.
The following table shows how the available \(15\) marks are distributed:
| Marks | Bounds on \(T\) | Bounds on \(N\) | Other Restrictions |
|---|---|---|---|
| \(5\) | \(2 \le T \le 4\) | \(2 \le N \le 4\) | Only the letters "a" and "b" will be used |
| \(5\) | \(2 \le T \le 10\) | \(2 \le N \le 30\) | None |
| \(2\) | \(2 \le T \le 100\) | \(2 \le N \le 100\) | Only the letter "a" will be heavy; all other letters are light |
| \(3\) | \(2 \le T \le 10\ 000\) | \(2 \le N \le 100~~\) | None |
Output \(T\) lines, where each line
will be either T or F. If the \(i\)-th input string does alternate between
light and heavy letters, the \(i\)-th
line of output should be T; and otherwise, the \(i\)-th line of output should be
F.
3 4
abcb
bcbb
babc T
F
T The first string is composed of a light letter, then a heavy letter, then a light letter, and then a heavy letter.
The second string ends in two consecutive heavy letters.
The third string is composed of a heavy letter, then a light letter, then a heavy letter, and then a light letter.
2 3
abc
bcb F
T The first string is composed of all light letters.
The second string is composed of a heavy letter, then a light letter, and then a heavy letter.
Swipe is a new mobile game that has recently exploded in popularity. In each level of Swipe, you are given \(2\) rows of integers that can be represented as arrays \(A\) and \(B\) of size \(N\). The objective of Swipe is to beat each level by turning array \(A\) into array \(B\).
There are two swipe operations you can perform on array \(A\).
Swipe right: Select the subarray \([\ell,r]\) and set \(A_i = A_\ell\) for all \(\ell \le i \le r\).
Swipe left: Select the subarray \([\ell,r]\) and set \(A_i = A_r\) for all \(\ell \le i \le r\).
For example, starting with array \(A = [0,1,2,3,4,5]\), if we swipe right on \([2,4]\), we would obtain the array \([0,1,2,2,2,5]\). If instead, we started with the same array \(A\), and swiped left on \([3,5]\), we would obtain the array \([0,1,2,5,5,5]\). Note that these arrays are \(0\)-indexed.
Unfortunately, the game is bugged and contains levels that are impossible to beat. Determine if it is possible to transform array \(A\) into array \(B\). If it is possible, determine a sequence of swipe operations that transforms array \(A\) into array \(B\).
The first line of input will consist of one positive integer \(N\), representing the length of each of the two arrays of integers.
The second line of input contains \(N\) space separated integers contained in array \(A\).
The third line of input contains \(N\) space separated integers contained in array \(B\).
The following table shows how the available \(15\) marks are distributed:
| Marks | Bounds on \(N\) | Bounds on \(A_i\) and \(B_i\) |
|---|---|---|
| \(2\) | \(N=2\) | \(1 \le A_i,B_i \leq 3\) |
| \(4\) | \(1 \le N \le 8\) | \(1 \le A_i,B_i \leq 8\) |
| \(4\) | \(1 \le N \le 500\) | \(1 \le A_i,B_i \leq 3000\) |
| \(5\) | \(1 \le N \le 300\,000\) | \(1 \le A_i,B_i \leq 300\,000\) |
Note that for a subtask worth \(M\) marks, you will receive \(\left\lfloor \frac{M}{2} \right\rfloor\) marks for a solution that only correctly outputs the first line of output.
The first line of output will contain YES if there is a
sequence of swipes that can transform array \(A\) into array \(B\); otherwise, the first line of output
will contain NO.
If the first line of output is YES, the next line
contains a non-negative integer \(K\)
(\(K \leq N\)), indicating the number
of swipes.
Each of the next \(K\) lines contain
three space-separated values: \(D_j\),
\(\ell_j\), and \(r_j\). The value \(D_j\) will be either R or
L, indicating that the \(j\)th swipe is either a right or left
swipe, respectively. The values \(\ell_j\) and \(r_j\) indicate the left-end and right-end
of the swipe where \(0 \le \ell_j \le r_j <
N\).
3
3 1 2
3 1 1YES
1
R 1 24
1 2 4 3
1 4 2 3 NO
4
2 1 4 3
2 1 4 3 YES
0Alanna, the mayor of Kitchener, has successfully improved the city’s road plan. However, a travelling salesperson from the city of RedBlue complained that the roads are not colourful enough. Alanna’s second job is to paint some of the roads.
Kitchener’s road plan can be represented as a collection of \(N\) intersections with \(M\) roads, where the \(i\)-th road connects intersections \(u_i\) and \(v_i\). All roads are initially grey. Alanna would like to paint some of the roads in red or blue such that the following condition is satisfied:
Whenever there is a grey road that connects \(u_i\) and \(v_i\), there is also a path of roads from \(u_i\) to \(v_i\) such that the roads on the path alternate between red and blue, without any of the roads on this path being grey.
To lower the city’s annual spending, Alanna would like to minimize the number of painted roads. Can you help Alanna design a plan that meets all the requirements?
The first line contains two integers \(N\) and \(M\) \((1 \le N,M \le 2 \cdot 10^5)\).
The \(i\)-th of the next \(M\) lines contains two integers \(u_i\) and \(v_i\), meaning that there exists a road from intersection \(u_i\) to intersection \(v_i\) \((1 \le u_i,v_i \le N, u_i \ne v_i)\).
There is at most one road between any unordered pair of intersections.
The following table shows how the available 15 marks are distributed:
| Marks | Additional Constraints |
|---|---|
| \(2\) | There is a road connecting intersection \(i\) with intersection \(i+1\) for all \(1 \le i < N\) (and possibly other roads). |
| \(3\) | We can reach any intersection from any other intersection, and \(N=M\). |
| \(3\) | No road belongs to two or more simple cycles (see Definition below). |
| \(7\) | None |
Definition: if we denote a road between intersections \(u\) and \(v\) as \(u \leftrightarrow v\), then a simple cycle is a sequence \(w_1 \leftrightarrow w_2\leftrightarrow \ldots \leftrightarrow w_k \leftrightarrow w_1\) where \(k \geq 3\) and all \(w_i\) are distinct.
Output a string of \(M\) characters,
representing the paint plan. The \(i\)-th character should be R
if the \(i\)-th road is to be painted
red, B if \(i\)-th road is
to be painted blue, or G (for "grey") if the \(i\)-th road is to be left unpainted.
Remember that you must minimize the number of painted roads while satisfying the condition. If there are multiple possible such plans, output any of them.
5 7
1 2
2 4
5 2
4 5
4 3
1 3
1 4RGGRGRB
A diagram of the intersections along with a valid paint plan that minimizes the number of painted roads is shown below. Note that the colours are shown on each road as R (red), B (blue), or G (grey).
All the unpainted roads satisfy the condition:
The \(2\)nd road, labelled G2, connects intersection \(2\) with intersection \(4\). The path through intersections \(2,1,4\) alternates red, blue.
The \(3\)rd road, labelled G3, connects intersection \(5\) with intersection \(2\). The path through intersections \(5,4,1,2\) alternates red, blue, red.
The \(5\)th road, labelled G5, connects intersection \(4\) with intersection \(3\). The path through intersections \(4,1,3\) alternates blue, red.
4 2
1 2
3 4BB
Note that it is possible for Kitchener to be disconnected.
Maxwell has a chocolate bar that he wants to share with his friends. The chocolate bar can be represented as a \(2\) by \(N\) array of integers \(T_{i,j}\), the tastiness of each square. Maxwell would like to split the entire chocolate bar into connected parts such that the average (mean) tastiness of the chocolate bar is the same for each part. Maxwell would like to know what is the maximum number of connected parts he can split his chocolate bar into as described above.
A part is considered connected if you can visit every cell by moving up, down, left or right.
The first line of input will consist of one positive integer \(N\), representing the length of the chocolate bar.
The second line of input contains \(N\) spaced integers representing the top row of the chocolate bar where the \(j\)-th integer from the left represents \(T_{1,j}\).
Similarly, the third line of input contains \(N\) spaced integers representing the bottom row of the chocolate bar where the \(j\)-th integer from the left represents \(T_{2,j}\).
The following table shows how the available \(15\) marks are distributed:
| Marks | Bounds on \(N\) | Bounds on \(T_{i,j}\) |
|---|---|---|
| \(2\) | \(N=2\) | \(0 \le T_{i,j} \leq 5\) |
| \(2\) | \(1 \le N \le 8\) | \(0 \le T_{i,j} \leq 20\) |
| \(1\) | \(1 \le N \le 20\) | \(0 \le T_{i,j} \leq 20\) |
| \(2\) | \(1 \le N \le 100\) | \(0 \le T_{i,j} \leq 20\) |
| \(2\) | \(1 \le N \le 1\ 000\) | \(0 \le T_{i,j} \leq 100\) |
| \(3\) | \(1 \le N \le 2\ 000\) | \(0 \le T_{i,j} \leq 100\ 000\) |
| \(3\) | \(1 \le N \le 200\ 000\) | \(0 \le T_{i,j} \leq 100\ 000\ 000\) |
Output a single integer, representing the maximum number of connected parts Maxwell can split his chocolate bar into.
2
5 4
6 52
An example of how to split this chocolate bar optimally into \(2\) parts is to have the bottom right corner as its own part and the rest of the chocolate as the second part, as shown below.
Each piece will have an average tastiness of \(5\).
5
1 0 1 2 0
0 2 0 3 1 5
One way to get the optimal split is shown in the following picture:
Note that each piece has an average tastiness of \(1\).