1660E - Matrix and Shifts - CodeForces Solution

#include<bits/stdc++.h>
     
using namespace std;
     
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <string, string> pss;
typedef vector <int> vi;
typedef vector<bool> vb ;
typedef vector<string> vs ;
typedef vector <vi> vvi;
typedef vector<pii> vpii;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<pll> vpll;
     
const ll INF = 1000000000+7 ;
const ll MOD = 998244353 ;
     
#define all(X) (X).begin(), (X).end()
#define allr(X) (X).rbegin(), (X).rend()
#define sz(X) (int)X.size()
#define setbits(X)(long long) __builtin_popcountll(X)
#define fastio() ios_base::sync_with_stdio(false); cin.tie(NULL);
 
#define fi first
#define se second
#define pb push_back
#define maxxbysec [](const auto& lhs, const auto& rhs) { return lhs.second < rhs.second; }
    
bool sortbysec(const pair<auto,auto> &a,
               const pair<auto,auto> &b){   
    return (a.second < b.second);}   
 
void solve();

vector<bool> is_prime(1e7+1, true);

void sieve(){
   
   is_prime[0] = is_prime[1] = false;
    for (ll i = 2; i <= 1e7 ; i++) {
        if (is_prime[i] && 1ll*i * i <= 1e7) {
            for (ll j = 1ll*i * i; j <= 1e7; j += i)
                is_prime[j] = false;
        }
    }}
ll binpow(ll a, ll b , ll mod = INF) {
 
     if( b == 0 )
         return 1 ;
     
     ll res = 1  , x = a ;
     for( ll i = 0 ; i < 63 ; ++i ){
         if( (1ll<<i) & b )
             res = (res*x) % mod ;
         x = (x*x) % mod ;
     }
     return res ;
 }
ll fact( ll n , ll mod = INF){
    ll res = 1 ;
    for( ll i = 1 ; i <= n ; ++i )
        res = (res*i)%mod ;
    return res ; } 
vll factorization(ll n) {
    vector<long long> factorisation;
    for (long long d = 2; d * d <= n; d++) {
        while (n % d == 0) {
            factorisation.push_back(d);
            n /= d;
        }
    }
    if (n > 1)
        factorisation.push_back(n);
    return factorisation;}
class DisjointSet{
public: 

    vector<ll> parent;
    vector<ll> size;

    void make_set(ll n){
        
        parent.resize(n, 0);
        size.resize(n, 1);
        for(ll i = 0 ; i < n ; i++)
            parent[i]= i;
        
    }

    ll find_set(ll v) {
        if (v == parent[v])      // Path Compression
            return v;
        return parent[v] = find_set(parent[v]);
    }

    void union_sets(ll u, ll v) {
        v = find_set(v);
        u = find_set(u);
        if (v != u) {
            if (size[v] < size[u])
                swap(v, u);
            parent[u] = v;
            size[v] += size[u];
        }
    }

    ll len( ll u ){
        return size[find_set(u)] ;
    }};
    
int main()
{   
    fastio();
    
    long long t=1;
    cin>>t;

    while(t--){
        solve();
    }
    
    return 0;
} 



 
void solve(){  
 
    ll n ;
    cin >> n ;

    vs v(n) ;
    ll ones = 0 ;
    for( ll i =0 ; i < n ; ++i ){
        cin >> v[i] ;
        ones += count( all(v[i]) , '1' ) ;
    }

    ll maxx = 0 ;
    for( ll i = 0 ; i < n ; ++i ){
        ll r = 0 , c = i , lres = 0 ;
        do{
            lres += (v[r][c]-'0') ;
            r = (r+1)%n ;
            c = (c+1)%n ;
            }while( r != 0 ) ;
        maxx = max( maxx , lres ) ;
    }

    cout << ones-maxx + (n-maxx)<<'\n' ;

}