812B - Sagheer, the Hausmeister
Problem statement
Gist
There are $n$ floors and there are some lights on in some rooms, at *some* floors. There are $m$ rooms per floor, and two stairways - one at the start and one at the end.
You can change floors only via the stairs. So implicitly there are $m + 2$ columns, and $n$ rows.
Edge cases:
- You start from the bottom-most row, from the left-most stair-case.
- You don't need to traverse all the rows. If you've turned off all the required lights, you can stop.
Solution
The solution is in the direction of dynamic programming, atleast that's how I did it (because of DP upsolving).
Observations & line of thought:
1. Let's say there are many rooms on the floor from 2,3,4,5...,10, where the light it on. In this case, 3,4,..9 are irrelevant. Only the first and the last rooms with the lights on matter.
2. There are 3 states for a floor, which need different handling in different cases
1. More than one room with lights on
2. One room with lights on
3. No room with lights on
3. For each floor, we can keep track of the minimum cost to reach the starting or the ending point. We can use that by using this cost for the previous (lower) floor.
4. If there are more than one room with lights on, then while calculating the transition cost for the first room, we need to cover the last room on the current floor.
1. This means that if there is a floor $F_2$ and it has rooms with lights on at 2 & 6, and we have floor $F_1$ and it has rooms with lights on at 3 & 7, then if you want to calculate the min cost to reach $F_2${2} then you must cover $F_2${6}, and vice versa.
1. This just means that if you're calculating from $F_1${3} to $F_2${2}, then it must have 6 in it's path, and similarly for $F_1${7} to $F_2${2}, $F_1${3} to $F_2${6} (which should have 2 in it's path) & $F_1${2} to $F_2${7} (which should have 2 in it's path)
5. If there is only a single room with lights on, then all transitions from the previous floor's starting and end points are valid, as you don't need to cover any other points
1. That is $F_1${3} to $F_2${2} is valid, even from the left (3 -> 0, change floors, and then 0 -> 2)
6. If there is no room with lights on, then we have two options, the first column, and the last one, which have stairs in them.
1. Note that the behaviour of this case is NOT similar to the case when you've two rooms, as you can (and will) ignore the second stair.
2. But since both options are relevant - which means that the next floor can use a transition from any of the stairs - left or right, we need to do this calculation for both of the columns.
3. Note that you can mimic the single room case, if you place the room with the lights on at the first stair - get the answer, and then at the last stair - get the answer, and the reset the floor with no rooms with lights on.
Using all these observations, I submitted my code: https://codeforces.com/contest/812/submission/299218591
/*
"I will come again & conquer you
because as a mountain you can't grow, but as a human, I can.”
- Sir Edmund Hillary.
https://codeforces.com/problemset/problem/812/B
*/
#include
using namespace std ;
typedef long long ll ;
typedef long double lld ;
#define f(i,s,n) for(int i=s;i<(int)n;i++)
#define fn(i,s,n) for(int i=s;i>=(int)n;i--)
#define fl(i,s,n) for(ll i=s;i<(ll)n;i++)
#define fln(i,s,n) for(ll i=s;i>=(int)n;i--)
template void mini(C&a4, C b4){a4=min(a4, b4); }
template void maxi(C&a4, C b4){a4=max(a4, b4); }
#define vi vector
#define vii vector>
#define vl vector
#define pb push_back
#define X first
#define Y second
#define pii pair
#define pll pair
#define pli pair
#define pil pair
#define vll vector
#define all(x) x.begin(),x.end()
#define parr(x) {cout<<#x<<" :\n" ;for(auto el:x) cout<& startEnd, vector& dp, int row, int m) {
assert(row > 0);
dp[row].X = dp[row - 1].Y + endLinkCost(startEnd[row - 1].Y, startEnd[row].X, m);
mini(dp[row].X, dp[row - 1].X + endLinkCost(startEnd[row - 1].X, startEnd[row].X, m));
dp[row].Y = dp[row - 1].X + startLinkCost(startEnd[row - 1].X, startEnd[row].Y, m);
mini(dp[row].Y, dp[row - 1].Y + startLinkCost(startEnd[row - 1].Y, startEnd[row].Y, m));
if (startEnd[row].X == startEnd[row].Y) { // only a single 1 in the row
mini(dp[row].X, dp[row - 1].X + startLinkCost(startEnd[row - 1].X, startEnd[row].X, m));
mini(dp[row].Y, dp[row - 1].Y + endLinkCost(startEnd[row - 1].Y, startEnd[row].Y, m));
int minVal = min(dp[row].X, dp[row].Y);
dp[row].X = minVal;
dp[row].Y = minVal;
}
}
void solve() {
int n,m;cin>>n>>m;
vector presence(n, vi(m + 2));
vector startEnd(n, {m + 2, -1});
int rowsToProcess = n;
bool emptyRowsFromTheTop = true;
fn(i, n - 1, 0) {
string s;cin>>s;
f(j,0,m + 2) {
if (s[j] == '1') {
presence[i][j] = 1;
mini(startEnd[i].X, j);
maxi(startEnd[i].Y, j);
}
}
if (startEnd[i].Y == -1) {
// empty row
if (emptyRowsFromTheTop) {
rowsToProcess = i;
}
startEnd[i].X = 0;
startEnd[i].Y = (i == 0 ? 0 : m + 1);
} else {
emptyRowsFromTheTop = false;
}
}
vii dp(n, {0,0});
dp[0].Y = startEnd[0].Y;
dp[0].X = startEnd[0].Y + (startEnd[0].Y - startEnd[0].X);
f(i,1,rowsToProcess) {
if (startEnd[i].Y == m + 1) {
// set fake point at 0
startEnd[i] = {0, 0};
fillRowDp(startEnd, dp, i, m);
int startDpValue = dp[i].X;
// set fake point at m + 1
startEnd[i] = {m + 1, m + 1};
fillRowDp(startEnd, dp, i, m);
int endDpValue = dp[i].Y;
startEnd[i] = {0, m + 1};
dp[i] = {startDpValue, endDpValue};
} else {
fillRowDp(startEnd, dp, i, m);
}
}
if (rowsToProcess == 0) {
cout<<"0\n";
} else {
cout<
Learnings
- Focus on thinking more before writing a single line of code. Writing is easy, thinking is hard.
No comments:
Post a Comment