DivideThePlane
2021 HF Prelim · 2021-03-02 · by misof
Problem Statement
You have a two-dimensional plane. You have already drawn some lines onto the plane: exactly H distinct horizontal lines and exactly V distinct vertical lines.
The lines can be seen as region boundaries. You want to divide your plane into at least N regions. If necessary, you can draw additional straight lines. Each of the new lines must also be either horizontal or vertical.
Compute and return the minimum number of additional lines you need.
Constraints
- H will be between 0 and 10^6, inclusive.
- V will be between 0 and 10^6, inclusive.
- N will be between 1 and 10^14, inclusive.
0 0 1 Returns: 0
You don't have any lines drawn yet. You want to have at least one region. Luckily, the whole plane is now one region and that's exactly what you need, so you do not have to draw any lines.
0 0 3 Returns: 2
If you draw a single line, you will have two regions, which isn't enough. Thus, you need at least two lines. Drawing two lines is clearly sufficient. We can draw two parallel lines and get three regions, or we can draw two perpendicular lines and get four regions. Both of these ways are valid optimal solutions for this test case.
4 0 3 Returns: 0
You already have four horizontal lines. These already divide the plane into five regions, so you have enough regions and you do not have to draw any more lines.
4 0 20 Returns: 3
The only optimal solution here is to draw three vertical lines. This will produce exactly 20 regions. The plane will look as follows: | | | | | | ----+--+--+---- | | | ----+--+--+---- | | | ----+--+--+---- | | | ----+--+--+---- | | | | | | and here are the individual regions numbered: | | | 1| 2| 3| 4 ----+--+--+---- 5| 6| 7| 8 ----+--+--+---- 9|10|11|12 ----+--+--+---- 13|14|15|16 ----+--+--+---- 17|18|19|20 | | |
1 3 35 Returns: 6
One of the multiple optimal solutions is to add five new horizontal lines and one new vertical line (so there will be a total of six horizontal and four vertical lines). Another optimal solution is to add four horizontal and two vertical lines. In either case the total number of new lines is six.
99999 99997 10000000000 Returns: 2
Watch out for integer overflow.
Submissions are judged against all 97 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class DivideThePlane with a public method long long makeCuts(int H, int V, long long N) · 97 test cases · 2 s / 256 MB per case