arujbansal's blog

By arujbansal, 4 weeks ago, In English

Hey guys, I made a video on the Convex Hull Trick (a great dynamic programming optimization). I explain the general idea behind it and how we can implement it/the idea behind using it when:
1. Our slopes are monotonic and our query values are monotonic
2. Our slopes are monotonic

I basically explain it through the last problem of the atcoder dp contest (links to everything are available in the video description) so this video also serves as an editorial for Frog 3.
I do recommend that you first read the description as this video does have prerequisites.

Here is the video: Convex Hull Trick Video

You can read more about CHT here: CP-Algorithms Convex Hull Trick and Li Chao Trees

I don't go into dynamic CHT or Li Chao Trees but you can check the video description for a tutorial on Li Chao Trees by radoslav11 which is a great tutorial. I was easily able to learn how Li Chao Trees work from it.

Read more »

 
 
 
 
  • Vote: I like it
  • +104
  • Vote: I do not like it

By arujbansal, history, 5 weeks ago, In English

Hey guys!

I've started a YouTube channel called "Algorithms Conquered". I uploaded a video on segment trees to see how it goes. I am thinking of uploading videos on problems on segment trees and different ways in which we can use segment trees and well as educational dynamic programming problems (not classic problems but problems which will improve your understanding of dp in general).

I'd appreciate if you can check it out :)

Algorithms Conquered


Also, if you have any video ideas or want to learn something do let me know in the comments!

Read more »

 
 
 
 
  • Vote: I like it
  • +72
  • Vote: I do not like it

By arujbansal, 5 months ago, In English

The generalised use case for a difference array is this:
You are given Q ranges in the form (L, R) and for each point you have to find how many ranges overlap at that point.

In this problem, we are given an array and M operations in the form (L, R, Value) and for each operation, we have to add Value to each point in the range L, R of the given array. After this, we are given K queries in the form of (x, y) and for each point in the range (x, y), we have to perform operations x1, x2 ... y.

Before we get started, if you are not familiar with prefix sums, I would suggest you read up on it here:
GFG Prefix Sums

Difference Arrays are basically used to perform multiple range update queries where we only need to find the answer after performing all the queries. They allow us to do so in O(n).
Note: Performing a single update query is O(1). It is only when we need to print our final answer, we use prefix sums which take O(n).

Let's say I have the following array of 5 integers called elements (1 based indexing):
1 1 1 1 1

l is the left boundary of our range query and r is the right boundary of our query.
My queries are as follows (in the format l, r, and update value):
1 3 2
4 5 3
1 4 1
1 5 -1

Let's assume that our constraints are pretty large and we need a very efficient solution to this problem.
Instead of iterating over the range and adding the value to each element in our array, we will create a new array (the difference array) called diff initially filled with zeroes. It will be of size 1 + the size of our initial array.
Now, instead of iterating over each element of our array and adding the values, we can simply add the value to index l of our difference array and subtract it from the index r+1 of our difference array. We need a difference array of size n+1 because we subtract the update value from r+1. Here, the right bound of the query + 1 can also the number present at position n+1.
We will see how this works in a moment.

Difference Array at each query:
0 0 0 0 0 0 (Before any query)
2 0 0 -2 0 0
2 0 0 1 0 -3
3 0 0 1 -1 -3
2 0 0 1 -1 -2

Finally, we will run a loop from 2 to n (size of the array) and add diff[i-1] to diff[i].
Now, running a loop from 1 to n, we will add diff[i] to elements[i].

What are we doing?
When we added our update value to index l and subtracted it from index r+1 and later on used prefix sums, for every range that we were supposed to update, our update value got added to it. As we were running the loop from 1 to n only once, we subtracted the update value from index r+1 of the difference array so that when we are summing it up, the update value we added earlier to index l does not get added to elements outside the update range.

Let's say we had a difference array of 0's as follows:
0 0 0 0 0 0

If we had to update range 2 — 4 with value 2, we would add 2 to index 2 and subtract 2 from index 5:
0 2 0 0 -2 0

Now when we use prefix sums, our final array will look like this:
0 2 2 2 0 0

If we had not subtracted 2 from r+1, our array would look like: 0 2 2 2 2 2



Code:
#include <bits/stdc++.h>

using namespace std;

int main() {

	int n = 5; // Size of array
	vector<int> elements{0, 1, 1, 1, 1, 1}; // 1 based indexing
        // n+2 because we need are not using the 0-th index and we need one more element in the array.
	vector<int> diff(n + 2, 0); 
	
	int updateValue = 10;
	int l = 2, r = 5;
	diff[l] += updateValue;
	diff[r + 1] -= updateValue;
	
	for (int i = 1; i <= n; i++) {
		diff[i] += diff[i - 1];
		elements[i] += diff[i];
	}
	for (int i = 1; i <= n; i++) cout << elements[i] << " ";
	return 0;
}

I highly recommend you try this problem based on this concept to understand it better:
295A - Greg and Array
My solution:
83554391

Feel free to share problems :)

Read more »

 
 
 
 
  • Vote: I like it
  • +101
  • Vote: I do not like it

By arujbansal, 6 months ago, In English

Take a look at the tasks here: Contest Link


A — Frog 1

The main thing to note in this problem is that the frog, from a position i can jump to only i + 1 or i + 2. This simplifies the problem.
We will create an array dp of size n (the total number of stones). dp[i] will store the minimum cost we can achieve till position i. An array jumps of size n will store the height of each stone.

For our base cases, we will set dp[0] = 0 and dp[1] = abs(jumps[1] — jumps[0]) as if we are on the second stone (0 based indexing), there is only one way to reach it i.e from the first stone.

Now, to get our final answer, dp[n-1], we need to solve all of our subproblems. To solve for any given position i, we need to have calculated the best we could do for positions i — 1 and i — 2. Why do we need to only consider positions i — 1 and i — 2? Well that is because the frog can only jump one or two stones ahead of its current position i.e to reach its current position i it had to have been at either i — 1 or i — 2.

We can simply do this in O(n).
For any given position i > 2, we can solve the subproblem this way:

dp[i] = min(dp[i-1] + abs(jumps[i] - jumps[i-1]), dp[i-2] + abs(jumps[i] - jumps[i-2]))

dp[i] will be the minimum cost to reach that position. To calculate this, we find the minimum cost of reaching positions i — 1 and i — 2. and then add the cost of jumping to position i and store the minimum.

Problem Link
Solution Link


B — Frog 2

This problem is slightly different from the first one. This time, we are given an additional variable k telling us the maximum size of a jump. k in the last problem was basically fixed to 2 as from a stone i we could only jump to i + 1 and i + 2.

Now, how do we modify our solution to handle this new case where k can be greater than 2?

We will still create an array dp (all values set to INFINITY) of size n (the number of stones we have). dp[i] will denote the minimum cost to reach stone i.
Our base case again, dp[0] = 0 (0 based indexing) as we start off from the first stone.

We use a nested loop:

for (int i = 0; i < n; i++) { // i represents the stone the frog is currently at.
        for (int j = i + 1; j <= i + k; j++) { // j represents a potential stone for the frog to jump to.
            if (j < n) // We have to check if the stone we want to jump to is not out of bounds.
                // Storing the total minimum cost to reach stone j from stone i.
                dp[j] = min(dp[j], dp[i] + abs(stones[j] - stones[i]));
        }
}

Here, the first for loop denotes that the frog is currently at stone[i]. The second for loop basically calculates the best we can do if we jump from stone[i] to stone[i+1], stone[i+2], stone[i+3] ... stone[i+k].
We are performing the min() operation because if the cost of jumping from i to j is higher than a cost we have already found, we do not want to update dp[j] to a higher cost.

We perform this for every position the frog could be at i.e it is performed for all positions i, i+1, i+2...n.

After performing these operations (solving all the subproblems), our final answer is stored at dp[n-1] (0 based indexing).

Problem Link
Solution Link


C — Vacation

We are given three types of activities. We get different amount of points by doing each activity each day. The only restriction is that we cannot do the same activity on two consecutive days.
For example, if we did activity A yesterday, we cannot do activity A today but we can do it tomorrow.

To solve this problem, we will maintain a 2D array, dp[n][3].

dp[i][0] will store the maximum points we can gain by doing activity A on day i.
dp[i][1] will store the maximum points we can gain by doing activity B on day i.
dp[i][2] will store the maximum points we can gain by doing activity C on day i.

Our base cases will be:

// If you swim in the sea in sea on the first day, you cannot get more than a[0] points.
dp[0][0] = a[0]; 
// If you catch bugs in the mountains on the first day, you cannot get more than b[0] points.
dp[0][1] = b[0]; 
// If you do homework at home on the first day, you cannot get more than c[0] points.
dp[0][2] = c[0]; 

For every day i, as we cannot do the activity we did on the previous day,

// If we do activity A today, we have to have done activities B or C on the previous day.
dp[i][0] = a[i] + max(dp[i - 1][1], dp[i - 1][2]); 

// If we do activity B today, we have to have done activities A or C on the previous day.
dp[i][1] = b[i] + max(dp[i - 1][0], dp[i - 1][2]);

// If we do activity C today, we have to have done activities A or B on the previous day. 
dp[i][2] = c[i] + max(dp[i - 1][1], dp[i - 1][0]); 

Simply by checking for each day i, we can calculate the best we can do by the end of our last day.
As we can end by doing activities A, B, or C, our answer will be the maximum points gained on doing activities A, B, or C on the last day.
Time complexity: O(n)

Problem Link
Solution Link

Read more »

 
 
 
 
  • Vote: I like it
  • +38
  • Vote: I do not like it