PROBLEM LINK:
Setter: Erfan Alimohammadi
Tester: Teja Vardhan Reddy
Editorialist: Teja Vardhan Reddy
DIFFICULTY:
PREREQUISITES:
Simulation.
PROBLEM:
Given a r*c grid in which there are ants moving. Each ant moves in either up,down,left or right represented U,D,L,R respectively.Whenever an ant crosses border of the grid, it disappears. There are some anteaters on the grid represented by \# which do not move. whenever an ant enters the cell in which anteater is represent, it disappears. We want to find number of pairs of ants that meet each other.
EXPLANATION
Any ant can be on the grid for atmost max(r,c) time. It either crosses border in that time or is met by an anteater.
So any meeting of two ants must happen before max(r,c) + 1 units of time from start.
So we will try to simulate positions of ants on the grid for max(r,c) time. And find after simulating each unit of time, how many pairs of ants meet in that second.
Let us store a vector in each cell of the grid representing directions in which ants present in that cell are moving at that time moment.
To count pairs of ants meeting in that moment, we iterate over all cells in the grid. And if in a grid there are n ants, then C(n,2) = n*(n-1)/2 pairs of ants meet in that cell in that moment.
For simulating one second, we will move all the ants moving left to one position left (i.e an ant at (i,j) moves to (i,j-1)) and similarly other directions.After moving , we check that if there is an anteater in that cell or ant crosses border then we remove it from the vector corresponding to that moved cell.
Am implementation detail, to simulate, we cannot do it inplace. We need to copy into another vector and do because we dont want to move an ant two times in a time step.
TIME COMPLEXITY
Complexity of counting pairs at a time moment takes O(r*c) time. Total complexity for counting pairs= O(max(r,c)*r*c).
Complexity of simulating one unit of time = O(r*c + count of ants initially).Since, intially each cell contained atmost one ant, count of ants initially \leq r*c. Hence, simulating for max(r,c) timesteps take O(max(r,c)*r*c).
Hence, total time complexity is O(max(r,c)*r*c).
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 310;
int t, r, c;
vector<char> grid[2][MAXN][MAXN];
bool antEater[MAXN][MAXN];
long long ans;
pair<int, int> charToDir(char ch) {
if (ch == 'R')
return {0, 1};
if (ch == 'L')
return {0, -1};
if (ch == 'U')
return {-1, 0};
if (ch == 'D')
return {1, 0};
return {0, 0};
}
pair<int, int> newPosition(int x, int y, char ch) {
pair<int, int> dir = charToDir(ch);
return {x + dir.first, y + dir.second};
}
bool isInside(int x, int y) {
return (x >= 1) && (x <= r) && (y >= 1) && (y <= c);
}
bool isInside(pair<int, int> pos) {
return isInside(pos.first, pos.second);
}
void updateGrid(int it) {
it &= 1;
int nextIt = (it ^ 1);
for (int i = 1; i <= r; i++)
for (int j = 1; j <= c; j++) {
for (char ch: grid[it][i][j]) {
pair<int, int> newPos = newPosition(i, j, ch);
if (isInside(newPos) && !antEater[newPos.first][newPos.second])
grid[nextIt][newPos.first][newPos.second].push_back(ch);
}
grid[it][i][j].clear();
}
}
void countPairs(int it) {
it &= 1;
for (int i = 1; i <= r; i++)
for (int j = 1; j <= c; j++) {
long long sz = grid[it][i][j].size();
ans += sz * (sz - 1) / 2;
}
}
int main() {
cin >> t;
while (t--) {
cin >> r >> c;
ans = 0;
for (int i = 1; i <= r; i++)
for (int j = 1; j <= c; j++) {
char ch;
cin >> ch;
if (ch != '-' && ch != '#')
grid[0][i][j].push_back(ch);
antEater[i][j] = (ch == '#');
}
for (int i = 0; i < max(r, c); i++) {
updateGrid(i);
countPairs(i + 1);
}
cout << ans << endl;
for (int i = 1; i <= r; i++)
for (int j = 1; j <= c; j++) {
grid[0][i][j].clear();
grid[1][i][j].clear();
antEater[i][j] = false;
}
}
return 0;
}
Tester's Solution
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout)
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// find_by_order() // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
int d1[4]={0,0,-1,1};
int d2[4]={-1,1,0,0};
int arr[312][312][4],arr1[312][312][4];
string str[312];
int main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
while(t--){
int r,c;
cin>>r>>c;
int i,j,k;
f(i,1,r+1){
f(j,1,c+1){
rep(k,4){
arr[i][j][k]=0;
arr1[i][j][k]=0;
}
}
}
f(i,1,r+1){
cin>>str[i];
f(j,1,c+1){
if(str[i][j-1]=='L'){
arr[i][j][0]++;
}
else if(str[i][j-1]=='R'){
arr[i][j][1]++;
}
else if(str[i][j-1]=='U'){
arr[i][j][2]++;
}
else if(str[i][j-1]=='D'){
arr[i][j][3]++;
}
}
}
int it,tim=max(r,c)+3;
int ans;
ll tot=0;
rep(it,tim){
f(i,1,r+1){
f(j,1,c+1){
ans=0;
rep(k,4){
if(str[i][j-1]=='#'){
arr[i][j][k]=0;
}
if(arr[i][j][k]==0)
continue;
// if(it==1){
// cout<<i<<" "<<j<<" "<<k<<endl;
// }
ans+=arr[i][j][k];
arr1[i+d1[k]][j+d2[k]][k]+=arr[i][j][k];
}
// if(ans>=2){
// cout<<i<<" "<<j<<endl;
// }
tot+=ans*(ans-1)/2;
}
}
f(i,1,r+1){
f(j,1,c+1){
rep(k,4){
arr[i][j][k]=arr1[i][j][k];
arr1[i][j][k]=0;
}
}
}
}
cout<<tot<<endl;
}
return 0;
}
Feel free to Share your approach, If it differs. Suggestions are always welcomed.