Chef and Matrix Division
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef has n × n array A of non-negative integers. He wants to divide this array by p-1 horizontal dividers and p-1 vertical dividers into p2 blocks such that maximum sum of elements of each block will be the smallest.
More formally, Chef want to choose p-1 horizontal dividers 0 = h0 < h1 < ... < hp = n and p-1 vertical dividers 0 = v0 < v1 < ... < vp = n to minimize the next value:
- The first line of each test file contains two space-separated integers n and p denoting the size of array A and the number of horizontal and vertical dividers.
- Each of next n lines contains n space-separated integers Ai, 1, Ai, 2, ..., Ai, n denoting the ith row of the array A.
Your score for each test case will be calculated by formula described above. Your goal is to minimize this score.
Your total score for the problem will be the sum of scores on all the test cases.
Your solution will be tested only on 20% of the test files during the contest and will be rejudged against 100% after the end of competition.
- 2 ≤ p ≤ n ≤ 500
- 1 ≤ Ai, j ≤ 109
Input: 4 3 1 1 2 2 2 1 2 2 3 1 4 2 4 4 2 2 Output: 2 3 1 3
As you can see at the picture below, this array is divided into p2 = 9 blocks by p-1 horizontal(red lines) and p-1 vertical(green lines) dividers. Also there are two vertical (v0 = 0 and v3 = 4) dividers and two horizontal (h0 = 0 and h3 = 4) for better understanding of this division.
Your score for this test case will be 6 / (4 / 3)2 (there are two blocks with sum of elements 6).
This test case won't be in the test data because n ∉ [450..500]. It just for let you understand how scoring works. Also there are another ways to divide this array into 9 parts. All of them will be accepted, but with different scores.
Test data generation
There will be 20 test files.
For each test file the number n is chosen from the range [450..500] with equal probability. All elements of A are also chosen randomly. For each test case p will be manually selected.
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.