Skip to main content

Posts

Maximum Increase - 702A - Codeforces Solution

Formal Problem Statement - You are given array consisting of n integers. Your task is to find the maximum length of an increasing subarray of the given array. A subarray is the sequence of consecutive elements of the array. Subarray is called increasing if each element of this subarray strictly greater than previous. Problem Link - Codeforces - 702A This is a simple problem, with an even simpler solution. We simply transverse across the array comparing each element with the one before it, and maintaining two counters, one for the length of current increasing sequence, and other for the length of overall maxima till this point. Even better, we don't need to store the array, we can transverse by just storing the current, and the element before it. So, the memory required is lesser. After an analysis of this algorithm, we can say that it runs in  θ(n) time. #include <iostream> #include <algorithm> using namespace std; int main() { int n, pRead, cRead;
Recent posts

Greedy Ascent Algorithm - Finding Peak in 2D Array

Formal Problem Statement - Find a peak in a 2D array, where a is a 2D-peak iff a ≥ b, a ≥ d, a ≥ c, a ≥ e. If there are more than one peaks, just return one of them. Greedy Ascent Algorithm  works on the principle, that it selects a particular element to start with. Then it begins traversing across the array, by selecting the neighbour with higher value. If there is no neighbour with a higher value than the current element, it just returns the current element. Logically, this algorithm is correct, as it returns the element - which has none of it's neighbours greater than the current element. After a bit of thought, we can come to the conclusion that, in a worst case, the whole array will be transversed. Hence, its time complexity is Θ(mn) . Finally, the code using recursion would be, #include <iostream> using namespace std; int a[100][100], n, m; int recur(int i, int j) { if (i > 0 && a[i - 1][j] > a[i][j]) return recur(i - 1,

Boredom Problem Solution - Codeforces 445A (Round 260, Div1)

This is a beautiful beginner level dynamic programming problem, and is quite important if you are just beginning to understand recursion. Problem Statement -  Alex doesn't like boredom. That's why whenever he gets bored, he comes up with games. One long winter evening he came up with a game and decided to play it. Given a sequence a consisting of n integers. The player can make several steps. In a single step he can choose an element of the sequence (let's denote it ak) and delete it, at that all elements equal to ak + 1 and ak - 1 also must be deleted from the sequence. That step brings ak points to the player. Alex is a perfectionist, so he decided to get as many points as possible. Help him. Problem Source - Codeforces 445A Let's consider a simple case to begin with, if the sequence is 2 2 2. Then, clearly, Alex has only one choice - to pick the number 2. In that case, his score would be 2*3 = 6. Moving forward, if the sequence was 2 2 3. Then Alex