Repovive
  • Dashboard
  • Ranking
  • Submissions
  • Discussion
  1. Contests
  2. Weekly Challenge 1: Approximation
  3. W1D2B

My submissions

/
/
/
/

Announcements

My submissions

/
/
/
/

Announcements

Solve
Author

W1D2B. 2D Banner

2 pts·1s·256 MB

Constraints

Input

Output

Samples

Input
t
1
Case 1
8 10
3 4 2 5 1 4 3 2 5 1
2 5 20 20 20 20 20 3 4 2
4 1 20 20 20 20 20 5 2 3
5 3 20 20 20 20 20 4 1 5
1 2 20 20 20 20 20 3 5 4
4 5 2 1 3 5 2 4 3 1
2 3 5 4 1 2 5 3 4 2
5 1 4 3 2 1 4 5 2 3
Explanation
Output
2 3 4 7

You are given a grid with nnn rows and mmm columns. The cell in row iii and column jjj has height ai,ja_{i,j}ai,j​.

You want to place a rectangular banner on the grid. A banner is determined by four integers r1,c1,r2,c2r_1, c_1, r_2, c_2r1​,c1​,r2​,c2​ such that 1≤r1≤r2≤n1 \le r_1 \le r_2 \le n1≤r1​≤r2​≤n and 1≤c1≤c2≤m1 \le c_1 \le c_2 \le m1≤c1​≤c2​≤m.

The score of this banner is:

min⁡(ai,j)×(r2−r1+1)×(c2−c1+1)\min(a_{i,j}) \times (r_2-r_1+1) \times (c_2-c_1+1)min(ai,j​)×(r2​−r1​+1)×(c2​−c1​+1)

where the minimum is taken over all cells (i,j)(i,j)(i,j) satisfying r1≤i≤r2r_1 \le i \le r_2r1​≤i≤r2​ and c1≤j≤c2c_1 \le j \le c_2c1​≤j≤c2​.

Let OPTOPTOPT be the maximum possible score of a banner.

You do not need to find an optimal banner. You only need to output any banner whose score is at least half of OPTOPTOPT.

In other words, if the score of your banner is SSS, your output is accepted if 2×S≥OPT2 \times S \ge OPT2×S≥OPT.

  • 1≤t≤51 \le t \le 51≤t≤5
  • 1≤n,m≤8001 \le n,m \le 8001≤n,m≤800
  • The sum of n×mn \times mn×m over all test cases is at most 500000500000500000
  • 1≤ai,j≤1061 \le a_{i,j} \le 10^61≤ai,j​≤106
ttt nma1,1a1,2⋯a1,ma2,1a2,2⋯a2,m⋮an,1an,2⋯an,m}×t\left. \begin{array}{l} n \quad m \\ a_{1,1} \quad a_{1,2} \quad \cdots \quad a_{1,m} \\ a_{2,1} \quad a_{2,2} \quad \cdots \quad a_{2,m} \\ \vdots \\ a_{n,1} \quad a_{n,2} \quad \cdots \quad a_{n,m} \end{array} \right\} \times tnma1,1​a1,2​⋯a1,m​a2,1​a2,2​⋯a2,m​⋮an,1​an,2​⋯an,m​​⎭⎬⎫​×t

For each test case, output four integers r1,c1,r2,c2r_1, c_1, r_2, c_2r1​,c1​,r2​,c2​, describing the banner you choose.

The output must satisfy 1≤r1≤r2≤n1 \le r_1 \le r_2 \le n1≤r1​≤r2​≤n and 1≤c1≤c2≤m1 \le c_1 \le c_2 \le m1≤c1​≤c2​≤m.

If the score of your banner is SSS, it must satisfy 2×S≥OPT2 \times S \ge OPT2×S≥OPT.

The output format is:

r1c1r2c2}×t\left. \begin{array}{l} r_1 \quad c_1 \quad r_2 \quad c_2 \end{array} \right\} \times tr1​c1​r2​c2​​}×t

The chosen banner covers rows 222 to 444 and columns 333 to 777.

All cells inside it have height 202020, and its area is 3×5=153 \times 5 = 153×5=15, so its score is 20×15=30020 \times 15 = 30020×15=300.

The rectangle from row 222 to row 555 and column 333 to column 777 has score 20×20=40020 \times 20 = 40020×20=400, so the shown output is not optimal. Still, a score of 300300300 is enough because it is at least half of the optimal score.