Decrease subarray by 1, min operations to make it 0
Link: https://leetcode.com/problems/minimum-number-of-increments-on-subarrays-to-form-a-target-arrayint minNumberOperations(vector<int>& arr) {
// rephrase
// invert the problem, in one operation, can dec subarray by 1, convert to 0
// greedy, start from left to right, for each index, find the next smaller
// and decrease from current to next smaller ( excluded ) to make it same height
// as the next smaller
// my initial approach of doing horizontal slices was too complicated though I think it would've worked too
// in any case, I only pay when I go up, for any goin down, I an just extend the relevant slices to make my slabs
int ans = arr[0];
for (int i = 1; i < (int)arr.size(); i++) {
if (arr[i] > arr[i - 1]) ans += arr[i] - arr[i - 1];
}
return ans;
}(Prev variation) both increase and decrease subarray by 1 and make source to target
The idea of extending ranges is similarly applied
long long minimumOperations(vector<int>& nums, vector<int>& target) {
// similar idea as another problem where only decrements were allowed and target was 0
// you extend the previous range or start anew
// so on each turn, either you extend in the direction of current accum ( new ranges ), or adjust it downward at 0 cost ( close ranges )
// or close all in the other direction entirely ( this has cost )
#define int long long
int n = nums.size();
int ans = 0, acc = 0;
for (int i = 0; i < n; i++) {
int acc_needed = target[i] - nums[i]; // what accumulator should be
if (acc_needed == acc) continue;
// if in the same direction
if (acc * acc_needed > 0) {
if (abs(acc_needed) >= abs(acc)) {
// need to extend in the same direction
ans += abs(acc_needed - acc);
} else {
// can downsize at 0 cost
}
} else {
// just reset to 0 and continue from there
ans += abs(acc_needed);
}
acc = acc_needed;
}
return ans;
#undef int
}Car Fleet 1
Link: https://leetcode.com/problems/car-fleet/int carFleet(int target, vector<int>& position, vector<int>& speed) {
// observation: it's clear by the direction that I need to go left to right
// starting from the smallest position
// observation, your speed is limited by speed of cars ahead you
// let t(i) be time the ith car reaches target
// each car is limited by car to it's right
// so start from right to left
// ti = suffix max of t(i..)
// answer is the number of distinct t(i)
int n = position.size();
vector<pair<int, int>> v(n);
for (int i = 0; i < n; i++) v[i] = pair<int, int>{position[i], speed[i]};
sort(v.begin(), v.end());
int ans = 0;
double mx = 0;
for (int i = n - 1; i >= 0; i--) {
auto [pos, speed] = v[i];
double time = ((double)target - pos) / speed;
if (time > mx) mx = time, ans++;
}
return ans;
}Car Fleet 2
Link: https://leetcode.com/problems/car-fleet-ii/vector<double> getCollisionTimes(vector<vector<int>>& v) {
// attempt 1:
// this is entirely based on the next car which is wrong as there can be multiple steps of slowdowns
// observation 1:
// the correct way is to relate to that collisions problem in google code jam
// collisions are independent, assume that cars just "move past"
// so the collisions time = min { collision time with the invididual cars ahead }
// observation 2:
// above naively will be O(n^2)
// notice that since you can consider the pairs individually and start from right to left
// note that since you only care about pairs (i,j) where i<j
// remove any where speed(j)>=speed(i), that's a never case
// will it be needed ever again? no as I will be pushing i, if it collides with j, it must first collide with i
// for all where speed(j) < speed(i), I only want to consider the "leaders"
// so if the time to collision with the stack top is>=stack top collides with something else
// then this mean stack top was slowed down by some other car and it's not a leader
// so I can remove stack top
// will this be needed ever again? no as any that needed this would first meet i which I'll push
int n = v.size();
vector<double> ans(n);
double inf = 1e18;
auto collision_time = [&](int i, int j) {
assert(i < j);
double rel_speed = v[i][1] - v[j][1];
if (rel_speed <= 0) return inf;
double rel_dist = v[j][0] - v[i][0];
return rel_dist / rel_speed;
};
vector<int> stk;
ans[n - 1] = -1;
stk.push_back(n - 1);
for (int i = n - 2; i >= 0; i--) {
auto bad_top = [&]() {
int top = stk.back();
auto next_touch = collision_time(i, top);
if (next_touch == inf) return true;
if (ans[top] != -1 && next_touch >= ans[top]) return true;
return false;
};
while (!stk.empty() && bad_top()) stk.pop_back();
if (stk.empty())
ans[i] = -1;
else
ans[i] = collision_time(i, stk.back());
stk.push_back(i);
}
return ans;
}