2-D Permutations

View as PDF

Submit solution

All submissions

Best submissions

Points: 10 (partial)

Time limit: 2.0s

Memory limit: 1G

Author:

4fecta

Problem type

Edward spent the whole weekend brainstorming problems involving 2-D arrays. Unfortunately, they were all too hard, so he came up with this instead:

You are given $N \times M$ $N \times M$ integers, numbered from $1$ $1$ to $N \times M$ $N \times M$ . You would like to arrange these numbers into an $N \times M$ $N \times M$ array $A$ $A$ . The rows are numbered from $1$ $1$ to $N$ $N$ and the columns from $1$ $1$ to $M$ $M$ . Denote the number assigned to the $i$ $i$ -th cell from the top and the $j$ $j$ -th cell from the left $A_{i, j}$ $A_{i, j}$ . An arrangement is called valid if for all cells with $i > 1$ $i > 1$ , $A_{i, j} > A_{i-1, j}$ $A_{i, j} > A_{i - 1, j}$ , and for all cells with $j > 1$ $j > 1$ , $A_{i, j} > A_{i, j-1}$ $A_{i, j} > A_{i, j - 1}$ . You are also given $Q$ $Q$ queries. For each query, a number $q_i$ $q_{i}$ is given, and you must return the number of different cells $q_i$ $q_{i}$ can be placed in all valid arrangements.

Edward has no idea how to solve this problem either. Please help him solve it.

Input Specification

The first line will contain three integers $N$ $N$ , $M$ $M$ , and $Q$ $Q$ , the dimensions of the array and the number of queries.

The next $Q$ $Q$ lines will each contain one integer $q_i$ $q_{i}$ , as specified in the problem statement.

Output Specification

Output $Q$ $Q$ lines, the $i$ $i$ -th line containing the number of different cells $q_i$ $q_{i}$ can be placed in all valid arrangements.

Constraints

For all subtasks:

$1 \le N, M \le 5000$ $1 \leq N, M \leq 5000$

$1 \le Q \le 10^6$ $1 \leq Q \leq 10^{6}$

$1 \le q_i \le N \times M$ $1 \leq q_{i} \leq N \times M$

Subtask 1 [15%]

$1 \le N \times M \le 10$ $1 \leq N \times M \leq 10$

$1 \le Q \le 10$ $1 \leq Q \leq 10$

Subtask 2 [35%]

$1 \le N, M, Q \le 300$ $1 \leq N, M, Q \leq 300$

Subtask 3 [50%]

No additional constraints.

Sample Input 1

Copy

Sample Output 1

Copy

Explanation for Sample 1

The two valid arrangements are:

1	2
3	4

1	3
2	4

$2$ $2$ and $3$ $3$ can be placed in two different cells, while $1$ $1$ and $4$ $4$ can only be placed in one.

Sample Input 2

Copy

Sample Output 2

Copy

1
1
1

Explanation for Sample 2

The only valid arrangement is:

Since there is only 1 valid arrangement, each number can only be placed in 1 unique cell.

Sample Input 3

Copy

5 5 1
18

Sample Output 3

Copy

Explanation for Sample 3

The following diagram shows the 11 possible cells $18$ $18$ can be placed in. Green cells denote possible cells, while red cells denote otherwise:

Comments

0

labungloading commented 2 days ago

I'm confused by sample 3 as how can 18 be placed in row 1 column 5? Wouldn't the cell right under it be 10 and since 18 is not less than 10 make the arrangement false?

4

Overseas commented on Dec. 31, 2020, 9:49 a.m. ← edited →

i am certain that python is not being able to handle this, got all the answer correct but always TLE for part 3.

edit; it can, but only with pypy3 or pypy2

0

andrewtam commented on Aug. 14, 2020, 3:57 p.m.

Are all queries distinct?

2

pblpbl commented on Aug. 14, 2020, 4:35 p.m.

Not necessarily.