Hello CodeForces !
I was solving this Problem on CodeChef the other Day. I misinterpreted the question and was thinking of a different variety of the same question.
Problem Link
Originally, the Question says —
You have $$$N$$$ cities where $$$A[i]$$$, $$$0≤A[i]≤10^9$$$ denotes the Unhappiness Value of the $$$i^{th}$$$ city.
You are given two integers $$$X$$$ and $$$Y$$$. For each Blimp sent, you can make one of the following choices —
Operation 1. Make the Blimp Fly over every city, in which case the sadness of every city will decrease by $$$Y$$$.
Operation 2. Choose a city $$$i$$$, where ($$$1≤i≤N$$$), and shower confetti over city $$$i$$$. In this case, the sadness of cities $$$1, 2,..., i−1$$$ will decrease by $$$Y$$$, the sadness of city $$$i$$$ will decrease by $$$X$$$, and cities $$$i+1, i+2,..., N$$$ see no change in sadness.
(Note that each of the operation consumes 1 Blimp at a time).
We have to find the minimum number of blimps needed such that, by making the above choice optimally for each blimp, you can ensure that no city is sad (i.e, in the end every city has sadness $$$A[i]≤0$$$).
Modification (this is what I thought)
Operation 1 — Instead of Making the Blimp Fly over every city, I will only reduce the unhappiness of the $$$i^{th}$$$ City by $$$Y$$$.
Operation 2 (Confetti) — Stays the same.
What would be the Minimum Number of Blimps Needed ?
My Approach -Let $$$dp(n)$$$ be an array/vector where $$$dp[i]$$$ denotes the minimum Blimps required for the $$$i^{th}$$$ city. $$$Σ dp[i]$$$ will give me the final answer. I will keep a counter to update $$$A[i]$$$ due to any prior Confetti Operations.
$$$Case 1.$$$ When $$$X≥Y$$$. Always Perform Operation 2.
$$$Case 2.$$$ When $$$X \lt Y$$$.
Let us first check if $$$X≥A[i]$$$. In this case, even if $$$X \lt Y$$$, its still better to perform Operation 2 as Number of Blimps required would be the same.
Else, we perform Operation 1 until we have a value less than $$$Y$$$. We would now have $$$dp[i] = A[i] / Y$$$ and $$$A[i]$$$ $$$=$$$ $$$A[i]$$$ $$$mod$$$ $$$Y$$$.
If $$$A[i] != 0$$$, we again check if $$$X≥A[i]$$$. If the condition now holds, we perform Operation 2, (1 time) in addition to previous Operation 1's. If not, then we perform one more Operation 1 to get $$$dp[i]$$$.
Implementation (C++)#include <iostream>
#include <vector>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int tc; cin >> tc;
while(tc--)
{
int n, x, y;
cin >> n >> x >> y;
vector<int> v(n);
for(int i=0; i<n; i++) cin >> v[i];
vector<int> dp(n);
int ctr = 0;
for(int i=n-1; i>=0; i--)
{
v[i] -= ctr; // update unhappiness
if(v[i] <= 0) dp[i] = 0; // already happy
else
{
if(x >= y) // always drop confetti
{
dp[i] = v[i] / x;
dp[i] = ((v[i] % x) != 0) ? dp[i] + 1 : dp[i];
ctr += y * dp[i];
}
else
{
if(x >= v[i]) // use confetti even if y > x
{
dp[i] = 1;
ctr += y;
}
else
{
dp[i] = v[i] / y;
v[i] = v[i] % y; // remaining
if(v[i] != 0)
{
if(x >= v[i]) ctr += y; // use confetti even if y > x
dp[i] += 1;
}
}
}
}
}
int s = 0;
for(int i=0; i<n; i++) s += dp[i];
cout << s << '\n';
}
return 0;
}
I wanted to know if my Approach & Implementation for the Modified Version of the Problem is correct or not.
Полный текст и комментарии »
