Can anyone suggest a solution to SIGNATURE from codechef November cookoff.
It’s simple bruteforce
I’ve written a function shiftcomp, to which i pass the client signature and clients typical signature, and the displacements dr and dc. The function calculates how many cells from the 2 grids don’t match in O(n^2)
Ans = INT_MAX
For r: 1->n
For c: 1->m
Ans = min(ans, Shiftcomp(arr, brr, r, c));
Ans = min(ans, Shiftcomp(arr, brr, -r, c));
Ans = min(ans, Shiftcomp(arr, brr, r, -c));
Ans = min(ans, Shiftcomp(arr, brr, -r, -c));
Cout << ans << endl;
These 4 calls to shiftcomp make sure that i displace the contents of the 2nd grid/matrix to all possible directions for the current values of r and c.
R, c => shifting to bottom right
-r, c=> shifting to top right
R, -c => shifting to bottom left
-r, -c => shifting to top left.
Hope this helps
[Don’t make the same mistake as i did, i initialised ans to 0, which gave answer 0 for all inputs…lol took me too long to find that mistake out]