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. 
