KOI Team Selection Test 2025
Original Statement / Submission Site
KOI City was formed around a large river that runs through the city from east to west. There are N villages on each side of the river.
The villages on the north side are labeled A1, A2, ..., AN in order from downstream to upstream. The villages on the south side are labeled B1, B2, ..., BN in the same order. Thus, KOI City contains a total of 2N villages.
The people of KOI City originally traveled and interacted using rafts. As the city modernized, bridges were constructed across the river.
Since KOI City developed from downstream to upstream, the first bridge connected villages A1 and B1. This bridge is called bridge 0. The city then constructed bridges 1, 2, ..., 2N - 2 in this order, for a total of 2N - 1 bridges.
After bridge 0 was built, every new bridge was constructed adjacent to the previously built bridge. More precisely, for every 0 ≤ i ≤ 2N - 3, suppose bridge i connects villages Ax and By. Then bridge i + 1 connects either:
Ax and By+1, orAx+1 and By.Which of these two cases occurs is recorded by a string S of length 2N - 2:
S[i] = 'A', bridge i + 1 connects Ax and By+1.S[i] = 'B', bridge i + 1 connects Ax+1 and By.The string S contains exactly N - 1 occurrences of 'A' and exactly N - 1 occurrences of 'B'. Consequently:
2N - 2 connects villages AN and BN.KOI City plans to perform maintenance work on some of the 2N - 1 bridges. Because the work is noisy, the city wants to avoid selecting two or more bridges incident to the same village.
Subject to this restriction, the city wants to maintain as many bridges as possible. It also wants to compute the number of different ways to choose the maximum possible number of bridges, modulo 109 + 7.
Two maintenance plans are considered different if the sets of selected bridges are different.
You must compute both values. However, partial credit is available for computing only the maximum number of bridges correctly.
Implement the function described below.
std::array<int, 2> roadwork(std::string S)S: a string of length 2N - 2.T times in a single test case.p be the maximum number of bridges that can be selected for maintenance.q be the number of ways to select exactly p bridges, modulo 109 + 7.{p, q}, where 0 ≤ q ≤ 109 + 6.1 ≤ T ≤ 102 ≤ N ≤ 221S contains exactly N - 1 occurrences of 'A' and exactly N - 1 occurrences of 'B'.N ≤ 21N ≤ 23N ≤ 25N ≤ 27N ≤ 29N ≤ 211N ≤ 213N ≤ 215N ≤ 217N ≤ 219There are no additional constraints.
In every subtask, returning only the correct maximum number of bridges earns 40% of that subtask's score.
Consider N = 2 and S = "AB". The grader calls:
roadwork("AB")
The structure of KOI City is shown below.
By maintaining bridges 0 and 2, it is possible to select a maximum of 2 bridges. This is the only way to select two bridges, so the function must return:
{2, 1}
Returning a value such as {2, -1} or {2, 0} is considered correct only for the maximum-number component.
There are three ways to select exactly one bridge, but these are not counted because one bridge is not the maximum possible number.
Consider N = 7 and S = "AABBAABBAABB". The grader calls:
roadwork("AABBAABBAABB")
The structure of KOI City is shown below.
At most 6 bridges can be selected for maintenance, and there are exactly 4 ways to do so. Therefore, the function must return:
{6, 4}
The sample grader reads input in the following format:
T N1 S1 N2 S2 ... NT ST
Let C[i] be the array returned by roadwork for the i + 1-st test case. The sample grader prints:
C[0][0] C[0][1] C[1][0] C[1][1] ... C[T-1][0] C[T-1][1]
Note that the sample grader may differ from the grader used for actual evaluation.