Header Ad

HackerEarth Cells in a matrix problem solution

In this HackerEarth Cells in a matrix problem solution, You are given an integer N denoting an N x N matrix. Initially, each cell of the matrix is empty. You are given K tasks. In each task, you are given a cell (i,j) where cell (i,j) represents the ith row and jth column of the given matrix.

You have to perform each task sequentially in the given order. Each task is described in cell (i,j). For each task, you have to place X in each cell of row i and each cell column j. After you complete each task, you are required to print the number of empty cells in the matrix.


HackerEarth Cells in a matrix problem solution


HackerEarth Cells in a matrix problem solution.

#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m;
cin>>n>>m;
set<int> row,col;
for(int i=0;i<m;i++)
{
int l,r;
cin>>l>>r;
row.insert(l);
col.insert(r);
cout<<(n-row.size())*1LL*(n-col.size())<<" ";
}
return 0;
}

Second solution

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <iomanip>
#include <fstream>
#include <stack>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll , ll> PLL;
typedef long double ld;

#define pb push_back
#define all(c) c.begin(),c.end()
#define allr(c) c.rbegin(),c.rend()
int mod = 1000000007;
const int inf = 1034567891;
const ll LL_INF = 1234567890123456789ll;
#define PI 3.14159265
#define endl '\n'
#define F first
#define S second
#define debug(x) cout << #x << " = " << x << endl;
#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

#define out(container) for (auto it : container) cout << it << " "; cout << endl;


template < typename T > T GCD(T a, T b) { ll t; while(a) { t = a; a = b % a; b = t; } return b; }
template < typename T > string toString(T a) { return to_string(a); }
template < typename T > void toInt(string s, T &x) { stringstream str(s); str >> x;}
inline int add(int x, int y){ x += y; if(x >= mod) x -= mod; return x;}
inline int sub(int x, int y){ x -= y; if(x < 0) x += mod; return x;}
inline int mul(int x, int y){ return (x * 1ll * y) % mod;}
inline int powr(int a, ll b){
int x = 1 % mod;
while(b){
if(b & 1) x = mul(x, a);
a = mul(a, a);
b >>= 1;
}
return x;
}
inline int inv(int a){ return powr(a, mod - 2);}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);

int n, k;
cin >> n >> k;
ll ans = n * 1ll * n;
vector<bool> row(n + 1, false);
vector<bool> col(n + 1, false);
int r = n, c = n;
while (k--) {
int x, y;
cin >> x >> y;
if (!row[x] && !col[y]) {
ans = ans - c - r + 1;
r--;
c--;
} else if (!row[x] && col[y]) {
ans = ans - c;
r--;
} else if (row[x] && !col[y]) {
ans = ans - r;
c--;
}
cout << ans << " ";
row[x] = col[y] = true;
}
cout << endl;

return 0;
}


Post a Comment

0 Comments