PROBLEM LINK:
Author : John Zakkam
Testers : Mann Mehta, Smit Mandavia, Taranpreet Singh, Aneesh D H, Jaymeet Mehta, Himani Popli and Raksha Jain.
Editorialist : John Zakkam
DIFFICULTY:
EASY
PREREQUISITES:
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 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,' ');
}
int main()
{
FIO;
ll t,m,n,d,i,j,s,e,ans,prv;
t=readIntLn(1,100);
while(t--){
m=readIntSp(1,300);
n=readIntLn(1,300);
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++){
a[i][j]=readStringSp(1,1)[0];
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;
}
}
a[i][j]=readStringLn(1,1)[0];
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
test=int(stdin.readline())
for _ in range(test):
N,M = map(int,stdin.readline().split())
mat=[]
for i in range(N):
mat.append(list(stdin.readline().strip().split()))
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[0][1]-s_and_d[0][0])
continue
for i in range(sx,N-1):
l,r,nl,nr=s_and_d[i][0],s_and_d[i][1],s_and_d[i+1][0],s_and_d[i+1][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][1]-s_and_d[-1][0]
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.