PROBLEM LINK:
Setter: Hasan Jaddouh
Tester: Yash Chandnani
Editorialist: Ishmeet Singh Saggu
DIFFICULTY:
Medium
PREREQUISITES:
Dynamic Programming and Greedy.
PROBLEM:
You are in a building with M floors and a lift. You are given a sequence B of N floor visited by the lift in order(For its validity consecutive element should have adjacent floor). There can be some floor in this sequence which is unknown(indicated by -1) and you have to compute the minimum number of times the elevator has changed its direction. And in the case where sequence B is invalid then print -1.
QUICK EXPLANATION:
- We will solve this problem using dynamic programming. We will apply dynamic programming on known floors.
- State :
- dp[i][0] is the minimum number of direction change required to visit this floor and at the time lift visit this floor it is moving up.
- dp[i][1] is the minimum number of direction change required to visit this floor and at the time lift visit this floor it is moving down.
- For computing the transition from the minimum number of a direction change from ith known floor to i+1th can be computed efficiently by greedy approach. Also, you have to take care of several conditions while making transitions.
- Also you have to consider the minimum direction change required to reach the first known floor if it is not the first floor in sequence B similarly you have to compute the minimum direction change required to reach the last floor of sequence B if it is unknown.
EXPLANATION:
Let us observe what we can do in this problem. Note if you are at ith floor and if it is known(B_i != -1) then there are only 2 ways in which the elevator might have visited this floor, i.e. it could have come to this floor from below it and it could have visited it from the floor above. So it gives us a hint to solve this problem using dynamic programming. Let us consider all the floor which is known to us in order and compute the number of unknown floors between them and make a separate array A for these known floors. Let us define 2 dp state for the ith floor as dp[i][0] is the minimum number of direction change required to visit this floor and at the time lift visit this floor it is moving up and dp[i][1] is the minimum number of direction change required to visit this floor and at the time lift visit this floor it is moving down. Now let us see how we will handle the state transition from known floor i to known floor i+1.(Note the first known floor might not be the first element of the sequence B so for the minimum number of swaps required to reach this floor we will compute it)
Now for reaching the first known floor A_1 when the lift is moving up. So it means lift reached it from below so we will greedily try to keep the same direction until we reach floor M and if there are still some more floor to cover then we will add 1 to our minimum change variable and greedily move up till we reach floor 1 or finished our unknown floor then again if more unknown floors are left again we will add 1 and go down till M and so-on. Similarly, we will compute for reaching the first known floor A_1 when the lift is moving down.
State Transitions
- Value of dp[1][0] and dp[1][1] for the first floor is computed from the method above, and if it is the first floor of the sequence B then these values will be 0.
- Let us represent the number of unknown floors between floor A_i and floor A_{i+1} by X.
- So if the floor difference between A_i and A_{i+1} > X then you cannot reach from floor A_i to A_{i+1} and the sequence B is invalid so answer is -1.
- Let us represent the absolute difference between floor as Y. Then we can reach reach floor A_{i+1} only if distance between them in sequence B(X+1) has same parity as Y,
i.e. (X+1) % 2 == Y % 2.(Why? Let consider A[i] <= A[i+1] then as we know that final floor is A[i+1]. so all the floor we visited below A[i+1] in our optimal traversal will be added 2(or 4 or 6) times as we have to comeback and similarly for all the floor above A[i] hence not affecting the parity of distance). - Now we will compute transition from dp[i][0] to dp[i+1][0] and dp[i+1][1], dp[i][1] to dp[i+1][0] and dp[i+1][1]. For computing the minimum number of direction change we will greedily try to keep the same direction until you reach floor 1 or floor M until the distance between you and destination and until you can make it back to the is equal to the difference in the number of floors between your current floor and destination(
plus you might have to travel some more floors to change the direction when you reach the floor A[i+1] with the wrong direction so you have to handle that too and save some distance for it). Also for floor 1 you can’t reach it from above and for floor M you can’t reach it from below so have to handle that too. Also, there might be a transition where you can reach the floor but can’t have the proper direction so we don’t have to consider that transition.
dp[i+1][0] = min(dp[i][0] + min_direction_change_when_init_direction_is_up_and_final_direction_is_up, dp[i][1] + min_direction_change_when_init_direction_is_down_and_final_direction_is_up);
dp[i+1][1] = min(dp[i][0] + min_direction_change_when_init_direction_is_up_and_final_direction_is_down, dp[i][1] + min_direction_change_when_init_direction_is_down_and_final_direction_is_down);
So if there is a floor for which reaching it is not possible in both cases, when final direction of lift is up and when final direction of lift is down then the answer is -1 else consider there are N' floor in array A. Now the only thing that is left is to compute the number of direction change required to cover the unknown floors which are after the last known floor N'. Suppose we will consider dp[N'][0] so the lift is moving up we will greedily try to keep the same direction until we reach floor 1 and if there are still some more floor to cover then we will add 1 to dp[N'][0] and greedily move down till we reach floor M or finished our unknown floor then again if more unknown floors are left again we will add 1 and go up till 1 and so-on. Similarly, we will compute for dp[N'][1] when the lift is moving down. Minimum of dp[N'][0] and dp[N'][1] will be our final answer.
Note In the case where all floors are unknown. In that case, it is optimal to start at floor 1 and go all the way to floor M, if still some more floor is left then add 1 to the answer and move all the way up to the floor 1, if still some more floor is left then add 1 and go down and so-on.
TIME COMPLEXITY:
- N is the sequence length and sum of computation of all dp transition is O(N), so total time complexity per test case is O(N)
SOLUTIONS:
Setter's Solution
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <assert.h>
using namespace std;
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){
assert(cnt>0);
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 T;
int n;
int sm_n=0;
int m;
int A[100100];
int dp[100100][2]; // 0 going down - 1 going up
int calculate(int start_y,int start_x,int end_y,int end_x,bool & going_up){
int cur = start_y;
int idx = start_x;
int cost = 0;
while(true){
if(idx == end_x){
break;
}
if(going_up && cur - end_y == end_x - idx){
cost++;
going_up = ! going_up;
break;
}
if(!going_up && end_y - cur == end_x - idx){
cost++;
going_up = ! going_up;
break;
}
if(going_up){
if(cur == m){
cost++;
going_up =false;
cur = m-1;
} else {
cur++;
}
} else {
if(cur==1){
cost ++;
going_up =true;
cur = 2;
} else {
cur--;
}
}
idx++;
}
return cost;
}
int get_ans(int l,int r,bool is_forced_up,bool is_forced_down,bool is_forced_up_end,bool is_forced_down_end){
vector<pair<int,int> > arr;
for(int i=l;i<=r;i++){
if(A[i] != -1)
arr.push_back(make_pair(i-l,A[i]));
}
int len= r-l;
int s = arr.size();
for(int i=1;i<s;i++){
if(abs(arr[i].second - arr[i-1].second) > arr[i].first - arr[i-1].first){
return 1<<20;
}
}
for(int i=0;i<s;i++){
dp[i][0] = dp[i][1]= 1<<20;
}
if(!is_forced_down){
if(arr[0].second -1 < arr[0].first){
dp[0][1] = ( arr[0].first - arr[0].second +1 + m - 2) /(m-1);
} else {
dp[0][1]= 0;
}
}
if(!is_forced_up){
if(m-arr[0].second < arr[0].first){
dp[0][0] = ( arr[0].first - (m-arr[0].second) + m - 2) /(m-1);
} else {
dp[0][0]= 0;
}
}
for(int i=0;i<s-1;i++){
dp[i][0] =min(dp[i][0] ,dp[i][1]+1);
dp[i][1] =min(dp[i][1] ,dp[i][0]+1);
bool going_up=true;
int cst =calculate(arr[i].second,arr[i].first,arr[i+1].second,arr[i+1].first,going_up);
if(going_up){
dp[i+1][1] = min(dp[i+1][1], dp[i][1] + cst);
} else {
dp[i+1][0] = min(dp[i+1][0], dp[i][1] + cst);
}
going_up=false;
cst =calculate(arr[i].second,arr[i].first,arr[i+1].second,arr[i+1].first,going_up);
if(going_up){
dp[i+1][1] = min(dp[i+1][1], dp[i][0] + cst);
} else {
dp[i+1][0] = min(dp[i+1][0], dp[i][0] + cst);
}
}
dp[s-1][0] =min(dp[s-1][0] ,dp[s-1][1]+1);
dp[s-1][1] =min(dp[s-1][1] ,dp[s-1][0]+1);
if(arr[s-1].first == len){
int ans = 1<<20;
if(!is_forced_up_end){
ans = min(ans,dp[s-1][0]);
}
if(!is_forced_down_end){
ans = min(ans,dp[s-1][1]);
}
return ans;
}
int ans = 1<<20;
if(len - arr[s-1].first > m- arr[s-1].second){
ans =min(ans,dp[s-1][1]+ (len - arr[s-1].first - (m- arr[s-1].second) + (m-2))/ (m-1));
} else {
ans =min(ans,dp[s-1][1]);
}
if(len - arr[s-1].first > arr[s-1].second - 1){
ans =min(ans,dp[s-1][0]+ (len - arr[s-1].first - (arr[s-1].second - 1) + (m-2))/ (m-1));
} else {
ans =min(ans,dp[s-1][0]);
}
return ans;
}
int main(){
//freopen("03.txt","r",stdin);
//freopen("03o.txt","w",stdout);
T=readIntLn(1,1000);
while(T--){
bool ok=true;
n=readIntSp(1,100000);
m=readIntLn(2,100000);
sm_n+=n;
assert(sm_n<=1000000);
for(int i=0;i<n;i++){
if(i==n-1){
A[i]=readIntLn(-1,m);
} else {
A[i]=readIntSp(-1,m);
}
assert(A[i] != 0);
}
int val = -1;
for(int i=0;i<n;i++){
if(A[i]==-1)continue;
if(val == -1){
val = (A[i]+i)%2;
} else {
if(val != (A[i]+i) %2){
ok=false;
}
}
}
if(n==1){
cout<<0<<endl;
continue;
}
if(val == -1){
cout<< (n-2)/(m-1)<<endl;
continue;
}
int cur_x=-1;
int cur_y= -1;
for(int i=0;i<n;i++){
if(A[i] == -1)continue;
if(cur_x == -1){
cur_x = i;
cur_y = A[i];
continue;
}
if(i - cur_x < abs(cur_y - A[i])){
ok=false;
}
}
if(!ok){
cout<<-1<<endl;
continue;
}
int ans = get_ans(0,n-1,false,false,false,false);
if(ans >= 1<<20){
cout<<-1<<endl;
continue;
} else {
cout<<ans<<endl;
}
}
assert(getchar()==-1);
}
Feel free to share your approach. In case of any doubt or anything is unclear please ask it in the comment section. Any suggestions are welcomed. 