ANTEATER - EDITORIAL

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

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. :slight_smile:

5 Likes

The editorial mentions in the end that maintaining a duplicate array is necessary ; and we need to implement idea outplace… And if I am correct ; that is why arr1 is maintained…

Also I can see ( In tester solution ) that the original input is maintained to check the the occurances of ‘#’ symbols ( Ant-Eater positions )…

However ; I solved it ------->>
1 : without that extra array ( Without extra arr1 )
2 : without that extra 3rd dimension ( by using bitmasking )
3 : without retaining the input strings…

if any-one is interested ; can look at the submission - https://www.codechef.com/viewsolution/24931959

And If I went wrong somewhere ; or any-one if finds any way so that I can improve my implementation ; please suggest…!!!

Hope this helps…

is it correct that n ant are present in a grid or in a cell at any movement to count pairs…
in my point of view there are n ant present in any cell at any movement… plz correct if i’m wrong…

yeah… n ants should be present in a cell

Can u please explain your approach. I used an extra array to keep track of the ants.

Hey I have tried some other approach without keeping track of the ants
please checkit out
solution

I don’t know how efficient it is, but I guess, it was one of the simplest implementation.
For row 1 to r
For col 1 to c
If S[row][col]==‘R’
// Collision with U, we check on diagonal path only
r_init=row+1;
c_init=col+1;
if S[r_init][c_init]==‘U’ and S[row][col_init]!=’#’
//Check for straight line paths if there isn’t any ‘#’ on the path
And score ++;

It will be more or less copy paste of this part for different kind of meets .

1 Like

that is what i have used

Now the idea of the extra array is brought up just to avoid two ants standing at the same position at the same time right…?

Now my approach is related to a real life observation…

Imagine this - You have gone to a movie theater and standing in a queue of ‘n’ people who want to buy movie tickets… All the people standing in the queue have a tendency to move in only one direction - FORWARD so that they can get the ticket as soon as possible…

Does it happen that two people in the same queue stand at same position at the same point of time…?

Answer is NO.

Why ?

Because the queue has tendency only to move forward… now it never happens that the last person moves one step forward first ( In that case the last and second last person would be standing on the same spot )…

Rather what happens is that the first member of the queue moves forward ( Buys ticket and moves out of queue ) ; And in moving forward , he empties a space ( Where he was originally standing )… and that space is occupied by the second person…

And when the second person moves forward to take place where originally first person was standing ; he empties one more space ; which can now be occupied by the 3rd person and so on…

Now what can we learn from this…?

Take one direction at a time. Let say we only focus on direction UP ( Ignore left , right and down moving ants )

The ants moving up will be moving in the same column ( So ignore all other columns and try to understand with one column and one direction - UP )

If we allow the topmost ant to move first ; then 2nd and then 3rd ( And all ants are moving with same speed - only one step or position at a time ) ; then at no instant two of them will be on the same spot… ( Since all of them are moving up )

Similarly for ants in the same row moving in direction - LEFT… If we allow the left-most ant to move first ; then also when the second ant moves ; it cannot overlap the first one and similar is true for all ants.

So all you need to do is allow all movements but make them move wisely…

How does my code handle that ------>>
Look at the function update_changes at line 99. You will see 4 set of loops. Each of them is for handing one movement direction at a time…

Let me explain you the first set of for loop from line 101-105 ( Rest are similar )

The change function has five parameters. It represent that ant wants to go to position (i,j) from (i,j-1). Noticing the change in co-ordinates , you should understand that the ants want to move to right.

So this is the loop that will be handing all ants on the grid wanting to move right…

And since the ants want to move to the right ; Then we should begin our movement from the right-most ant ( As it would be at the beginning of the queue in direction of travel )…

So that’s why the inner loop starts from j-1 ( Right-most ant ) and goes uptil last ant that wanted to move right .

Similarly you can notice the change in co-ordinates ; understand what is the direction that is been handled ; And like-wise you will see my code always moves that ant first which is at the beginning of the queue in the direction of travel…

And that is how without using a duplicate array ; you may simulate movements such that overlaps are avoided…

This real life simple concept is useful and can be used to save computer memory for a lot of problems…

And if you know basic DP ; then you should be trying this question after
understanding my explanation…

You can see in the article ; that solution has space complexity - O(n*m) - Mentioned right under the code ; but if you simulate movements wisely ( Like I explained ) ; you can do that without using any extra space… :wink:

I tried to make this as detailed as possible ; still if anything was unclear ; feel free to reach out… Hope this helps… :slight_smile:

1 Like

I have solved the problem using another approach : Solution

Time complexity: O(max(r,c)rc)
Space complexity: O(r*c)

Can you please share link for your code ?? Thanks in advance…

#include<bits/stdc++.h>
using namespace std;
int main()
{
int T;
cin>>T;
for(int t=0;t<T;t++)
{
int r,c;
cin>>r>>c;
string s1[r];
for(int i=0;i<r;i++)
cin>>s1[i];

    int score=0;
	for(int i=0;i<r;i++)
	{
		for(int j=0;j<c;j++)
		{
			if(s1[i][j]=='R')
			{
				// counting colision of R and U
				int row=i+1;
				int col=j+1;
				while(row<r and col<c and row>=0 and col>=0 )
				{				
					if(s1[row][col]=='U' and s1[i][col]!='#')
					{
						int f=1;
						for(int x=i;x<row;x++) // check if there is any # in path of U
						{
							if(s1[x][col]=='#')
							{
								f=0;
								break;
							}
						}
						if(f)
						score++;
					}
					if(s1[i][col]=='#') // R will not be able to move right after this index
						break;
					row++;
					col++;
					
				}
				// counting colision of R and D
				row=i-1;
				col=j+1;
				while(row<r and col<c and row>=0 and col>=0)
				{
					if(s1[row][col]=='D' and s1[i][col]!='#')
					{
						int f=1;
						for(int x=i;x>row;x--)
						{
							if(s1[x][col]=='#')
							{
								f=0;
								break;
							}
						}
						if(f)
						score++;
					}
					
					if(s1[i][col]=='#')
						break;
					row--;
					col++;
				}
				// counting colision of R and l
				col=j+2; // we need to have the difference of columns even for simultaneously reaching at that point.
				row=i;
				int flag=c;
				for(int p=j+1;p<c;p++)
				{
					if(s1[i][p]=='#')
					{
						flag=p;
						break;	
					}
				}
				while(row<r and col<flag and row>=0 and col>=0)
				{
					if(s1[i][col]=='L' and s1[i][(j+col)/2]!='#')
						score++;
					col=col+2;
					
				}
			}
		}
	}
	for(int i=0;i<r;i++)
	{
		for(int j=0;j<c;j++)
		{
			if(s1[i][j]=='L')
			{
				// counting colision of L and U
				int row=i+1;
				int col=j-1;
				while(row<r and col<c and row>=0 and col>=0)
				{
					if(s1[row][col]=='U' and s1[i][col]!='#')
					{
						int f=1;
						for(int x=i;x<row;x++)
						{
							if(s1[x][col]=='#')
							{
								f=0;
								break;
							}
						}
						if(f)
						score++;
					}
					
					if(s1[i][col]=='#')
						break;
					row++;
					col--;
				}
				// counting collision between L and D
				row=i-1;
				col=j-1;
				while(row<r and col<c and row>=0 and col>=0)
				{
					if(s1[row][col]=='D' and s1[i][col]!='#')
					{
						int f=1;
						for(int x=i;x>row;x--)
						{
							if(s1[x][col]=='#')
							{
								f=0;
								break;
							}
						}
						if(f)
						score++;
					}
					
					if(s1[i][col]=='#')
						break;
					row--;
					col--;
				}
			}
		}
	}
	// counting collision between D and U
	for(int i=0;i<r;i++)
	{
		for(int j=0;j<c;j++)
		{
			if(s1[i][j]=='D')
			{
				int row=i+2;
				int col=j;
				int flag=r;
				for(int p=i;p<r;p++)
				{
					if(s1[p][j]=='#')
					{
						flag=p;
						break;
					}
				}
				while(row<flag and col<c and row>=0 and col>=0)
				{
					if(s1[row][j]=='U' and s1[(i+row)/2][j]!='#')
						score++;
					row=row+2;
				}
			}
		}
	}
	cout<<score<<"\n";
}
return 0;

}

A great approach of solving this without maintaining extra array, 3d grid array or saving inputs and by just using single vector, array and set.
https://www.codechef.com/viewsolution/24958103
Code is easy to understand and small.

Thank u so much for explaining your approach

Happy to help…! :smile:

Here is my approach as well. I maintained a time array of vector . it would contain the time of stepping of any ant, then in the end i would see if any vector had duplicated elements using maps. and use n*(n-1)/2 of them and add to my final result.

Here is my Solution :
https://www.codechef.com/viewsolution/25039488