I followed similar approach, got AC and 0.001 points 
2 Likes
And even sorting a matrix requires ‘heapify’-ing things and then finding for k-th max. That is a big NO-NO! 
Sure
https://www.codechef.com/viewsolution/34417627
variable names
rr and rc represents number remaining cells to find out.
rrow and rcol represents number of remaining 1s in that row or colum
rows and cols represents total ones in row or cols
try_it function tries to fill matrix as much as possible
and it should be called after every query whenever remaing 1s == remaing cells or remaing 1s==0
(I am using macro for this)
If you would have split the matrix into 4 parts you would have got 14 pts also you needed to store the queries so that you don’t query the same query again
1 Like
I am storing the query result but I am not spliting part.Thanks for suggestion!!
ufffff
how
Ask 1 1 i j query, then, calculate whether cell is 0 or 1 by a[i][j]-union(a[i][j-1],a[i-1][j]).
Sure, I copied the relevant part here - Covid sampling Codechef - Pastebin.com. Didn’t want to share my submission on a contest since it was super messy long code. Few notes:
I tried to compute the following:
prob(grid[r][c] = 0 | rowSum[r]=x, colSum[c]=y) and prob(grid[r][c] = 1 | rowSum[r]=x, colSum[c]=y).
In other words, for a given cell [r][c], what’s the probability that value is 0/1 if we know the sum of
all cells in its row and in its column.
In the code, array fr[][][] counts this:
fr[x][y][z] means that for some cell the row sum is x, column sum is y, and z is in {0,1}. Note that fr[][][] computes the count, not the probability itself. To get probability of 0 for a row sum x and column sum y, you could compute: fr[x][y][0] / (fr[x][y][0] + fr[x][y][1]).
Even though there are deterministic ways to compute f[x][y][z] values, I was lazy and wrote a simulation instead. Basically I repeatedly generate random grids and for each cell (r, c) do the following: count sum in row r, say X; count sum in column c, say Y. If (r,c) = 0 in the current grid,
we do f[X][Y][0]++, or else f[X][Y][1]++.
There is another array (condFreq), which tries to take into account the partial knowledge of other cell values in current row and column. Precisely, for (x,y,z) it computes probability of a cell being equal to z (z=0/1), when we don’t know Y values in it’s row and column in total, and the sum of them is equal to X. This is supposed to be more accurate than the previous one, but in my experience neither of them were useful to get acceptable solution (guess all 3600 squares).
Hope this helps 
Blockquote
1 Like
Doesn’t binary search need a monotonic space ? Also did you get AC ? Please do post the solution.
Here’s the solution.
https://www.codechef.com/viewsolution/33819068
My basic idea was since the more no. of rows/cols we query the lesser cost is, and since probability is pretty low, the matrix should be sparse. It didn’t give a great solution but I’m glad I was atleast able to do it.
Use your method，I asked about half of the squares, predicted the other half, and predicted that half was all zeros. 
Those submissions have been submitted after the contest. That’s why it is written 0pts. But the submissions before the screenshot got 1pts (i.e. a mark of 100 in the scoreboard).
Oh, thanks! Actually I am new so I didn’t know that!
I did the same thing. For some weird reason, I found binary search was applicable to the last three problems of div2
Could you please elaborate a little more on “binary search the exact positions of 1s in the row”
How does the search work?
Let’s say I have a way to find the prefix sum of the row r upto the k-th column. Let’s call this function pfrow(r,k).
Now let’s say there are 2 ones in the row. First I’ll Binary Search for minimum k such that pfrow(r,k)=1, this place has a 1. Next I’ll do the same for pfrow(r,k)=2, this is the position of another 1.
I precalculated the total number of 1s in the blocks so I can choose the columns in which I have to Binary Search.
1 Like
Got it, thanks a lot for sharing 