BeautifuLogic

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,...

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 ...