Questions: Checkpoint 4 — Mock Contest 4

A farm map shows grass (.) and fences (#). Two grass cells belong to the same pasture when they are next to each other up, down, left, or right (NOT diagonally). A farmer asks Q questions, each naming one cell: how many grass cells are in the pasture containing that cell? The answer is 0 when the named cell is a fence.

First line: R C Q. Then R rows of the map, then Q lines, each a zero-indexed r c. Print one answer per line, in question order.

Flood-fill every pasture only once with a recursive walk, giving each grass cell its pasture number and recording each pasture's size; then answer each question by looking up its cell. In the sample, the pasture containing 0 3 winds down and around through 7 cells, the cell 1 1 is a fence, and the corner cell 3 4 is a pasture of its own because it touches other grass only diagonally.

Constraints. 1 <= R, 1 <= C, R*C <= 400, and 1 <= Q <= 200000. Every question names a cell inside the map. Flood-filling again for every question will not finish in time.

Sample Input

4 5 4
..#..
.##.#
#...#
##.#.
0 0
0 3
1 1
3 4

Sample Output

3
7
0
1

A storeroom map has mold (M), clean shelf space (.), and walls (#). Every minute, mold spreads from each moldy cell into every clean cell next to it up, down, left, or right; walls never grow mold. Print the number of minutes until no clean cell is left: 0 if there is no clean cell at the start, or -1 if some clean cell can never be reached.

First line: R C. Then R rows of the map. Print the minute count (or -1) as an integer string.

Run one BFS that starts from every mold cell at once: put all of them on a FIFO deque with time 0 before the first popleft, and give each clean cell the time at which it is first reached. In the sample, the mold in the bottom-right corner covers its side of the room within 2 minutes; without that second patch, the last clean cell would be reached only after 5 minutes.

Constraints. 1 <= R, 1 <= C, R*C <= 200000, and the map contains at least one M. Re-scanning the whole map once per minute will not finish in time.

Sample Input

3 4
M..#
.#..
#..M

Sample Output

2

A coach must split N students (numbered 1..N) into two teams, and M pairs of students are rivals who must not be on the same team. A team may be empty. Print YES if such a split exists, otherwise NO.

First line: N M. Then M lines, each u v, meaning students u and v are rivals. Print YES or NO.

Build an adjacency-list dictionary and use a recursive DFS that places a student on a team and then places each unplaced rival on the other team; if a rival is already on the same team as the student, the split is impossible. Start a new DFS from every student who is still unplaced, because the rivalries may form several separate groups. In the sample, the six rivalries join six students in one ring, so the teams can alternate around it; a ring with an odd number of students could not be split.

Constraints. 1 <= N <= 500, 0 <= M <= 20000. No student is their own rival, and no rival pair is listed twice. Trying every way to form the two teams will not finish in time.

Sample Input

6 6
1 2
2 3
3 4
4 5
5 6
1 6

Sample Output

YES

A row of N fence posts stands at positions 0 through N - 1, and post i has height h[i]. Any two different posts i < j form a trough that holds min(h[i], h[j]) * (j - i) units of rainwater. Print the most water any trough can hold.

Use converging two pointers: start lo at the first post and hi at the last, record the current trough, then move the pointer at the SHORTER post one step inward (move hi when the two heights are equal). Stop when the pointers meet. In the sample, the final post is one wall of the best trough; without it the answer would be only 18.

First line: N. Then N non-negative integer heights (they may span several lines). Print the largest amount of water as an integer string.

Constraints. 2 <= N <= 200000, and every height is between 0 and 1000000000. Checking every pair of posts will not finish in time.

Sample Input

7
2 8 3 1 6 4 7

Sample Output

35

A row of N ice-cream tubs is labelled with flavor numbers. Find the length of the SHORTEST stretch of neighbouring tubs that contains at least one tub of every flavor appearing anywhere in the row.

First line: N. Then N flavor numbers. Print the shortest length as an integer string.

Use a sliding window: grow right one tub at a time while a dictionary counts each flavor inside the window, and keep track of how many different flavors the window holds; whenever the window holds every flavor, record its length and shrink from left, lowering the count of the flavor that leaves. In the sample, the row has flavors 1, 2, and 3; every stretch that starts earlier needs at least 4 tubs, and the unique shortest stretch 3 1 2 ends on the final tub.

Constraints. 1 <= N <= 200000, and every flavor number is between 1 and 1000000000. Checking every stretch will not finish in time.

Sample Input

8
2 2 1 1 3 3 1 2

Sample Output

3

On day 1, one letter is sent, even when A is 0. On every later day, each letter sent the day before causes A new letters, so day k sends A to the power k - 1 letters. Given A, a number of days E, and a modulus M, print the total number of letters sent during the first E days modulo M: the remainder of 1 + A + A^2 + ... + A^(E - 1) after dividing by M (the total is 0 when E is 0).

Input: A E M on one line. Print the total modulo M.

E can be as large as 10^18, so adding one day at a time is infeasible, and because M need not be prime you cannot divide by A - 1. Instead, use repeated squaring on a pair of values reduced modulo M: power for A^e and total for the letters of the first e days. Doubling the days turns the pair into total + power * total and power * power; adding one more day turns it into total + power and power * A. Write the bits of E from the most significant bit down, start from e = 0 (power = 1, total = 0), double for every bit, and then add one day when that bit is 1, reducing modulo M after every multiplication. Do not use a built-in modular-power shortcut (no three-argument pow). Your algorithm must use O(log E) modular multiplications. In the sample, the six days send 1 + 3 + 9 + 27 + 81 + 243 = 364 letters, which is 64 modulo 100.

Constraints. 0 <= A <= 10^18, 0 <= E <= 10^18, 1 <= M <= 10^18.

Sample Input

3 6 100

Sample Output

64

Trace this exact breadth-first routine and predict what it prints. Neighbours are visited in the order the edges are given.

seed visited with the single start node          # visited = {start}
put start on the back of a FIFO queue
while the queue is not empty:
    take a node u from the FRONT of the queue
    print u
    for each out-neighbour v of u, in input order:
        if v is not visited:
            mark v visited and put it on the BACK of the queue

Input first line: N M start (nodes 1..N, M directed edges, and the BFS start node). Then M lines, each u v, a directed edge u -> v; a node's out-neighbours are in input order. Print the printed node ids in the order the routine prints them, space-separated.

Constraints. 1 <= N <= 30, 0 <= M <= 200.

Sample Input

3 2 1
1 2
1 3

Sample Output

1 2 3