Connection Status:
Competition Arena > DinnerTable

DinnerTable

SRM 848 · 2023-08-03 · by misof

SRM 848 · 2023-08-03 · by misof · Sorting
Class Name: DinnerTable
Return Type: long
Method Name: count
Arg Types: (int, int, int, int)
Problem Statement

Problem Statement

The floor of our dining room is a rectangle divided into a grid of R by C unit square tiles. The tiles have integer coordinates ranging from (0, 0) to (R-1, C-1).

Some of the tiles are empty, others contain pillars that support the roof. There are at most N pillars (explained below).


We want to place a L x 1 dining table somewhere into the dining room. The table must be placed parallel to one of the sides and it must cover exactly L empty tiles.

In other words, the table must be placed either "horizontally" or "vertically", and it must avoid all pillars.


You are given the dimensions of the dining room and the table, and the coordinates of all pillars (as described below).

Return the number of ways in which the table can be placed.


In order to keep the input small, we will simply pick one specific pattern for the pillars:

  • Let r(i) = (4*i*i + 7*i) modulo R.
  • Let c(i) = (i*i*i + 8*i + 13) modulo C.
  • For each i from 0 to N-1, inclusive, the tile with coordinates (r(i), c(i)) contains a pillar.
  • No other tile contains a pillar.

Notes

  • The reference solution does not use any properties of the pattern of pillars. It can correctly solve the task for any configuration of N pillars.
  • Watch out for integer overflow when computing the values r(i) and c(i).
  • Different values of i may give you the same tile (r(i), c(i)). If that happens, there will be fewer than N pillars.
  • For any valid input the return value is guaranteed to fit into a 64-bit signed integer variable.

Constraints

  • R will be between 1 and 10^9, inclusive.
  • C will be between 1 and 10^9, inclusive.
  • L will be between 2 and 10^9, inclusive.
  • N will be between 0 and 10^5, inclusive.
Examples
0)
5
6
6
0
Returns: 5

The dining room has 5 rows by 6 columns. The dining table has length 6. There are no pillars. There are exactly 5 valid ways to place the table: it has to fill one of the rows.

1)
5
6
5
0
Returns: 16

Same dining room as above, but now the table only has length 5. There are two ways to place it into each row (either it touches the left or the right side), and there is one way to place it into each column. That's a total of 5*2 + 6*1 = 16 ways.

2)
5
6
7
0
Returns: 0

This table is too long for this dining room.

3)
5
6
4
2
Returns: 20

The two pillars are at (0, 1) and at (1, 4). Thus, the dining room looks as follows ('O' is a pillar, '.' is an empty tile): .O.... ....O. ...... ...... ...... There are 11 ways to place the table "horizontally" and 9 ways to place it "vertically". Two of these are shown below, with 'X's denoting the table. .O.... XXXXO. ...... ...... ...... .O.... ...XO. ...X.. ...X.. ...X..

4)
5
6
4
3
Returns: 20

The answer for N=3 is exactly the same as for N=2. This is because for i=2 we get the cell (r(i), c(i)) = (0, 1) again, thus there is no new pillar.

5)
5
6
4
5
Returns: 16

The dining room now looks as follows: .O.... ....O. .O..O. ...... ......

6)
100000
100000
10000
20000
Returns: 17666220715

Watch out for integer overflows!

7)
4
1
2
100000
Returns: 0

This dining room is completely covered by pillars. There is no room at all for the table.

Submissions are judged against all 99 archived test cases, of which 8 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class DinnerTable with a public method long long count(int R, int C, int L, int N) · 99 test cases · 2 s / 256 MB per case

Submitting as anonymous