How to solve COVDSMPL (June long challenge problem) optimally

I did, and it would work for n <= 10 easily, possibly for slightly larger n too, but for n=60 even if you’re 99% sure about some values, once in 3600 times it will almost always get something wrong. I didn’t explore it very deeply, maybe I could’ve done something better.

What I did was, I precomputed (using simulations) the following:
prob[rowSum][colSum][0/1] -> probability that sum of all cells in row is rowSum, similarly for columns and frequency of this event with grid[row][col]=0/1. To account for conditional probabilities (as we slowly gain more knowledge about the cells), I adjust this to be:
prob[cellCount][sum][0/1] to define the probability of 0/1 in a cell if there are cellCount unknown rows in it’s row and column in total and their sum is ‘sum’. At best, it was getting about 10 cells wrong in 60x60 matrix on average.

Another thing possible is to see the probability of 0 or 1 in a cell and only if it’s >99% or something declare it as such, otherwise do costly queries to find exact value. I tried this too, but even 99% was not too reliable. My guess is that n=60 was chosen partially to disallow this kind of approach.

1 Like

not me

:+1:

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

5 Likes

Brother, could you post a code? :pleading_face: I’d better do only 1/3 of the correct rate. I want to know more about it

You are a master of optimization.

1 Like

I tried making a probablity matrix, as it goes on passing queries, it adds the probablity += (infected in query)/total_infected.
The problem is when we get a matrix with symmetry along a diagonal, the probablity also reflects in the other diagonal.
I.e
1 0 0 0.67 0 0.67
0 0 0 --> we get probablity matrix as : 0 0 0
0 0 1 0.67 0 0.67

and thus we have to fetch the list of biggest (2*total_infected) probablity matrix entries.
and query them too.

BTW ORZ!
:")

Here’s the code for binary search in rows with large matrix and cost optimizations.

#include <bits/stdc++.h>
using namespace std;
int mat[61][61];
map<pair<pair<int,int>,pair<int,int> >,int>  askedValueStorer;
bool chooseLeft[61];

int response(int r1,int c1,int r2,int c2){
    if(askedValueStorer.find({{r1,c1},{r2,c2}})!=askedValueStorer.end()){
        return askedValueStorer[{{r1,c1},{r2,c2}}];
    }
    cout << "1 " << r1 << ' ' << c1 << ' ' << r2 << ' ' << c2 << '\n';
    int x;
    cin >> x;
    askedValueStorer[{{r1,c1},{r2,c2}}] = x;
    return x;
}
int outputMatrix(){
    cout << 2 << '\n';
    for(int i=1;i<=60;i++){
        for(int j=1;j<=60;j++){
            cout << mat[i][j];
            cout << (j==60 ? '\n' : ' ');
        }
    }
    int x;
    cin >> x;
    return x;
}

int askQuery(int r1,int c1,int r2,int c2,int typeQuery){
    int resp;
    int CountforLeft,CountforRight;
    
    if(typeQuery == 1){
        resp = response(1,c1,r2,c2);
        CountforRight = resp;
    }
    else{
        int a = response(1,c1,60,c2);
        int b = response(r2+1,c1,60,c2);
        resp = a-b;
        askedValueStorer[{{1,c1},{r2,c2}}] = a-b;
        CountforRight = b;
        assert(resp>=0);
    }
    
    if(r2>30 && c1!=1 && chooseLeft[c1]==false){
        CountforLeft = askedValueStorer[{{1,1},{r2,60}}] - CountforRight;
        if(CountforLeft > CountforRight){
            for(int i=c1+1;i<=60;i++){
                chooseLeft[i] = true;
            }
        }
    }
    if(r2>30 && c2!=60 && chooseLeft[c2]==true){
        CountforLeft = CountforRight;
        CountforRight = askedValueStorer[{{1,1},{r2,60}}] - CountforLeft;
        if(CountforLeft < CountforRight){
            for(int i=c2;i>0;i--){
                chooseLeft[i] = false;
            }
        }
    }
    int prevRowsum = 0;
    for(int i=1;i<r1;i++){
        for(int j=c1;j<=c2;j++){
            prevRowsum+=mat[i][j];
        }
    }
    resp -=prevRowsum;
    
    return resp;
}
void fillzeros(int r,int c1,int c2){
    for(int c=c1;c<=c2;c++){
        mat[r][c] = 0;
    }
}
void fillones(int r,int c1,int c2){
    for(int c=c1;c<=c2;c++){
        mat[r][c] = 1;
    }
}

map<pair<int,int>,int> interval_sum;

void bss(int l,int r,int rowsum,int i,int TYPE,bool isSimpleProcess){
    if(l>r)return;
    else if(l==r){
        mat[i][l] = interval_sum[{l,r}];
    }
    else{
        int mid = (l+r)/2;
        int leftQ,rightQ;
        bool chooseit = isSimpleProcess ? (mid > 30) : chooseLeft[mid];
        if(chooseit)leftQ = askQuery(i,1,i,mid,TYPE);
        else leftQ = rowsum - askQuery(i,mid+1,i,60,TYPE);
        int tempsum = 0;
        for(int k=0;k<l;k++){
            assert(mat[i][k]!=-1);
            tempsum+=mat[i][k];
        }
        leftQ-=tempsum;
        rightQ = interval_sum[{l,r}]-leftQ;
        interval_sum[{l,mid}] = leftQ;
        interval_sum[{mid+1,r}] = rightQ;
        
        if(leftQ==0){
            fillzeros(i,l,mid);
        }
        else if(leftQ==(mid-l+1)){
            fillones(i,l,mid);
        }
        else{
            bss(l,mid,rowsum,i,TYPE,isSimpleProcess);
        }
        if(rightQ==0){
            fillzeros(i,mid+1,r);
        }
        else if(rightQ==(r-(mid+1)+1)){
            fillones(i,mid+1,r);
        }
        else{
            bss(mid+1,r,rowsum,i,TYPE,isSimpleProcess);
        }
    }
    
}

void process_4(){
    for(int i=1;i<=60;i++){
        int TYPE = (i>30 ? 1 : 2);
        //cout << TYPE;
        int rowsum = askQuery(i,1,i,60,TYPE);
        //OnesinRow[i] = rowsum;
        for(int j=1;j<=60;j++)chooseLeft[j] = (j<=30) ? false : true;
        if(rowsum==0){
            fillzeros(i,1,60);
        }
        else{
            interval_sum.clear();
            
            interval_sum[{1,60}] = rowsum;
            bss(1,60,rowsum,i,TYPE,false);
        }
    }
}

int main() {
	int t;
	cin >> t;
	while(t--){
	    askedValueStorer.clear();
	    for(int i=1;i<=60;i++){
	        for(int j=1;j<=60;j++){
	            mat[i][j] = -1;
	        }
	    }
	    
	    int n,p;
	    cin >> n >> p;
	    
	    process_4();
	    
	    int res = outputMatrix();
	    if(res==-1)break;
	}
}

Got 77 points in Div 2.

1 Like

it would be so great if you could summarize your summary lol
Nice1 tho

:unamused:

can you send the link to your solution.

Getting a value 350k for 8 cases was very hard to begin with, there were around 30~50 optimizations I did, I mentioned only 4~5 of them which I consider understandable without knowing the entire code…

I had a special rule for interchanging the X and Y axis of the grid but I didn’t mention it because it will be hard to explain why that rule gives a nice result on the average case.

I’ll say I just had a lot of time

1 Like

ah, i see
How many lines of code did you write?

:pray:

In total it was more than 1500 lines, but I kept on rejecting a lot of ideas and solutions, so finally it was around 600 lines I guess…

:exploding_head:
woahh…

can you show your code now as contest has ended , i tried this approach but failed.

This short code may help you.

https://www.codechef.com/viewsolution/34421416

The error of this method should be particularly large? I used a method similar to yours, the worst correct rate is 1/6, and some correct grid is sorted to a very later position.

1 Like