COVDSMPL - Editorial

PROBLEM LINK:

Contest

Setter: Taranpreet Singh
Tester: Felipe Mota
Editorialist: Solutions collated from different contestants.

DIFFICULTY:

Challenge

PREREQUISITE:

No Intended Solution

PROBLEM:

You are given the task of finding people infected with COVID-19 among the whole population. There are a total of N^2 people and they are standing in a N \times N matrix, one person per cell.

Formally, for each i (1 \le i \le N) and j (1 \le j \le N), let’s denote A_{i, j} = 1 if the person standing in the i-th row and j-th column of the matrix is infected or A_{i, j} = 0 otherwise. Additionally, it is known that the infection spreads randomly at first and does not spread anymore ― that is, each person was initially infected with a probability P/100, independently from all other people. You do not know the values of A_{i, j} and your task is to find these values.

You may ask up to Q queries (Q is specified in the Constraints section below). In each query, you should choose a submatrix containing all people in rows r_1 through r_2 and columns c_1 through c_2 inclusive; the grader responds with the number of infected people in the queried submatrix.

Each query has a cost; see the section Scoring for this cost. You should find out exactly which people are infected and the sum of costs of all queries you make should be as small as possible.

CONTESTANT SOLUTIONS:

I Have collated solutions posted by top scorers here. Hopefully you will get many ideas here.

Solution by iamsv345. Score: 44

first query for whole matrix get total 1s
now find rows and colms in following way.
query for row 2 to n and colms 1 to n subtract from tot got row1( add it to sum )
query for row 3 to n and colms 1 to n row2=total-query-sum (add row 2 to sum)
repet untill n/2 and for remaning n/2 start from reverse (n to n/2)

same for colms.

try to fill matrix as much as you can
if row[i]=0 fill whole row with 0 or row[i]=remaining in row[i] fill whole with 1s

Last step.

start from left corner in following way
you can get sum of all rows under element by summing all rows found earlier same for colms right to element
and can also get sum of processed part(as we started from left corner) by adding all ones from 1 to i and 1 to j
then query for common green box (i+1 to n and j+1 to n) as shown in figure and ans
is a[i][j]=tot-sum(rows,i+1,n)-sum(cols,j+1,n)-ones in matrix (1 to i)row and (1 to j) cols) +query for common part.

Solution by sapfire. Score: 72

Okay, ~70 pt (div. 1) solution here:

In basic terms, I’m simply recursively traversing the entire matrix. If the current submatrix has only 0’s or only 1’s, I exit the current iteration. Else I split into two halves and go deeper.

However without optimizations this gets < 1 pt.

Several possible ways to make this cost less:

  1. As @kk2_agnihotri correctly pointed out, bigger matrices cost less, so when I receive an order to query a certain submatrix, I try several ways to find the sum in it through other sums. For example, by doing a prefix-sum-like (or suffix-sum-like) technique. I also try calculating the entire horizontal strip, extended down (or up) and then simply subtract the extra elements. Same with vertical strips. I calculate the expected cost of each of these options and simply choose the cheapest.

  2. It is possible to keep already calculated queries in a map so as not to do unnecessary work. I set the expected value for such a query (that has already been asked before) as 0, however in earlier versions I used numbers all the way down to -200 (well, I was kinda experimenting with constants as well).

  3. Expanding on the idea in (1), we can make the following improvement. Say we have a submatrix whose sum we are about to ask the judge. We notice that if the horizontal strip right above it is already calculated, we can add it to the submatrix and simply subtract the sum from the final answer. The cost of the query will thus only decrease. Same with the horizontal strip below and the two vertical strips to either side.

  4. Another, but as far as I can remember, insignificant improvement. If the submatrix about to be sent to the judge can be split into two submatrices with already calculated sums, we can return the sum of the two sums and avoid asking anything altogether.

In the earlier submissions I had been also trying to calibrate various constants (which worked btw!), but in the highest-scored submission there is absolutely no calibration (actually that only worsens the performance, lol…)

I’ve looked at several other top-scoring submissions. Their authors use Fenwick tree to calculate sums. I just did brute-force, I didn’t really need any fast algorithms, and most of my submissions actually had a runtime of 0.00 (before the part when I included point 4)

Hope I explained this more or less clear, and yes, the thought process was not linear, I came to those ideas in a week in total, so it wasn’t like I suddenly thought of something and got 70 points. I was rather close to the upper limit of submissions btw :slight_smile:

Solution by loop_free. Score: 79

My method is to preprocess the sum of each column and then ask each row in half. If this sum is 0 or the sum is the area, then you can directly fill in the number.

Note that each time you ask about a rectangle, choose a large rectangle with one of the four corners as its vertex to ask about it, and should reasonably use the previous inquiry results to infer.

In this way, about 60 points can be reached.

Solution by Demoralizer. Score: 91

I had the 2nd or 3rd highest score in division 1.
Here’s what I did.
First calculate total number of 1s in each row and each column, now ignore the rows and columns with all 0s.

Then I’ll binary search in each row to find the exact position of the 1s. Also, I’ll keep subtracting the found elements from the corresponding columns.

I also maintain the prefix_sum of the part of the grid I’ve already found. It helps me get elements of next row by querying larger rectangles and subtracting the found prefix_sum.

This solution was around 80 points.

To improve further, I divided the grid into 6X1 blocks. 600 blocks in total.
Used the same binary search approach to get the values in each block.

On an average there would be around 0 to 3 positives in each block and a lot of blocks would be empty.

Now once this precomputation is done, binary search again to exact cells while being aware of the blocks and rows and columns.

Apart from this I also used a lot of micro-optimizations, some of them are:-

If the upper half has more elements than lower half then invert the grid upside down.

Store all queries in a map to avoid redundancy.

While querying if the row or column just outside your query rectangle is empty, include it in your query as it won’t change the answer

If the possible candidates in a row are less than half of the total positives in the row, then the search space is too congested, now it is better to Binary search to find the 0s instead of 1s.

And some other micro optimizations.

I had one more significant optimization but I couldn’t implement it before the time ran out.