ARTICLE AD BOX
I had this problem in a competitive programming contest:
In a queue, there are N people in front of you, 1, 2, …, N. You know that a person at ith position, will take Ai units of time. You can choose to bribe a person in front of you for Bi amount of money (i is their position) and exchange positions with them. You can bribe multiple people but only bribe the person who is in front of you. As time is money, each unit of time is exactly equal to a unit of money. Assuming bribing a person and exchanging positions with them is instantaneous, you need to tell the least amount of money you need to spend to get in front of the queue.
Further, there will be Q updates to queue, and you need to tell answer for the original case, and every case after making an update.
Input: 1st line: N
2nd line: N integers, A1, A2, …, An.
3rd line: N integers, B1, B2, …, Bn.
4th line: Q
Next Q lines, with each line being:
i, a and b
in each update, A[i] = a and B[i] = b.
My approach to solve this question was to calculate the prefix sums of array A
from the start and array B from the back.
and then for each position i, I calculate the cost for getting in front of the queue by standing there after bribing everyone till that position. And taking the minimum of them all.
So for a position i, it will be A[i-1] + B[i].
Then, after each update, I recalculate the prefix sum for A and B from the index i and find the minimum i again.
And its worst case complexity would be: O(N * Q).
This solution worked for starting subtasks but time limit was being exceeded in some of the tasks of the later subtasks.
Is there a way to further optimize this approach or can there be an entirely new better approach to this problem?
This was my code as far as I can remember it to be:
#include <bits/stdc++.h> using namespace std; int main() { int N, Q, *A, *B; cin >> N; //Easier to calculate prefix sums //A1 is stored at index 1, B2 is stored at index 1 //So A[1] + B[1] is A1 + B2 //So is A[0] + B[0] is 0 + B1 (Bribe everyone case) //And so is A[N] + B[N] is AN + 0 (Bribe no one case) A = new int[N + 1]; B = new int[N + 1]; A[0] = 0; B[N] = 0; for (int i = 0; i < N; i++) { cin >> A[i + 1]; } for (int i = 0; i < N; i++) { cin >> A[i]; } cin >> Q; int ai = 1; int bi = N - 1; int a, b; int iterator = 0; int _min; while (iterator <= Q) { _min = 0; // Calculate prefix for (int i = ai; i <= N; i++) { A[i] += A[i - 1]; } for (int i = bi; i >= 0; i--) { B[i] += B[i + 1]; } //Calculate min for(int i = 0; i <= N; i++) { _min = min(_min, A[i] + B[i]); } cout << _min << '\n'; if(iterator < Q) { cin >> ai >> a >> b; bi = ai-1; } iterator++; } return 0; }