FILLGRID - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Utkarsh Gupta
Tester: Samarth Gupta
Editorialist: Taranpreet Singh

DIFFICULTY

Simple

PREREQUISITES

None

PROBLEM

Given a N \times N grid, fill the grid with -1 and 1 such that following conditions are met:

  • For every column - (Sum of values present in the column) \times (Product of values present in the column) \lt 0
  • For every row - (Sum of values present in the row) \times (Product of values present in the row) \lt 0

QUICK EXPLANATION

  • For even N, filling the whole grid with -1 satisfies all the conditions.
  • For odd N, filling the main diagonal with 1 and the rest of the grid with -1 satisfies the conditions.

EXPLANATION

Since this is a constructive problem, there may exist multiple solutions. Feel free to share yours in the comments.

Since we want the sum of elements \times product of values to be negative for all rows and columns, one tempting idea would be to fill the whole matrix with -1. Let’s see what happens in this case.

  • For even N, the product of each row and column is 1, and the sum of each row and column is -N, so we get the sum \times product to be -N for each row and column. This satisfies all the conditions.
  • For odd N, the product of each row and column is -1, and the sum of each row and column is -N, so we get the sum \times product to be N for each row and column. This doesn’t satisfy all the conditions.

So, for odd N, we have to use 1 somewhere. Changing the value of one cell changes the sum of the row to be -(N-2) and product of row to 1, hence sum \times product becomes -(N-2). Since N \geq 2, smallest odd N is N = 3, hence -N+2 is always a negative value for given constraints.

Hence, for each row, it is sufficient to replace one value with 1. We need to do that for columns as well. We also need to make sure that no two chosen cells share a row or column, otherwise, the product of that row or column would become -1 again.

One neat way of doing this is to flip the value from -1 to 1 for all cells in the main diagonal. All rows and columns get covered, with no row or column having more than one flipped cell.

For example, for N = 5, the grid looks like

 1 -1 -1 -1 -1
-1  1 -1 -1 -1
-1 -1  1 -1 -1
-1 -1 -1  1 -1
-1 -1 -1 -1  1

The Sum of each row and column is -N+2 and the product of each row and column is 1.

TIME COMPLEXITY

The time complexity is O(N^2) per test case since we need to print output of size N^2.

SOLUTIONS

Setter's Solution
//Utkarsh.25dec
#include <bits/stdc++.h>
#include <chrono>
#include <random>
#define ll long long int
#define ull unsigned long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define rep(i,n) for(ll i=0;i<n;i++)
#define loop(i,a,b) for(ll i=a;i<=b;i++)
#define vi vector <int>
#define vs vector <string>
#define vc vector <char>
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define deb(x) cerr<<#x<<' '<<'='<<' '<<x<<'\n'
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// ordered_set s ; s.order_of_key(val)  no. of elements strictly less than val
// s.find_by_order(i)  itertor to ith element (0 indexed)
typedef vector<vector<ll>> matrix;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
vector <int> adj[N];
void solve()
{
    ll n;
    cin>>n;
    if(n==2)
    {
        cout<<-1<<' '<<-1<<'\n'<<-1<<' '<<-1<<'\n';
        return;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==j)
                cout<<-1<<' ';
            else
                cout<<1<<' ';
        }
        cout<<'\n';
    }
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int T=1;
    cin>>T;
    int t=0;
    while(t++<T)
    {
        //cout<<"Case #"<<t<<":"<<' ';
        solve();
        //cout<<'\n';
    }
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;

long long readInt(long long l, long long r, char endd) {
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true) {
        char g=getchar();
        if(g=='-') {
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g&&g<='9') {
            x*=10;
            x+=g-'0';
            if(cnt==0) {
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);
 
            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd) {
            if(is_neg) {
                x=-x;
            }
            assert(l<=x&&x<=r);
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l, int r, char endd) {
    string ret="";
    int cnt=0;
    while(true) {
        char g=getchar();
        assert(g!=-1);
        if(g==endd) {
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt&&cnt<=r);
    return ret;
}
long long readIntSp(long long l, long long r) {
    return readInt(l,r,' ');
}
long long readIntLn(long long l, long long r) {
    return readInt(l,r,'\n');
}
string readStringLn(int l, int r) {
    return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
    return readString(l,r,' ');
}
 
void readEOF(){
    assert(getchar()==EOF);
}

int main() {
    // your code goes here
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    int sum = 0;
    while(t--){
        int n;
        cin >> n;
        if(n%2 == 0){
            for(int i = 0; i < n ; i++){
                for(int j = 0; j < n ; j++)
                    cout << -1 << " ";
                cout << '\n';
            }
        }
        else{
            for(int i = 0; i < n ; i++){
                for(int j = 0; j < n ; j++){
                    if(i == j)
                        cout << 1 << " ";
                    else
                        cout << -1 << " ";
                }
                cout << '\n';
            }
        }
    }
    readEOF();
    return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class FILLGRID{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int N = ni();
        int[][] grid = new int[N][N];
        for(int i = 0; i< N; i++)
            for(int j = 0; j< N; j++)
                if(i == j && N%2 == 1)grid[i][j] = 1;
                else grid[i][j] = -1;
        for(int[] row:grid){
            for(int element:row)p(element+" ");pn("");
        }
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    static boolean multipleTC = true;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        new FILLGRID().run();
    }
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

Here’s my approach

#include<bits/stdc++.h> 
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
const unsigned int M = 1000000007;
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> tree;
void solve()
{
    int t, n;
    cin>>t;
    while(t--){
        cin>>n;
        vector<vector<int>> data(n+1,vector<int>(n+1,-1));
        if(n%2 != 0){
            for(int i = 1; i <= n ;i ++ )
            data[i][i] = 1;
        }
        for(int i = 1; i <= n ;i ++){
            for(int j = 1; j <= n ; j ++)
            cout<<data[i][j]<<" ";
            cout<<"\n";
        }

    }
}
int main()
{
ios_base::sync_with_stdio(false);
cout.tie(NULL);
cin.tie(NULL);
solve();
return 0;
}
1 Like

It is same as filling the main diagonal with -1 and rest with 1 for odd n greater than equal to 3. Sum of elements in a row or a column would be n-2 and product would be -1 , giving sum*product equal to -(n-2).

Maybe the easiest way to solve,

if n is even, say 4

  • make a matrix of all -1s.

-1 -1 -1 -1
-1 -1 -1 -1
-1 -1 -1 -1
-1 -1 -1 -1
Here the product is always positive due to even number of -1s, and the sum always negative due to the absence of 1.

if n is odd, say 5
-fill up the principal diagonal with -1, and the rest with 1
-1 1 1 1 1
1 -1 1 1 1
1 1 -1 1 1
1 1 1 -1 1
1 1 1 1 -1
Now , for every column and row the sum will be positive,due to more 1s and less -1s, and the product negative , as there is a single -1 in every row /column.

Link to my soln:
Has O(n3) complexity but works out well :laughing:
https://www.codechef.com/viewsolution/51141071

1 Like

int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t–)
{
int n;
cin>>n;

    if(n&1)
    {
        for(int i=0;i<n;i++)               //odd
        {
            for(int j=0;j<n;j++)
            {
                if(i==j)
                cout<<-1<<" ";
                else
                cout<<1<<" ";
            }
            cout<<"\n";
        }
    }
    else
    {
        for(int i=0;i<n;i++)                //even
        {
            for(int j=0;j<n;j++)
            {
                
                cout<<-1<<" ";
            }
            cout<<"\n";
        }
    }
    


} 

return 0;

}

//My approach to this problem
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long
#define vt vector<ll>
#define vvt vector<vt>
#define vvvt vector<vvt>
#define all(c) (c).begin(), (c).end()
#define rep(i, start, end) for(ll i=start; i<=end; i++)
#define sd(n) scanf("%lld",&n)
#define eps 1e-3
const ll mod=1e9+7;
const ll max=1e5+5;
ll add(ll x,ll y ){ll res=x+y;return (res>=mod?res-mod:res);}
ll sub(ll x,ll y ){ll res=x-y;return (res<=0?res+mod:res);}
ll binpow(long long a, long long b) {a %= mod;long long res = 1;while (b > 0) {if (b & 1)res = res * a % mod;a = a * a % mod;b >>= 1;}return res;}
ll mul(ll x,ll y){ll res=x*y;return(res>=mod?res%mod:res);}
ll inv(ll x){return binpow(x,mod-2);}
template<class T>void print(T &a){for(auto val: a)cout << val << " ";cout << "\n";}
template<class T>ll size(T &a){return a.size();}
template<class T>void read(vector<T> &a){for(ll i=0;i<size(a);i++)cin>>a[i];}
int ceil2(int a, int b) { if (a == 0) return 0;return (a - 1)/b + 1;}
//long long modalt(int x,int n,int m){ if (n==0) return 1; if(n%2==0){ long long y=mod(x,n/2,)%m; return (y*y)%m;}else return ((mod(x,n-1,m)%m) *(x%m))%m;}
#define lim 400009
void solve(){
   int n;
   cin>>n;
   vvt mt(n,vt(n,-1));
   if(n%2!=0){
       for(int i=0;i<n;i++){
        mt[i][i]=1;
       }
   }
    for(auto j:mt){
       for(auto k:j){
            cout<<k<<" ";
           }
           cout<<endl;
       }
   }
int main(){
	int t;
	cin>>t;
	while(t--){
		solve();
	}
return 0;
}

* List item

Just clarifying that it has O(n^2) complexity only, not O(n^3).

1 Like

Solution: 51163372 | CodeChef
Why this is giving TLE ?