WolfHockeyTeamHard
SRM 690 · 2016-05-02 · by tozangezan
Problem Statement
There are 2*N wolves on the ice hockey team. The wolves are numbered from 0 to 2*N-1.
Cat Snuke is going to take photos of the whole team. The photos all have to look nice and they all have to look different. Both "nice" and "different" are formally defined below.
While taking each photo, the wolves will stand in a grid pattern with two rows by N columns. There is only one constraint: each row of the grid must contain a wolf whose number is K or more. Any such arrangement of wolves will look nice in a photo.
Given a photo of our 2*N wolves, we can look at it and write down a sequence of N+2 integers:
- For each column (from the left to the right), write down the largest wolf number in that column.
- Write down the largest wolf number in the first row.
- Write down the largest wolf number in the second row.
You are given the
Constraints
- N will be between 1 and 500,000, inclusive.
- K will be between 0 and 2N-1, inclusive.
2 0 Returns: 12
As N=2, we have four wolves. As K=0, each row of the grid must contain a wolf numbered 0 or more, which is always true. Hence, all 24 possible arrangements of wolves produce nice photos. However, some of those arrangements produce similar photos. For example, suppose there are wolves 1 and 2 in the first row and behind them wolves 0 and 3 in the second row. For this arrangement, we have: The maximum in the first column is max(1,0) = 1. The maximum in the second column is max(2,3) = 3. The maximum in the first row is max(1,2) = 2. The maximum in the second row is max(0,3) = 3. Hence, this arrangement produces the sequence {1,3,2,3}. Now suppose there are wolves 0 and 2 in the first row and wolves 1 and 3 in the second row. This is a different arrangement but it produces the same sequence: {1,3,2,3}. In total, Cat Snuke will be able to take at most 12 different photos. These correspond to the sequences {1,3,2,3}, {1,3,3,2}, {2,3,1,3}, {2,3,2,3}, {2,3,3,1}, {2,3,3,2}, {3,1,2,3}, {3,1,3,2}, {3,2,1,3}, {3,2,2,3}, {3,2,3,1}, and {3,2,3,2}.
4 5 Returns: 1104
100 78 Returns: 68021677
2100 4199 Returns: 0
Note that in this example K = 2*N-1. There is only one wolf with the number 2*N-1 or greater. Thus, in this case there are no nice photos: in one of the rows all wolves will always have numbers smaller than K.
81019 114514 Returns: 793441075
Submissions are judged against all 59 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class WolfHockeyTeamHard with a public method int count(int N, int K) · 59 test cases · 2 s / 256 MB per case