Busy Beaver is studying Archaeology and Materials at MIT! He has been studying ancient inscriptions made only of the letters M, I, and T and notices the following rule: any time the substring MIT appears, it may be rearranged into TIM, and any time TIM appears, it may be rearranged back into MIT.
Now Busy Beaver wants to form as many occurrences as possible of his favorite pattern, MITIT, in the string. Help him determine the maximum number of contiguous substrings equal to MITIT that can appear after performing any number of operations (possibly zero).
The first line contains an integer $$$T$$$ $$$(1 \le T \le 10^5)$$$ — the number of test cases.
The only line of each test case contains a string of length at most $$$10^5$$$ consisting of the characters M, I, and T.
The total length of all strings does not exceed $$$10^5$$$.
For each test case, output a single integer — the maximum number of substrings MITIT that can appear after performing any number of operations.
6TITIMMITTITITIMITIMTMTMTMMITMIMIMTITMTIMTITMTITITMTIITMTTMITMITMTMTITITMIMMMITMITTTIMTITITTTITITMITITIMIMIMITITITITIMIMIMIMIMIMITITITITTIIMITMTIMTIITMITMTIMTITIITITMTIMI
120005
In the first test case, we can do the following operations: TITIMMIT $$$\to$$$ TIMITMIT and TIMITMIT $$$\to$$$ MITITMIT. We can prove that it is impossible to construct two copies of MITIT inside this string.
Mr. Busy Beaver is very stressed: he has to babysit $$$N$$$ baby beavers who are strangely obsessed with arranging themselves into one gigantic snake(?!).
The $$$i$$$-th baby beaver starts at a distinct point $$$(x_i, y_i)$$$ on an infinite Cartesian plane. Then, they will all start moving. At all times, each beaver's velocity $$$\vec{v} = (v_x, v_y)$$$ must satisfy $$$$$$ |v_x| \le 1 \quad\text{and}\quad |v_y| \le 1 \quad \text{(cells per second)}. $$$$$$ They will only be satisfied once their final positions lie along a path that moves only upward and rightward (i.e., nondecreasing in both $$$x_i$$$ and $$$y_i$$$). Note that multiple beavers can be at the same point.
Busy Beaver is exhausted, and he just wants to go home. Help him find twice the minimum time required to coordinate these babies into the described snake formation. It can be proven that this value is an integer.
The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^4$$$) — the number of test cases.
Each test case begins with one integer $$$N$$$ ($$$1 \le N \le 2 \cdot 10^5$$$) — the number of baby beavers.
Each of the next $$$N$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$0 \le x_i, y_i \le 10^9$$$) — the initial coordinates of the $$$i$$$-th beaver.
All $$$(x_i, y_i)$$$ in a test case are distinct.
The sum of $$$N$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, print one integer — twice the minimum number of seconds needed for the beavers to reach a valid snake formation.
There are two subtasks for this problem.
- ($$$30$$$ points): The sum of $$$N$$$ over all test cases does not exceed $$$3000$$$.
- ($$$70$$$ points): No additional constraints.
141 82 68 55 3
4
In the sample test case, one way for the beavers to reach a snake formation in $$$2$$$ seconds is as follows:
- The beaver at $$$(5,3)$$$ can move to $$$(3,5)$$$ in $$$2$$$ seconds.
- The beaver at $$$(2,6)$$$ can move to $$$(3,6)$$$ in $$$1$$$ second, and then stay there for $$$1$$$ second.
- The beaver at $$$(1,8)$$$ can move to $$$(3,6)$$$ in $$$2$$$ seconds.
- The beaver at $$$(8,5)$$$ can stay still for $$$1$$$ second, and then move to $$$(8,6)$$$ in $$$1$$$ second.
We can show that it is impossible to form a snake with less time. Therefore, the answer is $$$2 \cdot 2 = 4$$$, twice the minimum number of seconds.
Busy Beaver lived on an unpainted sidewalk consisting of $$$N$$$ individual tiles numbered $$$1,2,\dots,N$$$ from left to right. The tiles all start with the factory-standard color $$$0$$$, but Busy Beaver is looking to change that! Over several days of painting, Busy Beaver aims to repaint the entire sidewalk.
Specifically, Busy Beaver wrote down a list of $$$Q$$$ plans, the $$$i$$$-th of which states that on day $$$d_i$$$ ($$$0 \le d_i \le 2^K-1$$$), Busy Beaver will repaint all tiles in the range $$$[x_i, y_i]$$$ with color $$$c_i$$$, overwriting their previous colors. Busy Beaver has at most one painting plan scheduled for each day, and he is interested in the sum of the final colors of all tiles after all the repaintings.
Unbeknownst to Busy Beaver, he is, in fact, the first Beaver to live in a Quantum Computer! This unfortunately means that the universe does not operate as he thinks it does. During the night, while no one is watching, the qubits undergo a random transformation: an integer $$$z$$$ between $$$0$$$ and $$$2^K - 1$$$ is selected, and every plan originally scheduled for day $$$i$$$ is instead moved to day $$$i \oplus z$$$, where $$$\oplus$$$ denotes bitwise XOR.
For a given $$$z$$$, the plans are then executed in increasing order of their (shifted) day, and each repaint operation overwrites the colors of the tiles between $$$x_i$$$ and $$$y_i$$$. Let $$$F(z)$$$ be the sum of the final colors of all tiles after applying the plans with shift $$$z$$$.
Compute $$${\large \sum_{z=0}^{2^K - 1}} F(z)$$$. Since the answer may be enormous, output it modulo $$$10^9+7$$$.
Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1\leq T\leq 150$$$). The description of the test cases follows.
The first line of each test case contains three integers $$$N$$$, $$$K$$$, and $$$Q$$$ ($$$1\leq N\leq 2\cdot10^5$$$, $$$0\leq K\leq60$$$, $$$1\leq Q\leq \min(2^K,2\cdot 10^5)$$$).
The $$$i$$$-th of the next $$$Q$$$ lines contains four integers $$$d_i$$$, $$$x_i$$$, $$$y_i$$$, and $$$c_i$$$ ($$$0\leq d_i \lt 2^K$$$, $$$1\leq x_i\leq y_i\leq N$$$, $$$0\leq c_i\leq10^9$$$).
It is guaranteed that the sum of $$$N$$$ across all test cases is at most $$$4\cdot10^5$$$, the sum of $$$Q$$$ across all test cases is at most $$$4\cdot10^5$$$, and all $$$d_i$$$'s within a test case are distinct.
For each test case, output one integer on its own line: the sum of the answers to Busy Beaver's original question over all $$$2^K$$$ possible shifts, modulo $$$10^9+7$$$.
There are five subtasks for this problem.
- ($$$10$$$ points): The sum of $$$N$$$, $$$2^K$$$, and $$$Q$$$ over all test cases are each less than or equal to $$$5 \cdot 10^3$$$. Note that this refers to each of the individual sums, not the cumulative sum of all of them. Also, $$$c_i \le 5 \cdot 10^3$$$ for all $$$i$$$.
- ($$$20$$$ points): For all test cases, $$$N=1, Q \le 2$$$.
- ($$$20$$$ points): For all test cases, $$$N=1$$$.
- ($$$20$$$ points): For all test cases, $$$K\leq 18$$$.
- ($$$30$$$ points): No further constraints.
36 4 66 3 5 412 2 2 34 1 4 25 3 3 414 1 1 313 1 6 46 4 44 1 2 03 2 6 42 2 2 25 3 5 04 4 68 2 4 211 1 3 29 3 4 410 3 3 22 3 4 33 1 4 5
332184220
35 4 49 1 2 212 1 3 110 4 5 314 1 5 46 4 45 2 4 314 5 6 210 3 6 31 4 6 56 4 511 2 4 513 1 2 414 4 6 510 1 6 315 2 6 0
224272276
Busy Beaver is an avid fan of Sheet Music Boss and dreams of playing long, intricate pieces on his piano. However, with only a measly $$$10$$$ fingers, there's not much he can do. Fortunately, his friend Ditto can grow an arbitrary number of fingers on their hand, letting them play any piece imaginable.
Ditto is trying to play a song consisting of $$$N$$$ notes, numbered $$$1$$$ to $$$N$$$. To play the $$$i$$$-th note, Ditto must press key $$$k_i$$$ at time $$$a_i$$$ and let go at time $$$b_i$$$. It is guaranteed that no two notes with the same key are played at the same time. In other words, for all pairs of notes $$$(i,j)$$$ where $$$k_i=k_j$$$, either $$$b_i\le a_j$$$ or $$$b_j\le a_i$$$.
Ditto plans to use a single hand with $$$F$$$ fingers, numbered left to right from $$$1$$$ to $$$F$$$, to play the song. They want to assign the finger $$$f_i$$$ to the $$$i$$$-th note. Ditto can play the song if they can assign a finger to each note to satisfy the following criteria:
- At no point in time do their fingers cross. Formally, for all pairs of notes $$$(i,j)$$$ where there exists a time $$$t$$$ where $$$a_i \lt t \lt b_i$$$ and $$$a_j \lt t \lt b_j$$$, if $$$k_i \lt k_j$$$, then $$$f_i \lt f_j$$$.
Ditto is allowed to delete up to $$$M$$$ notes from the song, where $$$M$$$ is $$$\mathbf{0}$$$ or $$$\mathbf{1}$$$. Find the minimum number of fingers they need on their hand in order to play the rest of the song. In other words, find the smallest $$$F$$$ where there exists a finger assignment $$$f$$$ that satisfies the above criteria.
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 two integers $$$N$$$ and $$$M$$$ ($$$1\le N\le 2\cdot 10^5$$$, $$$M=0$$$ or $$$1$$$).
The $$$i$$$-th of the next $$$N$$$ lines contains three integers $$$k_i$$$, $$$a_i$$$, and $$$b_i$$$ ($$$1\le k_i \le 10^9$$$, $$$1\le a_i \lt b_i \le 10^9$$$) — meaning that the $$$i$$$-th note uses key $$$k_i$$$ from time $$$a_i$$$ to time $$$b_i$$$.
It is guaranteed that no two notes with the same key are played at the same time and the sum of $$$N$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.
For each test case, print the minimum number of fingers Ditto needs on their hand so that after at most $$$M$$$ note deletions, there exists a satisfactory finger assignment.
There are three subtasks for this problem.
- ($$$10$$$ points): The sum of $$$N$$$ over all test cases does not exceed $$$10^3$$$ and $$$M=0$$$.
- ($$$20$$$ points): $$$M=0$$$.
- ($$$70$$$ points): No additional constraints.
55 03 3 65 2 56 5 61 1 41 5 75 12 1 610 1 64 5 98 5 96 8 104 11 1 22 1 21 3 42 3 41 06 2 51 16 2 5
33210
The notes for the first test case are shown below. The x-axis is the key pressed, and the y-axis is the time interval the note is pressed. The minimum number of fingers required is $$$3$$$ — each note is labeled with a finger to achieve this.
The notes for the second test case are shown below. Deleting either the yellow or blue note would make $$$3$$$ fingers sufficient, and this is optimal.
Busy Beaver has taken on a new engineering challenge: designing a water distribution system for his growing beaver colony. The system will consist of $$$N$$$ water stations (nodes) connected by pipes (edges), where no pipe connects a station to itself and no two stations have more than one pipe between them. As a careful planner, Busy Beaver ensures the entire system is connected; that is, water can flow from any station to any other through some series of pipes.
Busy Beaver wants his system to be resilient: no matter which spanning tree of pipes is chosen to serve as the active network, there must always be at least one main station, a node with degree at least $$$K$$$ in that tree, where $$$\frac{N + 3}{2} \le K \lt N$$$.
How many distinct connected pipe networks on $$$N$$$ labeled stations satisfy this condition? Two networks are considered distinct if they differ by at least one pipe. Since the answer may be enormous, output it modulo $$$998\,244\,353$$$.
The input contains two integers $$$N$$$ and $$$K$$$ ($$$5 \le N \le 5000$$$, $$$\frac{N + 3}{2} \le K \lt N$$$).
Output a single integer — the number of connected graphs satisfying the condition, modulo $$$998\,244\,353$$$.
There are four subtasks for this problem.
- ($$$10$$$ points): $$$N\le 7$$$.
- ($$$20$$$ points): $$$K \ge \max(N - 5,\frac{N + 3}{2})$$$.
- ($$$50$$$ points): $$$N \le 200$$$.
- ($$$20$$$ points): No additional constraints.
7 5
322
50 28
360690501