Please create more balanced div2. First 3 questions were too easy and the rest were too hard. There is no middle ground.
3 Likes
+1
+1
I would sincerely urge everyone, who couldn’t solve the 4th question in the Div-2 round. Please try to implement basic Brute-force solution, and try to figure out, what are you doing wrong in the logic.
signed main() {
int k = 12;
long long n = (1LL << 16) - 1;
int grid[4][4];
int minXorVal = 50;
long long minXorValFor = -1;
// int k = 4; // Set the desired number of set bits
repl(i, 0, n) {
// count number of set bits in i;
if(__builtin_popcount(i) == k) {
rep(j, 16) {
if(i & (1LL << j)) {
grid[j/4][j%4] = 1;
} else {
grid[j/4][j%4] = 0;
}
}
// xor of all the rows + columns
int rowXor = 0;
int colXor = 0;
rep(j, 4) {
int rowVal = 0;
int colVal = 0;
rep(l, 4) {
rowVal ^= grid[j][l];
colVal ^= grid[l][j];
}
rowXor += rowVal;
colXor += colVal;
}
if(minXorVal > rowXor + colXor) {
minXorVal = rowXor + colXor;
minXorValFor = i;
}
}
}
// print the min xor value and the value for the grid also.
cout << "Min XOR value: " << minXorVal << endl;
rep(j, 16) {
if(minXorValFor & (1LL << j)) {
grid[j/4][j%4] = 1;
} else {
grid[j/4][j%4] = 0;
}
}
// print grid
rep(i, 4) {
rep(j, 4) {
cout << grid[i][j] << " ";
}
// new line
}
If you had simply implemented this piece of code, as bruteforce, and try to find optimal arrangement of k 1’s, You would have easily made observation.
1 Like
That’s a great insight. It took me a 1hr+ to rectify my mistake.
I don’t think 4th(SXMR) is hard. It’s just tricky. (though it took me a long time to recognize)
Even the 5th(LENGTHX) can be implemented easily with set and dp (just had an idea, didn’t try)
thats a really good idea. Didnt think in that direction during the contest.