 # CARLOT - Editorial

Author : John Zakkam
Testers : Mann Mehta, Smit Mandavia, Taranpreet Singh, Aneesh D H, Jaymeet Mehta, Himani Popli and Raksha Jain.
Editorialist : John Zakkam

EASY

Greedy, Matrix

## PROBLEM:

There are M levels for a building numbered from 1 to M from top to bottom, each level having N parking spots numbered from 1 to N from left to right. Some spots might have a car while other may be empty.
There is a thief who wants to unlock all the cars. Now, he is skilled such that for the first time, he can directly reach in any parking spot in no time.
Find the minimum time when all the cars would be unlocked.He can start from anywhere in the matrix.

# EXPLANATION:

So, to make it clear, you are given a M x N character matrix with 'N' and 'P', you have to go through all the 'P' s in minimum number of steps.You can start from anywhere in the matrix.
We follow a greedy approach to this problem, Go to the 1st occured 'P', depending on the row, like if it’s even row, you have to go to the right most 'P' in that row.
If it is odd row, we go to the left most 'P'. From the starting position, we go on till we reach the last 'P'.Now, we follow a greedy strategy, like :
First of all let us find cost by type one movement, that is cost of vertical movement.Find first and the last row having at least one car. If there isn’t any car then answer is 0 (given in question).
Otherwise vertical movement cost = last-first. Then lets store first and the last position of car in each row. Now for going from odd row to even row, we will need abs(last(odd_row)-last(even_row)) steps and abs(first(odd_row)-first(even_row)) for going from even to odd row also in each row we will need (last(row)-first(row)) steps
We also need to take care of case when rows are empty between two rows having at least one car, we can just skip those row because we will only need vertical cost for it.

# SOLUTIONS:

Setter's Solution in C++
``````#include<bits/stdc++.h>
using namespace std;

#define ll long long int
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mod 1000000007

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 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){
}
long long readIntLn(long long l,long long r){
}
}
}

int main()
{
FIO;
ll t,m,n,d,i,j,s,e,ans,prv;
while(t--){

char a[m][n];
ll l[m],r[m];
s=-1;

for(i=0;i<m;i++){
l[i]=-1;
for(j=0;j<n-1;j++){
assert(a[i][j]=='N' || a[i][j]=='P');
if(a[i][j]=='P'){
if(s==-1)
s=i;
e=i;
if(l[i]==-1)
l[i]=j;
r[i]=j;
}
}
assert(a[i][j]=='N' || a[i][j]=='P');
if(a[i][j]=='P'){
if(s==-1)
s=i;
e=i;
if(l[i]==-1)
l[i]=j;
r[i]=j;
}
}

if(s==-1){
cout << 0 <<  "\n";
continue;
}

ans=r[s]-l[s]+(e-s);
if(s%2==0)
prv=r[s];
else
prv=l[s];

for(i=s+1;i<=e;i++){
if(l[i]==-1)
continue;
if(i%2==0){  // towards right
if(prv!=l[i])
ans+=(int)abs(prv-l[i]);
prv=r[i];
}else{
if(prv!=r[i])
ans+=(int)abs(r[i]-prv);
prv=l[i];
}
ans+=r[i]-l[i];
}

cout << ans << "\n";
}
assert(getchar()==-1);
return 0;
}
``````
Tester's Solution in Python
``````from sys import stdin,stdout
for _ in range(test):
mat=[]
for i in range(N):
first_p,sx,sy,dx,dy=False,0,0,0,0
s_and_d=[]
for i in range(N):
start=False
temp_s,temp_d=-1,-1
for j in range(M):
if mat[i][j]=="P":
if not start:
start=True
temp_s=j
temp_d=j
s_and_d.append([temp_s,temp_d])
if start:
if i%2:
dx,dy=i,temp_d
else:
dx,dy=i,temp_s
if not first_p:
first_p=True
if i%2:
sx,sy=i,temp_d
else:
sx,sy=i,temp_s
steps=0
cy=sy
if not first_p:
print(0)
continue
if N==1:
print(s_and_d-s_and_d)
continue
for i in range(sx,N-1):
l,r,nl,nr=s_and_d[i],s_and_d[i],s_and_d[i+1],s_and_d[i+1]
steps+=r-l
if i%2:
if l!=-1:
cy=l
if nl!=-1:
steps+=abs(cy-nl)
cy=nl
else:
if r!=-1:
cy=r
if nr!=-1:
steps+=abs(nr-cy)
cy=nr
steps+=s_and_d[-1]-s_and_d[-1]
steps+=dx-sx
print(steps)
``````

An alternate approach can be found here.
If you find any ambiguity in this or you would like to share something, please comment below.

1 Like

Can we not use Recursion or backtracking to solve this …?

1 Like

can you attach the test cases

1 Like

Sorry for the late reply @kevin_eleven , you can check the test data here

1 Like

I don’t think its good idea to do it. This greedy approach is more easily implemented.