MITIT 2024 Combined Round
A. Monotonically Increasing Tardiness Informatics Tournament
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Check out Python input/output or C++ input/output or Java input/output for reading in the input numbers.

The organizing beavers of the Monotonically Increasing Tardiness Informatics Tournament (MITIT) need to meet regularly to ensure that the contest runs smoothly, but they sometimes lose motivation.

There are $$$N$$$ organizing beavers who regularly have meetings that last exactly $$$M$$$ minutes. The $$$i^{\text{th}}$$$ beaver shows up $$$t_i$$$ minutes late on the first meeting. On each successive meeting, beaver $$$i$$$ comes $$$a_i$$$ minutes later than they did to the previous meeting. Output the first meeting where everyone is so late that they all miss the entire meeting.

A beaver is said to have missed the entire meeting if they arrive at least $$$M$$$ minutes late.

Input

The first line contains two space-separated integers $$$N$$$ ($$$ 1 \le N \le 2\cdot 10^5$$$) and $$$M$$$ ($$$ 1 \le M \le 10^9$$$).

The $$$i^{\text{th}}$$$ of the next $$$N$$$ lines contains two integers $$$t_i$$$ ($$$0 \le t_i \lt M$$$) and $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$).

Output

Output one line with the answer.

Example
Input
4 60
0 9
30 4
10 12
14 9
Output
9
Note

For the first meeting, Beaver $$$1$$$ arrives on time, Beaver $$$2$$$ arrives $$$30$$$ minutes late, Beaver $$$3$$$ arrives $$$10$$$ minutes late, and Beaver $$$4$$$ arrives $$$14$$$ minutes late. For meeting $$$9$$$, Beaver $$$1$$$ arrives $$$72$$$ minutes late, Beaver $$$2$$$ arrives $$$62$$$ minutes late, Beaver $$$3$$$ arrives $$$106$$$ minutes late, and Beaver $$$4$$$ arrives $$$86$$$ minutes late. This is the first meeting for which everyone arrives at least $$$60$$$ minutes late; for meeting $$$8$$$, Beaver $$$2$$$ arrives $$$58$$$ minutes late.

B. Min-Max Game
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The century-long rivalry between Busy Beaver and Busy Revaeb rages on to this very day. This time, they decide to challenge each other in a two-player game.

There is a sequence of $$$N$$$ positive integers $$$a_1, \dots, a_N$$$. Busy Beaver and Busy Revaeb play a turn-based game as follows:

  • Busy Beaver chooses two adjacent numbers in the sequence, erases them, and writes down the larger of the two erased numbers there.
  • Busy Revaeb does the same, but writes down the smaller of the two erased numbers.
Busy Beaver goes first. The game ends when there is only one number $$$X$$$ remaining in the sequence. Busy Beaver wants to maximize $$$X$$$; Busy Revaeb wants to minimize it. Find the value of $$$X$$$ if both players play optimally.
Input

The first line contains $$$N$$$ ($$$1 \leq N \leq 2 \cdot 10^5$$$), the number of elements in the array.

The second line contains $$$N$$$ space-separated integers $$$a_1, \dots, a_N$$$ ($$$1 \le a_i \le 10^9$$$).

Output

Output a single integer – the value of the only element left in the array if both players play optimally.

Scoring
  • ($$$15$$$ points) $$$N \leq 3$$$.
  • ($$$25$$$ points) $$$1 \leq a_i \leq 2$$$.
  • ($$$60$$$ points) No additional constraints.
Examples
Input
3
2 1 4
Output
2
Input
4
1 1 1 2
Output
1
Note

Sample Explanation 1

The last value cannot be $$$4$$$, because if Busy Beaver tries to keep $$$4$$$ by not choosing it on the first round, Busy Revaeb can take the $$$4$$$ the next round, leaving the last value $$$1$$$ or $$$2$$$. The last value also cannot be $$$1$$$ because Busy Revaeb could have taken the $$$1$$$ in round $$$1$$$, ensuring the last value is greater than $$$1$$$.

Busy Beaver can ensure the last value is at least $$$2$$$, and Busy Revaeb can ensure the last value is at most $$$2$$$. Thus, the last value will be $$$2$$$ under optimal play.

Sample Explanation 2

The last value is either $$$1$$$ or $$$2$$$. If Busy Revaeb's strategy consists of taking $$$2$$$ as soon as possible, then he can guarantee that after his turn (turn $$$2$$$), the sequence contains only $$$1$$$s $$$-$$$ regardless of how Busy Beaver moves in turn $$$1$$$. Therefore, when both play optimally, the last value will be $$$1$$$.

C. Tromino Packing
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Busy Beaver found a strange puzzle. The puzzle consists of a box divided into an $$$N \times M$$$ grid of squares. Each cell of the grid is either occupied (denoted by a '#'), empty (denoted by a '.'), or empty but marked with a 'o'.

The puzzle comes with a bunch of L-tromino pieces, one for each 'o' cell of the grid. An L-tromino is composed of three square blocks in the shape of an L as shown. The center of the L-tromino is the square that is adjacent to both of the other two squares (marked with an o in the picture).

Busy Beaver realizes that to solve the puzzle, he needs to pack all the L-trominos into the box such that the L-trominos are aligned to the grid, each L-tromino center is at an empty cell marked with a 'o' and no two L-trominos overlap each other or an occupied cell. All L-trominos can be rotated freely.

Can you help Busy Beaver count the number of ways to solve the puzzle? As the answer may be large, output it modulo $$$10^9+7$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \le T \le 500$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$N$$$ and $$$M$$$ ($$$2 \le N,M \le 1000$$$), the dimensions of the grid.

The next $$$N$$$ lines each contain $$$M$$$ characters, describing a row of the grid. Each character is either '#', '.', or 'o'.

It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$1000$$$.

It is guaranteed that the sum of $$$M$$$ over all test cases does not exceed $$$1000$$$.

Output

For each test case, output a single integer: the number of ways to solve the puzzle modulo $$$10^9+7$$$.

Scoring

Let $$$(r,c)$$$ denote the cell at row $$$r$$$ and column $$$c$$$ ($$$1 \le r \le N, 1 \le c \le M$$$).

  • ($$$10$$$ points) Each 'o' cell is Manhattan distance at least $$$3$$$ away from each other 'o' cell. That is, if $$$(r_1,c_1)$$$ and $$$(r_2,c_2)$$$ are two different 'o' cells, then $$$|r_1-r_2|+|c_1-c_2| \ge 3$$$.
  • ($$$30$$$ points) Each 'o' cell is vertically adjacent to at least one other 'o' or '#' cell. That is, for any 'o' cell at $$$(r,c)$$$, either $$$(r-1,c)$$$ or $$$(r+1,c)$$$ is an '#' cell or another 'o' cell.
  • ($$$60$$$ points) No additional constraints.
Example
Input
5
4 5
###.o
.o...
#..o.
#..##
5 5
..###
.o..#
.o.o.
..#o.
###..
8 31
.########.#..oo..o..o#o..o....o
o.######.o#o...o..o..#..o..oo..
o..####.o.#####..########o..###
..o.o..o..#####.o########..o###
.o##..##.o#####o.########..o###
o.##.o##.o#####..########o..###
..######..#..o..o.o..####..o###
.o######o.#o..o..o..o####o..###
2 3
#.o
.o.
2 2
..
..
Output
4
6
1
0
1
Note

Note that the first test case satisfies the constraints for the first subtask and the second test case satisfies the constraints for the second subtask.

In the first test case, the $$$4$$$ ways to solve the puzzle are as shown:

In the second test case, the $$$6$$$ ways to solve the puzzle are as shown:

In the third test case, the only way to solve the puzzle is as shown:

In the fourth test case, there are no ways to solve the puzzle.

In the fifth test case, there are no 'o' cells, so the unique way to solve the puzzle is to not place any L-trominos.

D. Tree 2-Coloring
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Busy Beaver is decorating a Christmas tree, but he has some strange preferences for what colors to use.

Consider a coloring of the vertices of a tree, using two colors: red and green.

In a coloring, call a connected component of green vertices cool if at most two red vertices are adjacent to that component. For a tree $$$t$$$, let $$$f(t)$$$ be the maximum number of cool components in any coloring of $$$t$$$.

There is a tree $$$t$$$, initially only containing a single vertex, denoted vertex $$$1$$$. Perform $$$N$$$ queries; in the $$$i^{\text{th}}$$$ query, add a leaf vertex by attaching it to vertex $$$a_i$$$. There are two types of test cases, depending on a variable $$$X \in \{0, 1\}$$$:

  • If $$$X = 0$$$, output $$$f(t)$$$ after all queries are completed.
  • If $$$X = 1$$$, output $$$f(t)$$$ after each query.
Input

There are multiple test cases. The input file begins with $$$T$$$ and $$$X$$$ ($$$1 \le T \le 4\cdot 10^4$$$, $$$X \in \{0, 1\}$$$), the number of test cases and the test type respectively.

The first line of each test case contains an integer $$$N$$$ ($$$1 \le N \le 2 \cdot 10^5$$$).

The second line contains $$$N$$$ integers $$$a_1, \dots, a_N$$$ ($$$1 \le a_i \le i$$$).

It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$4 \cdot 10^5$$$.

Output

If $$$X = 0$$$, then for each test case, output $$$f(t)$$$ for the final tree on a single line.

If $$$X = 1$$$, then for each test case, output $$$N$$$ lines, the $$$i^{\text{th}}$$$ line being the value of $$$f(t)$$$ after the $$$i^{\text{th}}$$$ query.

Scoring
  • ($$$25$$$ points) $$$X = 0$$$.
  • ($$$30$$$ points) Each $$$a_i$$$ is chosen uniformly at random from $$$[1, i]$$$.
  • ($$$45$$$ points) No additional constraints.
Examples
Input
2 0
4
1 2 3 3
8
1 2 3 2 3 6 5 7
Output
3
5
Input
2 1
4
1 2 3 3
8
1 2 3 2 3 6 5 7
Output
1
2
2
3
1
2
2
3
4
4
4
5
Note

Sample Explanation 1

For the first test case, we can color vertices $$$1$$$, $$$2$$$, $$$4$$$, and $$$5$$$ green (note that there are $$$N + 1 = 5$$$ vertices since there is already a vertex in the beginning). Then $$$\{1, 2\}$$$, $$$\{4\}$$$, and $$$\{5\}$$$ are cool components.

For the second test case, we can color vertices $$$1$$$, $$$4$$$, $$$5$$$, $$$6$$$, $$$8$$$, and $$$9$$$ green. Then $$$\{1\}$$$, $$$\{4\}$$$, $$$\{5, 8\}$$$, $$$\{6\}$$$, and $$$\{9\}$$$ are cool components.

Sample Explanation 2

This sample has the same trees as the first one, but is of type $$$X = 1$$$.

E. Connecting Buildings
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Confused by MIT's building layout, Busy Beaver decided to design a simpler layout – the Majestic Interconnected Toroid Institute of Technology (MITIT)...

There are $$$N$$$ main buildings numbered $$$1,\dots,N$$$ arranged on a circle with circumference $$$C$$$. The $$$i$$$th building is located at position $$$L_i$$$ ($$$0 \le L_i \lt C$$$) along the circle and has a height of $$$H_i$$$. There is one more building, the student center, located at the center of the circle whose height is not decided yet.

Busy Beaver wants to connect the $$$N+1$$$ buildings with some straight tunnels such that any building can reach any other building using these tunnels. A tunnel can be modeled as a line segment (in a 2-dimensional plane) connecting two of the buildings. All these tunnels will be at the same elevation, so their corresponding line segments must not intersect (except at endpoints). For some reason, the cost of constructing a tunnel between two buildings with heights $$$h_1$$$ and $$$h_2$$$ is equal to $$$|h_1-h_2|$$$.

Busy Beaver has $$$Q$$$ questions $$$M_1,\dots,M_Q$$$, where he wonders: What is the minimum possible cost to connect all the buildings if the student center has a height of $$$M_i$$$?

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \le T \le 500$$$). The description of the test cases follows.

The first line of each test case contains three integers, $$$N$$$, $$$Q$$$, and $$$C$$$ ($$$1 \le N \le 500$$$, $$$1 \le Q \le 10^6$$$, $$$1 \le C \le 10^9$$$).

The $$$i^\text{th}$$$ of the next $$$N$$$ lines contains two integers $$$L_i$$$ and $$$H_i$$$ ($$$0 \le L_i \lt C$$$, $$$1 \le H_i \le 10^9$$$).

The $$$i^\text{th}$$$ of the next $$$Q$$$ lines contains a single integer $$$M_i$$$ ($$$1 \le M_i \le 10^9$$$).

The $$$L_i$$$ are pairwise distinct and there does not exist two diametrically opposite buildings ($$$i$$$ and $$$j$$$ such that $$$L_i = L_j+C/2$$$).

It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$500$$$.

It is guaranteed that the sum of $$$Q$$$ over all test cases does not exceed $$$10^6$$$.

Output

Output $$$Q$$$ lines: the minimum cost to connect all the buildings when the student center has a height of $$$M_1,\dots,M_Q$$$ respectively.

Scoring

Let $$$\sum N$$$ denote the sum of $$$N$$$ over all test cases and $$$\sum Q$$$ denote the sum of $$$Q$$$ over all test cases.

  • ($$$15$$$ points) $$$\sum N,\sum Q \le 80$$$ and $$$0 \le L_i \lt C/2$$$ for all $$$i$$$.
  • ($$$15$$$ points) $$$\sum N,\sum Q \le 80$$$.
  • ($$$15$$$ points) $$$\sum N \le 80$$$ and $$$0 \le L_i \lt C/2$$$ for all $$$i$$$.
  • ($$$10$$$ points) $$$\sum N \le 80$$$.
  • ($$$15$$$ points) $$$\sum Q \le 500$$$ and $$$0 \le L_i \lt C/2$$$ for all $$$i$$$.
  • ($$$10$$$ points) $$$\sum Q \le 500$$$.
  • ($$$10$$$ points) $$$0 \le L_i \lt C/2$$$ for all $$$i$$$.
  • ($$$10$$$ points) No additional constraints.
Example
Input
2
4 4 5
0 3
1 1
2 4
4 1
5
9
2
6
1 1 1000000000
998244353 998244353
1
Output
6
10
5
7
998244352
Note

One optimal way to connect the buildings for the questions in the first test case are as shown:

For the second test case, the cost to connect the student center with the only other building is $$$|1-998244353| = 998244352$$$.

F. Array Gerrymandering
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Busy Beaver has decided to run for president. Unfortunately, his only other rival, Lazy Lemur, is too strong, and Busy Beaver can't win using normal means. Therefore, he does what all good politicians do: rig the election via gerrymandering!

Busy Beaver's country consists of $$$N$$$ cities in a row numbered $$$1$$$ to $$$N$$$. Each city votes either Lazy Lemur or Busy Beaver as president, represented by a $$$0$$$ if the vote is for Lazy Lemur and a $$$1$$$ if the vote is for Busy Beaver. However, Busy Beaver gets to split the $$$N$$$ cities into $$$K$$$ nonempty blocks of contiguous cities, where each block is a district. For every value of $$$K$$$ from $$$1$$$ to $$$N$$$, Busy Beaver wishes to maximize the number of districts that have strictly more votes for him than Lazy Lemur.

Can you help Busy Beaver find the maximum number of districts with strictly more votes for $$$K = 1, \dots, N$$$?

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \le T \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains one integer $$$N$$$ ($$$1 \le N \le 10^5$$$) describing the number of cities.

The second line of each test case contains a string $$$s$$$ of $$$0$$$'s and $$$1$$$'s of length $$$N$$$, where $$$s_i$$$ being $$$0$$$ denotes Lazy Lemur winning the $$$i^\text{th}$$$ city's vote and a $$$1$$$ denoting Busy Beaver winning the $$$i^\text{th}$$$ city's vote, for each $$$i$$$ from $$$1$$$ to $$$N$$$.

It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case, output $$$N$$$ integers, where the $$$K^\text{th}$$$ integer represents the maximum number of districts with strictly more votes for Busy Beaver after splitting the cities into $$$K$$$ nonempty blocks of contiguous cities.

Scoring
  • ($$$10$$$ points) The sum of $$$N$$$ across all test cases is at most $$$100$$$.
  • ($$$25$$$ points) The sum of $$$N$$$ across all test cases is at most $$$3000$$$.
  • ($$$65$$$ points) The sum of $$$N$$$ across all test cases is at most $$$10^5$$$.
Example
Input
3
3
000
5
01101
8
11011011
Output
0 0 0
1 1 2 2 3
1 2 3 4 4 5 5 6
Note

There are $$$3$$$ test cases.

In the first test case, Busy Beaver can never win any districts because every city is voting for Lazy Lemur.

In the second test case, there are $$$5$$$ cities. For $$$K = 3$$$, Busy Beaver can win $$$2$$$ districts by splitting the cities into districts using the subarrays $$$[1, 3]$$$, $$$[4, 4]$$$, and $$$[5, 5]$$$. In $$$[1, 3]$$$, $$$2$$$ out of the $$$3$$$ cities vote for him. He loses the subarray $$$[4, 4]$$$ because the one city there does not vote for him. He wins the subarray $$$[5, 5]$$$ because the one city there votes for him. It can be proven that Busy Beaver cannot win more than $$$2$$$ districts.

Notice that splitting into subarrays $$$[1, 2]$$$, $$$[3, 4]$$$, and $$$[5, 5]$$$ would only win him $$$1$$$ district. In particular, he wins only one city in each of $$$[1, 2]$$$ and $$$[3, 4]$$$, and thus does not hold a strict majority in either district.