Hello everyone! I would like to invite you to participate in HackerEarth HourStorm #2. It’s the second version of a short contest, that runs for 1 hour! The problem set consists of 3 traditional algorithmic tasks of various difficulties. The contest starts on the 11th of August i.e today at 9.30- PM IST

For traditional algorithmic tasks, you will receive points for every test case your solution passes — so you can get some points with partial solutions as well. Check contest page for more details about in-contest schedule and rules.

send_nodes and I have worked on the preparation of the contest. As usual, there will be some prizes for the top three competitors:

$75 Amazon gift card
$50 Amazon gift card
$25 Amazon gift card

In addition, top 5 on the scoreboard with rating less than 1600 will win HackerEarth t-shirts. The problems are on the easier side, giving everybody a fair shot at taking home the prizes. Good luck to everyone, and let's discuss the problems after the contest!

Note that the contest begins after the end of the CF Round.

Update : The contest begins in 15 minutes

Hello Codeforces. Today I'm writing about a Math topic that is really simple, but resources are limited.

SLAE stands for system of linear algebraic equations. Basically, consider we have a set of equations of the form :

a₀·x₀ + a₁·x₁ + a₂·x₂ + ... + a_n - 1·x_n - 1 = val₀

b₀·x₀ + b₁·x₁ + b₂·x₂ + .... + b_n - 1·x_n - 1 = val₁

c₀·x₀ + c₁·x₁ + c₂·x₂ + .... + c_n - 1·x_n - 1 = val₂

.....

Note that all a, b, c... are real-valued arrays and all val_i, x_i are arbitrary reals. Realize how x₀, x₁, ...x_n - 1 appear in each of the equations. In the post below, it is assumed we are dealing with reals, and not only integers.

Now, we want to find values of [x₀, x₁...x_n - 1] that satisfy each of the given equations listed, given all a, b, c... and val_i. The simplest method to find such solutions is to use Gaussian Elimination, that solves the problem in O(N³), where N = number of equations = number of variables .

To Learn about Gaussian Elimination, click here. Today, we shall learn about 2 special class of problems that can be solved using Gaussian Elimination.

Problem 1 : Markov Chains and Cyclic Expected Values :

Pre-requisite : Gaussian-Elimination, Expectation of a random variable.

Many a times as a part of expected value problems, you are expected to sum up infinite series that hold as limits, as probabilities lie in the closed interval [0, 1]. For example,

, as

However, not always can we expect the variables whose Expected value we need to calculate to be independent. Consider you have N random variables , where , there are cyclic dependencies among the variables for their expected values, i.e consider depends on , on and depends on . So, there exists an infinite loop for calculating the Expected values of the random variables.

For example, consider the following problem :

You are given Tree T consisting of N nodes. Initially there is a player in node S. In a single move, he moves to one of the adjacent nodes of the node he is currently at, each with equal probability. What is the expected number of moves before he reaches node T ?.

Here, we need to understand that the expected values are infinite sums as well as cyclic. Creating a simple formula for the answer is quite hard. The Expected value starting from node S depends on some neighbor of node S, however, the Expected value of some neighbor of node S depends on Expected value of node S. Notice that whenever we reach a particular node, the probability of moving to any other node regardless of the number of steps performed always remains the same. So, this is a Markov Chain. Let's consider the transition matrix of this chain.

Create a matrix P, where P[i][j]= probability of moving from node i to j in a single move. Now, Let denote the expected number of steps needed to reach node T from node i.

.

Try and take a moment and think about why this formula is correct.

Surprise Surprise, this can be modeled as SLAE. Rewrite equations as :

. So the system is :

\begin{equation} \begin{pmatrix} 1-P[0][0] & -P[0][1] & ... & -P[0][N-1] \newline -P[1][0] & 1-P[1][1] & ... & -P[1][N-1] \newline .... \newline -P[N-1][0] & -P[N-1][1] & ... & 1-P[N-1][N-1] \end{pmatrix} \cdot \begin{pmatrix} \mathbb E(0) \newline \mathbb E(1) \newline .. \newline .. \newline \mathbb E(n-1) \end{pmatrix} = \begin{pmatrix} 1 \newline 1 \newline .. \newline 1 \end{pmatrix} \end{equation}

This is the equation (I_N - P)·E = 1, We need to find the column vector E. Note that for node T, we need to have P[t][i] = 0, t ≠ i and P[t][t] = 1, as we won't move from node T, it is an absorbent state of the Markov chain. So, the T^th row of matrix I_N - P will be all zeros. Also, the equation does not hold true for node T. Also, we know . So, the part does not affect any of the equations. So, just remove the T^th row and column from both sides of the equation.

The matrix is now a square (N - 1)·(N - 1) matrix, that is invertible. Invert the matrix using Gaussian Elimination augmenting with the RHS, to obtain E, i.e.

We can use this generic technique in all cases where the expected values are cyclic in nature , i.e expected value of state A depends on state B, and expected value of state B depends on state A. We can use any prime mod too, to obtain expected value in Modulo. Just remember : dependent random variables, use this. Practice Problems :

One (Same problem as above) My Code

Two

Problem 2 : Xor's using SLAE

Pr-requisite : Vector Space properties, Linear Algebra.

mod 2

mod 2

mod 2

So, xor is just bit-wise addition mod 2. We can represent the xor of two integer's x, y as vector addition in . For example ,

i.e. ,

\begin{equation} \begin{pmatrix} 0 \newline 1 \newline 0 \end{pmatrix} + \begin{pmatrix} 1 \newline 1 \newline 1 \end{pmatrix} \equiv \begin{pmatrix} 1 \newline 0 \newline 1 \end{pmatrix}
Mod \space 2
\end{equation}

So, we can use this addition to replace xor.The main advantage of this scheme is that we have converted the subset xor problem to solving a linear system instead. Consider we want to find a, b, c such that:

a·v1 + b·v2 + c·v3 ≡ x Mod 2, given v1, v2, v3 and x. Here v1, v2, v3, x are arbitrary binary column vectors. This is equivalent to solving the linear system :

\begin{equation} \begin{pmatrix} v1 & v2 & v3 \end{pmatrix} \cdot \begin{pmatrix} a \newline b \newline c \end{pmatrix} \equiv x \hspace{0.2cm} Mod \hspace{0.2cm} 2 \end{equation}.

Since a, b, c can only belong to {0, 1}, this is precisely finding a solution to subset xor.

Note that the span of any given set of size N is a vector space. There is a concept called as Basis of a vector space , i.e a smallest size subset of a given set that spans the entire vector space spanned by the original set given. We can solve the same problem over smaller sized basis rather than using all the elements of the set.

Via the Basis, we can solve useful xor based problems such as :

1> Given a set S of size N, find the number of distinct integers that can be represented using xor over the set of the given elements.

2> How many sub sequences of a given set S of size N have xor equal to X. (Do it yourself).

3> What is the maximum possible xor you can have using a subset of a given set :

All of these problems can be modeled using SLAE in Mod 2. We can do operations faster in Mod 2 using bitset having complexity .

Problems :

One

Two

This is my first time wiring a tutorial blog, so please excuse any minor mistakes. Please give you feedback, it is always useful. Thank You.

Hi, good day to U'll.

I have the following equation :

 = 

Can you help me with a proof for this ? BTW, this relates to the last part of the following problem : Link. The editorial for the problem tells us to convert the lhs to the rhs w/o any proof or explanation on how it is obtained. Any help would be useful

Thank You

Hello,

Today, I was trying to solve this problem. The Dp behind this problem is not very difficult and is not the tricky part of the problem according to me.

The part that I have completely failed to to understand in this problem is where we are required to calculate ( Pi * 1000^2N%(1e9 + 7)). The author meintions in the problem statement that this (( Pi * 1000^2N%(1e9 + 7))) is guaranteed to be an integer.

Can somebody please provide me a proof of this or just simplify the formula ? I have complete idea about how to approach this problem with doubles without Modulo, but have no idea about doing this with the formula above. How do I calculate the probability  * 1000^2N%(1e9 + 7) ? Help !

Hey Guys, I've been trying for a long time to solve this question Watto and Mechinism using a Trie. I know this task can be accomplished using hashing too, but I need help with a Trie based solution so that I can understand Tries better.

Now, I Have written a solution in Java almost identical to another solution that has been written in C++. The C++ based soltuion gets an AC, whereas I keep getting TLE on test case 33. The AC code does not belong to me and I've used it only for learning purpose . I have completely been unable to understand what I have done different My Submission from this one . Please help me with this. What am I doing wrong or different from the AC solution here.??

Hello friends.. For the Past few Days I have been studying about Segment Trees and Binary Indexed Trees. I have noticed a few subtle differences among them ..I'm listing them below..Please let me know if I've gone wrong somewhere..

1> Binary Indexed Trees can be used for range queries when the array size is huge..>2*10^7 and above whereas segment trees can't be used for the same... 2> Binary Indexed Trees are more efficient for point sum/point update type of sums..Eg https://www.codechef.com/problems/SPREAD .I could't solve this problem using a segment tree with fast I/O with lazy prop..but with BIT I got AC... 3>Segment Trees can be used for a wider variety of problems such as RMQ, Sum, Square Sum, Frequency Table etc.

-Please comment....