Credits: _deactivated_, dnshgyl21, Sawarnik, Xzirium

The Easy One

Simply sort the three numbers, then print the second number, or otherwise do the same with a few if-else statements.

Love For Subsets

It can be shown that the optimal way is to first take all the odd numbers, then out of the remaining take those which are congruent to 2 mod 4. Then those which are congruent to 4 mod 8, then 8 mod 16 and so on. Using simple maths, it can be done in logn time.

Max Out Parallelogram

First we recall an important property of a parallelogram, the opposite sides are parallel and equal. The area of any parallelogram is equal to the length of any side multiplied with the perpendicular distance between this side and its opposite side. A line passing through any two distinct point $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$ where $$$x_1!=x_2$$$ or $$$y_1!=y_2$$$ then it can be represented by ax+by=c where $$$a=(y_2-y_1)$$$, $$$b=(x_1-x_2)$$$ and $$$c=x_1y_2 - x_2y_1$$$. Incase $$$b$$$ is negative we multiply $$$-1$$$ throughout the equation. We can also observe that the distance between $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$ is $$$\sqrt{a^2+b^2}$$$. The perpendicular distance between two parallel lines $$$ax+by=c_1$$$ and $$$ax+by=c_2$$$ is $$$\frac{|c_2-c_1|}{\sqrt{a^2+b^2}}$$$. Thus the area of the parallelogram would be $$$|c_2-c_1|$$$ since the line of the line would be $$$\sqrt{a^2+b^2}$$$. Thus the final answer would be maximum of $$$\max c - \min c$$$ for the parallel line formed by taking two points having equal distance. For implementation we take a map whose index is the pair of $$$a$$$ and $$$b$$$, and $$$b>=0$$$, the value stored would be a pair of maximum of $$$c$$$ and minimum of $$$c$$$ for the same $$$a$$$ and $$$b$$$. This would overall take $$$O(N^2 \log N)$$$. Finally we iterate over the map and take the maximum difference of $$$c$$$ for the same $$$a$$$ and $$$b$$$.

Las Vegas

Let us first sort all the coins in descending order of their values. The idea here is that as we iterate through the coins, we will maintain for each stack, the expected earnings that you will have when that stack is chosen for the next turn.

We start iterating through the coins sorted as above. Let us consider we are currently at the $$$i$$$-th coin, and let $$$val$$$ be its value and $$$s$$$ be the stack it belongs to. We calculate two things, the expected earnings when you start the game with this coin and when the employee starts the game with this coin.

So, let us try to calculate the case when we start with this coin. Note that the next turn belongs to the employee, so he will aim to choose the stack which gives the least earnings when he starts with that stack (and vice versa for the other case). This means we need to keep track of what will be the expected earnings for each stack $$$s'$$$, when you start with that stack – let it be $$$dp1_{s'}$$$, and when the employee starts with it – let it be $$$dp2_{s'}$$$.

Thus, when you start with this coin, your earnings will be the minimum of $$$dp2$$$ of all stacks plus $$$val$$$ itself. On the other hand, when the employee starts with the coin, your earnings will be the maximum of $$$dp1$$$ of all stacks plus $$$val$$$. Before moving on to the next coin though, we will need to update the values of $$$dp1_s$$$ and $$$dp2_s$$$. This is simple to do, if $$$sz$$$ is the size of the $$$s$$$-th stack then we only need to execute:

A Day With Griddy Grid

On the first look at the problem we can notice some things like constraints of the problem are low, we have to find if some answer is possible or not and in case it is possible what is the minimum number of steps. All these things are pointing to some flow algorithm. Another thing to notice: If we consider the sum of cells at different parities their differences will always remain the same after any number of operations in any way. (Assuming parity of (i,j) cell= parity of (i+j) )

Let’s consider the case if n*m is even:

It means the number of cells with odd parity and even parity are the same. This implies that the sum of odd parity should be equal to odd parity, otherwise there is no possible way to make all cells equal.

In case sums are equal. Let’s solve the problem if we know the final number on all cells to check if it is a feasible solution. Now this is an easy max-flow problem. Just make a bipartite graph and put cells with odd parity on the left side and cells with even parity on the right side. Put edge from source to left side nodes with capacity equal to their initial values given by array ‘a’. Put edge from right side nodes to sink with capacity equal to their initial values given by array ‘a’. Put edges between adjacent nodes from left side to right side with infinite capacity. Find max flow in this graph if flow is equal to the sum of cells with any parity(both are equal). Then the given answer is feasible else not. We can also make another observation that if x is a possible answer then x+1,x+2… All are possible (can be proven easily). So we can just do a simple binary search on the answer to use the max-flow algorithm to check feasibility.

Let’s consider the case if n*m is odd:

The number of cells with odd parity + 1 = Number of cells with even parity. If x is possible number finally then difference between even and odd cells should be x initially else there will not be any possible way to make all cells equal. So we just have to check the feasibility of value of their differences using max-flow method as described above.

As the graph is bipartite we can use any fast algorithm to find max flow like Hopcroft, Dinics.

Complexity of flow = $$$E\sqrt V$$$, where $$$E$$$ is number of edges and $$$V$$$ is number of vertices. As, $$$E=O(nm)$$$ and $$$V=O(nm)$$$, complexity of algorithm is $$$\log A(i,j)*\text{flow_complexity}$$$.