### dnshgyl21's blog

By dnshgyl21, history, 18 months ago,

Solution

Hint
Solution

Hint
Solution

Hint 1
Hint 2
Solution

Hint
Solution

## F. The Evil Company

Hint 1
Solution
• +29

By dnshgyl21, 19 months ago,

Solution

Solution
Code

Hint 1
Solution

Solution

Solution

#### F. The Weirwood

Hint 1
Hint 2
Hint 3
Hint 4
Solution
• +8

By dnshgyl21, 23 months ago,

Solution

Solution

Solution

Solution

Solution

#### F. Grid And Paths

Solution
• +11

By dnshgyl21, history, 2 years ago,

Credits: _deactivated_, dnshgyl21, Sawarnik, Xzirium

Solution

#### B. ABBA

We solve this problem in cases:

Firstly, we take the case where all the characters of the string are either ‘a’ or ‘b’. For this do not require to perform any operations as every character of the string is equal.

Secondly, we take the case where ‘a’ and ‘b’ both exist at least once. Here we can either make all the characters ‘a’ or ‘b’. We try to calculate the minimum operations required to make all characters ‘a’. We also observe that there exists a character ‘b’ with adjacent character ‘a’ since ‘a’ and ‘b’ both exist at least once. We convert this ‘b’ to ‘a’ with an operation. Again if there exist ‘b’ then by similar argument we can perform this operation. We repeatedly perform this operation until all the characters become ‘a’. The number of operation would be number of ‘b’ characters. Similarly, in order to make all the characters of the string ‘b’ the number of operation would be number of ‘a’ characters. Therefore the final answer would be the minimum of these two.

Hint 1
Hint 2
Solution

Hint
Solution

#### E. XOR

To solve this problem we need few observations, Observation # 1: Value(A,B) = Value(Root,A) Xor Value (Root,B) We can write any value of any path in the following way. Observation #2: If we solve the problem for any single bit of binary format then for existence of unique value every bit should give a unique answer. On the other hand if any bit will give invalid answer then overall answer will not exist. If answer is valid for all bits and for atleast one bit multiple answer exists then overall answer will be multiple. So problem can be modified in this way. Let’s solve for any single bit.

Assume Ans(A) = Value(Root,A) for any single bit. Where Ans(Root)=0, we have just taken it in this way to reduce confusion while solving modified problem. For any query of path if Value(A,B)=0 then Ans(A) should be equal to Ans(B) again mentioning we are solving it for any single bit. And if in case Value(A,B)=1 then Ans(A) should be different from Ans(B).

So above problem can be seen as simple 2-sat problem. For more details about 2-sat: https://cp-algorithms.com/graph/2SAT.html After solving for each bit we can see if any answer exists or not and if exists then it is unique or not. If unique answer exists we can find exact answer by using 2 sat. Complexity = O((n+m)logn) As we are solving for each bit individually that’s why logn factor came. And for each bit while doing 2 sat we are iterating over all edges and nodes that’s why O(n+m) factor came.

#### F. Lets Count

Lets first begin by solving an easier problem, where the constraint on h and w were upto 20.

In this case we can proceed via inclusion and exclusion. For this define R constraint each corresponding to the given rectangle, which indicates that the min inside this given rectangle is exactly equal to the given value. Like in inclusion exclusion, we can define the violation for a given rectangle to be that the minimum is strictly greater than the given v.

Now if we decide which of the rectangles are causing violation, like in the case of inclusion exclusion, we can go though all the rectangle and all the position and grid, and update the value to be the max value over all possible rectangles, and then simple take the product of values across all the grid cells.

Now looping through all subsets of violation, our answer simply becomes

Ans = Summation over subsets of violation( No of ways considering these are violated)

Now in the general case where h and w are large, we can see that we can simply compress the coordinate so that the size of the grid becomes small, and then we can process as above.

• +28

By dnshgyl21, history, 2 years ago,

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:

$dp1_s += \frac{\min dp2 + \text{val}}{sz}$
$dp2_s += \frac{\max dp1 + \text{val}}{sz}$

#### 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}$.

• +22

By dnshgyl21, history, 3 years ago,

Purpose of the blog is that how people feel about possibility of Div 1 Educational Rounds.

Many people really like Educational Rounds. As these rounds include more conceptual problems rather than ad-hoc or some difficult pattern observation problems. Now a days most of Div 2 educational rounds have only (F,G) time taking or some thinking, other problems are too standard.

So I think if there are majority of people also who like this idea admins can consider Div 1 Educational rounds also. :)