Grid Board
Time limit1sMemory limit128 MB
Choose K rows and columns to delete from a grid so the maximum value among the remaining cells is minimized, then output the selected rows and columns.
- Level
Medium7 of 10
- Topics
- Binary search, Greedy
- Solved
- No attempts yet
Problem
A grid has N rows and M columns, and each cell contains one positive integer. An integer K is given. K is at least 2, less than N, and less than M.
Choose R rows and C columns so that R + C = K. After removing every cell that belongs to a chosen row or a chosen column, consider the largest number among the remaining cells. Your goal is to make that largest number as small as possible.
Suppose N = 4 and M = 5, and the grid is as follows.
When K = 3, choosing rows 1 and 3 and column 4 leaves 5 as the largest number among the remaining cells.
Choosing row 3 and columns 3 and 4 also leaves 5 as the largest remaining number. However, no choice of rows and columns can make every remaining number smaller than 5.
Given the grid and the total number K of rows and columns to choose, write a program that minimizes the largest number among the cells not removed by the chosen rows and columns.
Input
The first line contains two integers N and M, the size of the grid. N and M are each between 3 and 300, inclusive.
The second line contains K, the total number of rows and columns to choose. K is less than N and less than M.
The next N lines describe the grid from row 1 to row N. Each line contains M positive integers separated by spaces. Every number in the grid is between 1 and 500,000, inclusive.
Output
On the first line, print the minimum possible value of the largest number among the cells that remain after choosing R rows and C columns with R + C = K.
On the second line, print R followed by the selected row numbers in increasing order. On the third line, print C followed by the selected column numbers in increasing order. If no row or no column is selected, print only 0 on that line.
Separate integers on the same line with one space. If there are multiple valid answers, print any one of them.