[Tutorial] SquareRoot Decomposition + Dynamic Programming in Competitive Programming

Hi guys! ✋

rachit jain blog, Rachit Jain, rachit jain iit roorkee, rachit jain iitr, rachit iitr,rachit codechef, rachit hackerrank, rachit jain microsoft

You are going to learn how Square Root Decomposition and DP can be mixed to generate harder problems.

This is an awesome math problem on Matrices. It is based on DP + Data Structures(Fenwick Tree/SquareRoot Decomposition). Its a counting problem from CSAcademy Junior Challenge 2017.

Problem Link is here.   

You are given a matrix $M$ with $N,M( \le 2000)$ rows and columns, and you have to count the no of special square submatrices. A square matrix is special if it has all $1s$ on its borders and principal diagonal(top-left to bottom-right). The rest of the matrix can be filled with either $0s$ and $1s$.  

In beginning, the problem seems to be solvable using only DP, but the solution is simply mind-blowing, jaw-dropping and beautiful.  

The trick here is to iterate on diagonals which are $O(N+M)$ in number. Then for each diagonal, count the number of special square submatrices that lie on current diaognal i.e their principal diagonal lies on the current diagonal that we are iterating. 

Lets pick any two points on the diagonal that we are currently at. 

Using DP, we do some preprocessing. Then the question is transformed to given two arrays $L,R$, find the number of pairs $(i, j)$ such that following 3 conditions are met:   

1. $i\le j$ 

2. $L_j \le i$

3. $R_i \ge j$  

We iterate on $j$, and use square root decomposition to solve this problem :)

The video tutorial is divided into 2 parts: 

1. Part1: Approaching the problem and building our solution

2. Part2: The Square Root Decomposition part

Refer the Video Description to find the links to problem link and other relevant information.

If you liked my efforts, please hit the like button 👍, subscribe and share the videos among your college :D  

Have a good day! 😆

An Interesting Math + Data Structure Problem from Codeforces (Round #430)

Hi guys! ✋

rachit jain blog, Rachit Jain, rachit jain iit roorkee, rachit jain iitr, rachit iitr,rachit codechef, rachit hackerrank, rachit jain microsoft

This is a data structure(TRIE) + math based problem from Codeforces Round #430.
Problem Link is here.   
You are given an array $A$ of size $N$, and you have to perform $M$ operations on it.  
In each operation, you are given an integer $x$, and you perform XOR operation of every element of the array with $x$. Note that the array is updated after every operation and subsequent operations are performed on modified array. At end of every operation, you need to print the mex value of the updated array.     

NOTE: mex of a set $A$ is the least whole number ( $\ge 0$ ) which is not present in $A$.    

Check out the following video where I've described the solution:
CodeForces Round 430 - Problem D Tutorial (Number Theory, Trie)

Refer the Video Description to find the links to source code and problem link.

If you liked my efforts, please hit the like button 👍, subscribe and share the videos among your college :D  

Have a good day! 😆

An Interesting Number Theory Problem from CSAcademy(Round #43)

Hi guys! ✋

rachit jain blog, Rachit Jain, rachit jain iit roorkee, rachit jain iitr, rachit iitr,rachit codechef, rachit hackerrank, rachit jain microsoft

This is a greedy, math problem from CSAcademy Round #43.
You are given two integers $N,K$ and you are required to print an array of $N$ distinct integers $<10^6$ such that there are exactly $K$ pairs $(a[i], a[j])$ with their gcd as $1$.  

Check out the following video where I've described the solution:
CSAcademy Round 43 - Coprime Pairs Tutorial (Number Theory)

Refer the Video Description to find the links to source code and problem link.

The family 💓 has grown to 600+ subscribers and I thank you guys for the love and support :)  

If you liked my efforts, please hit the like button 👍, subscribe and share the videos among your college :D  

Have a good day! 😆

YouTube Playlist for Dynamic Programming

Hi guys! ✋

rachit jain blog, Rachit Jain, rachit jain iit roorkee, rachit jain iitr, rachit iitr,rachit codechef, rachit hackerrank, rachit jain microsoft

I am happy to launch the YouTube playlist for Dynamic Programming: From Zero to Hero.    

I've put in a lot of my efforts this time, kept the video detailed so that a lot of people (beginners for sure) are able to understand:
1. How to approach problems based on Dynamic Programming?
2. How to think of DP states?
3. How to build the DP recurrence relations?
4. Can DP problem be solved faster using MATRIX EXPONENTIATION? ✌

Beginners will surely learn a lot, lot, lot from this. 

Check out the following videos:
1. Intro to DP: How to approach DP states, Recurrences 
2. Dynamic Programming + Matrix Exponentiation

Check the Video Description to find the links to source code and problem link.

Finally, the family 💓 has grown to 500+ subscribers and I thank you guys for the love and support :)  

If you liked my efforts, please hit the like button 👍, subscribe and share the videos among your college :D  

Have a good day! 😆

Video Tutorial For a SquareRoot Decomposition Problem - HILLJUMPING

rachit jain blog, Rachit Jain, rachit jain iit roorkee, rachit jain iitr, rachit iitr,rachit codechef, rachit hackerrank, rachit jain microsoft

Hi

I've put in a lot of my efforts this time, kept the video detailed so that a lot of people including beginners are able to understand how to solve this tough squareroot decomposition problem HILLJUMPING from Codechef August 17 Long Challenge.

You can learn about SquareRoot Decomposition, binary search, and how a simple and beautiful solution is built up, starting from scratch :D

Beginners will surely learn a lot, lot, lot from this. 

Check out the video editorial here.
Check the Video Description to find the links to source code and problem link.

If you do not want the problem description, skip to 3:25
Then I explain my approach till 14:50 after which code discussion begins.

Also, YouTube decreased the volume level after upload. So please use headfones, and if any of you
has a solution to this, let me know!

My YouTube Channel for Competitive Programming

rachit jain blog, Rachit Jain, rachit jain iit roorkee, rachit jain iitr, rachit iitr,rachit codechef, rachit hackerrank, rachit jain microsoft

My very own YouTube Channel

Tags: video-tutorials,YouTube,data-structures, algorithms

Hi everybody,

I've finally launched my very own YouTube Channel here.

Its a kind request to LIKE the video if it helped you. 
This is important for me as more likes builds a trust for future viewers :)

At present, I plan to upload my video screencasts of online contests and video tutorials of some interesting programming problems that I encounter during daily online contests.

The pattern each video follows is:  
1. Problem Description  
2. Explanation/Solution  
3. Code Implementation/Discussion      

As a beginner, I was a bit slow while talking and I request all of you to watch the videos at 1.25x or 1.5x speed for better experience.

To begin off, I've covered some problems from the [Codechef August Long Challenge](https://www.codechef.com/AUG17).

1. [Palindromic Game] (Analysis based, medium)  
=> Video Link 

2. [Chef and Fibonacci Array] (Medium DP)
=> Video Link 

3. [Strings and Graphs] (Interesting analysis, medium-hard)  
=> Video Link

Video for Hill Jumping will be coming soon :)  
EDIT: Here is the video editorial for Hill Jumping.

Why should you subscribe to this channel:
1. You couldn't solve problems I make videos about: majorly covers beginners and intermediate level coders.    
2. You face difficulty in understanding the text editorial.  
3. You enjoy solving difficult yet interesting problems.
4. You really wanted some YouTube channel that talks about problems based on data structures and algorithms, and discuss how they can be solved.  

I hope this will help many people. Please subscribe and like the videos if you found them helpful.
Comment if you face any difficulties or if you have any recommendations for me.

With my common sense and your feedback, I hope the future videos will be of much greater quality :)  

Have a good day!

Tips for How to Prepare for Placement Interviews

rachit jain blog, Rachit Jain, rachit jain iit roorkee, rachit jain iitr, rachit iitr,rachit codechef, rachit hackerrank, rachit jain microsoft

Tags: placement, interviews, data-structures, algorithms

Hi! Today I will write about some tips, tricks and hacks I have found from my experience in attempting recruitment tests, interviews.

I will begin by giving a brief introduction about myself.
I have done B. Tech. in Electrical Engineering from IIT Roorkee. I have graduated 2 months back, and now working in Microsoft for over a month.

I started off competitive programming in 2-2(2nd Year 2nd Semester). So I had around 1.5 years of experience in competitive programming while I was sitting for placement tests. Having a strong background in competitive programming really saves your ass while others keep reading geeksforgeeks to prepare themselves.

How to crack the interviews and get a decent job?
So, the organizations will be coming in many colleges soon, and conduct their shortlisting tests.
Now, I will be talking very short and to the point. Each point is important.

Basic Skill Set (BSS): 
1. Quick implementation & debugging (practise questions on codeforces, hackerrank, participate in contests)
2. String Matching (important, KMP, Z-Algorithm, etc)
3. Binary Search, Sorting, STL (sets, maps, unordered set/map, vector, sort) - very very very useful
4. Data Structures - (Linked Lists, stacks, queues, BIT useful, Segment Tree - asked in Google)
5. Dynamic Programming - very very important (medium level problems, all companies ask)
6. Binary Trees & BST - super important! (All companies ask this)
7. DFS/BFS questions on Graphs (Dijsktra and flows are rarely asked)
8. DP on Trees (yes, an important topic)
9. Greedy, Backtracking - (Important, can be tricky)
10. Math Concepts like Prime Seive - Not that much important
11. Bitmask DP - sometimes asked in interviews, cover it later.

I think this is enough for cracking through most of the recruitment tests. Though there are always many other topics that can be covered, but I would suggest don't get overwhelmed and focus on these first. Once you are ready with these basics, you should move on to study other Data Structures and Algorithms. Knowing more and in detail will always make you more interesting and awesome.

Many recruitment problems are based on usages of sets, maps.
Do many practise problems based on them. Eg: see this, and the solution.

People who don't do CP should immediately do the following:
1. Need to improve implementation, debugging skills.
2. Learn the basic set of data structures and algorithms as mentioned above.
3. Begin by doing all 37 problems on GeeksForGeeks under array category.
4. Move on to DP on GeeksForGeeks.
5. For sets, maps I think problems on CodeForces like I mentioned above will be better.
6. Cover other topics like greedy, dfs/bfs from GeeksForGeeks.
7. Linked list, binary trees and their traversals. (Important!)

This should take around 2 weeks. I don't think people who are consistently doing CP would face the need of doing linked list, stacks, etc from geeksforgeeks. But its good if you give it a fast skimming read.

What next?
Now start off at interviewbit and solve problems there so that you familiarize yourself with verdicts like WA, AC, etc and also how to respond in case of TLE or WA. This will improve your implementation and debugging skills. This will clearly help you understand the various concepts like DP, trees, etc.

You must also participate in the ongoing challenges on sites like Codechef, Codeforces, Hackerrank, etc.

Once you are stable blue on CF around 1700, you can easily clear the recruitment tests. Then all you have to do is brush up your explanation skills so that you can clear the interview rounds too.

NOTE: Speed is important. Many times people fail by 10-15 mins to implement the algorithm correctly. This will really turn you off. So keep practicing everyday!

Tips for recruitment tests:
1. Be fast. Don't just keep on waiting for finding the solution.
2. If stuck on problem, proceed to next. First solve all of those that are easy.
3. At the end, ALWAYS submit the worst brute force solution with no matter what complexity. YES! The test cases are many times weak, and you get pretty high score.
4. You must be familiar with Python inbuilt functions involving combinatorics, permutations and string functionalities too. It can prove to be very beneficial ;)
5. This tip is more of a personal experience. In one of the test, I was getting only a score of 25. I soon realized that the  for loop conditions weren't true and I was simply printing 0. When I corrected it, I got a score of 75. Yes! so I had to basically see that if I am getting a WA in some test case, I need to print 0 there. Finally I used binary search on the values of variables(size of array, first element of array) to identify those test cases, and simply print 0. Basically what I did was used an infinite while loop with some condition like $100<n$ and $n<500$ so that I get the verdict TLE, and I am able to figure out those test cases where I was getting WA.


Tips for interviews:
1. Be humble. Don't give the slightest vibes of overconfidence or arrogance.
2. Never give up. If the problem asked seems difficult at first sight, don't lose out confidence. See what is given, what you have to find, and try doing it for small test cases. Then maybe you will find a pattern.
3. Speak as you think. Don't just keep scribbling on paper. Let the interviewer know about how you are approaching the problem.
4. If problem seems difficult, give the brute force solution and its complexity. Then try optimizing it, maybe using dynamic programming or some greedy solution.

Don't think you don't have time :D
Just start doing already!
Feel free to write your queries, I am always there to help :)

An Interesting Problem On Array Conversion [AtCoder]

rachit jain blog, Rachit Jain, rachit jain iit roorkee, rachit jain iitr, rachit iitr,rachit codechef, rachit hackerrank, rachit jain microsoft

Tags: directed-graphs, hamiltonian paths..

Today, I will talk about a problem from Atcoder.  
You are given 2 arrays A,B. You need to tell the minimum no of moves to convert A into B. In each move, you replace any A[i] by the xor of all elements in A. If its not possible to convert A to B, print -1.

Let us use 1-based indexing.
Now, place xor(A) at position 0. Then the move is basically swapping numbers at position 0 and some arbitrary position i.
So answer will only exist if both multisets of A, B (after including the xor of whole array) are same.

You can refer to editorial given at AtCoder, but I find my approach a bit easier to understand, though they are more or less the same thing.

So, in each move we swap a number $x$ at position $0$ with a number $y$ at position $i$.
Let this be represented by a directed edge from $x$ to $y$. Then, in next move, we will swap $y$ with some $z$, then $z$ with blabla... and finally swap some blabla with $b[0]$.

Isn't this a Hamiltonian Path from $a[0]$ to $b[0]$?

Note that a directed edge from $x$ to $y$ means that the correct position of $x$ is actually the position of $y$ in $A$.
$x→y$ means $x$ is at 0 position, and we place it at position of $y$, and bring $y$ to position $0$.
So an edge represents putting $x$ into its correct position, and then bringing $y$ to position $0$ so that we can place it in its correct position, and so on.

Consider an example,
A: [1, 3, 2]
B: [2, 1, 3]

Now using the available move option of swapping any element with first element, we need to transform array $A$ into $B$.

We perform 1→3 , $A$: [3,1,2]
We perform 3→2, $A$: [2,1,3]

You can see that the set of collection of edges denoting our operations are same as the set of collection of edges {b[i]→a[i] , 0 $\le i \le n$}
This is because for given $a[0]$, and let its position in $B$ be $i$, then we basically swap the numbers at position $0$ and $i$. Thus, the edge $a[0]→a[i]$ is exactly represented by $b[i]→a[i]$.

Now, $B$ is nothing but a permutation of $A$, and our edges are $b[i]→a[i]$. This is a standard thing that we often see in the world of competitive programming. The resultant graph is basically a forest of cycles.

Now since we want a hamiltonian path from $a[0]$ to $b[0]$, we obviously need connectivity. For all cycles that aren't a part of $a[0]$ we will have to break down and re-edit their edges a little bit so that those cycles will also contain $a[0]$ as an element in it.

If you didn't understand what I said above, try converting [1,3,2,7,8,9] to [2,1,3,9,7,8] by using move operation of swapping elements at position 0 and some arbitrary position $i$.

In terms of math, let $C$ be a cycle that doesn't yet have $a[0]$ as a member in it. (For eg: in above example, $7→8→9→7$ is a cycle that doesn't include a[0] i.e 1). Pick two consecutive edges from $C$, $x→y$ and $y→z$.
This means that when $x$ comes at pos $0$, we put it at position of $y$,
and then put $y$ at position of $z$.
Now see what happens when we swap $a[0]$ with $y$. Now $y$ comes at position $0$, and its destination position is still the position of $z$.
But destination position of $x$ is now the position of $a[0]$ after swap as it took the place of $y$.
And finally $a[0]$ has to come back to position $0$ , so destination position of $a[0]$ now becomes position of $y$.
So the new edges are $x→a[0]$, $a[0]→y$ and $y→z$. So $a[0]$ is successfully inserted into the cycle $C$ at the cost of one additional edge.

NOTE:
Bringing $a[0]$ into the cycle was necessary because our move operation allows us to swap any number with the number at position $0$. So once we get $a[0]$, we can apply the operation again and again i.e traverse the edges until the cycle is completed and all numbers are placed at their correct position.  

I hope this opens up your mind a bit. You now have the tools needed. I will recommend you to play around with it, consider a few examples, make the graphs, see how things are functioning.

Finally here is the AC code.

Introduction to a New Data Structure: WAVELET TREES

Wavelet Trees, Wavelet trees editorial, wavelet trees tutorial, wavelet tree rachit jain, Rachit Jain, rachit jain iit roorkee, rachit iitr, rachit jain iitr,rachit codechef, rachit hackerrank, rachit jain microsoft

Wavelet Trees
Tags: data-structures, wavelet-trees

Today, I will talk about a new data structure: Wavelet Trees.  
I read about them around a week back, and can't find the exact link where this was in discussion.

Anyway, you can read about it from this paper. It's something really powerful, easy to code, and perhaps very new to competitive programming(I haven't heard about it in my experience of 2 years).

Consider the following problems, and how I would have solved them normally:
1. Number of elements in subarray $A[L...R]$ that are less than or equal to $y$.
(Persistence Segment Tree?)
2. Number of occurrences of element $x$ in subarray $A[L...R]$.
(Subpart of 1st problem)
3. The $k^{th}$ smallest element in subarray $A[L...R]$.
(Ordered multiset + BIT would work for subarrays beginning from index 1)

I know you might have many other solutions, and you might think what I am trying to prove.

What if I told you, all of the above can be easily done in O(logn) using Wavelet Trees :o.  Plus, its very easy to code :D Awesome, isn't it?

I will be covering only range queries today that are mentioned above. There are some update queries too, that I might post in the coming posts.

Okay, so I will be explaining what a wavelet tree is, and how we use it for finding the $k^{th}$ smallest number in any given subarray $A[L...R]$.

TUTORIAL
I will strongly recommend you to read section 2(around 4 pages) from the above paper. If really lazy, read just 2.5 pages beginning from section 2, and you will get a fair idea of what I am talking below.

So wavelet trees are binary trees, where root node is represented by original array $A$ and the range $[lo, hi]$ in which the elements of array falls.
Let $mid=(lo+hi)/2$
Now, we partition(stable i.e the order of elements do not change) the array $A$ into two parts such that the left part contains all numbers that are $\le mid$, and right part contains all numbers that are $>mid$.
This is something similar to what we do in quicksort. Isn't it?
The range for left part becomes $[lo, mid]$ and for right part becomes $[mid+1, hi]$.

We keep on doing this recursively for left and right parts, so the height of tree will be $O(log(max(A)))$.

You can open the code and refer it as you read all of this.

So for every node $U$ of tree, we have the range $[lo, hi]$ in which its element lies and its array $S[U]$ represents a subsequence of original array.
For every node $U$, we will have a vector $b$ such that $b[i]$ tells us the number of elements from first $i$ elements of $S[U]$ that are $\le mid$. i.e it represents how many elements from first $i$ elements will go to the left subtree of $U$.
We can safely say that $(i-b[i])$ from first $i$ elements will go to right subtree.

Now, the most awesome thing is that elements in subarray $[l, r]$ of $S[U]$ are exactly divided into the left and right subtrees of $U$ depending on whether the element is less than or greater than mid value.

Okay, I will explain a bit more in detail.
Let's consider the subarray of type $[1...R]$.
Now $b[R]$ represents the number of elements that go to left subtree of $U$.
The rest $(R-b[R])$ nos go to right subtree of $U$.
So, we can query the present subarray $[1...R]$ by querying the starting $b[R]$ elements of left subtree and first $(R-b[R])$ elements of right subtree.

When we want to do same thing on general subarrays $[L...R]$, we can see that $b[L-1]$ nos go to left subtree from first $(L-1)$ elements, and $b[R]$ nos go to left from first $R$ elements. This means that those elements in range $[L...R]$ that go to left are exactly represented by nos from position $(b[L-1]+1)$ to $b[R]$  in the left subtree.

Kth Smallest Element in subarray [L...R]

So, if the query is find Kth smallest element in subarray $[L...R]$, lets begin from the root.
Now, $inLeft = (b[R] - b[L-1])$ gives the number of elements from subarray $[L...R]$ that go to left subtree. If this number is more than $K$, then we recursively go to left subtree. 

Otherwise, we go recursively to right subtree and find the $(K-inLeft)$ smallest element in that.  

Clearly, the complexity is the height of tree i.e $O(log(maxValue))$.  

Refer this code for understanding the implementation and explanation mentioned above.

Finally, this is the complete code that solves all the 3 queries mentioned above. 

If you have any doubts, read the paper as mentioned (Section 2), and read the code for better understanding. If doubts still persist, write down below.  

Note that there can be space issues with Wavelet Trees if array elements value are around $10^9$. You can avoid them by using coordinate compression. Another approach is to use Wavelet Matrix(Section 4.2) in above paper.

PS: I am really sleepy, and not sure if there are any bugs. I don't think there are but still its better if you test them by submitting on some related problem.

A Superb Problem on Hashing + Queries on Array [CodeChef]

Rachit Jain, rachit jain blog, rachit jain iitr, rachit iit roorkee, rachit iitr, rachit codechef, rachit hackerrank, rachit jain microsoft

Today, I will talk about this June Challenge Problem from Codechef.

The beauty about the problem is the solution. I broke down the problem into subproblems, solved them, combined them. Though there exist multiple solutions, I think my solution is worth sharing. You can surely learn a lot of things from this ;)

The problem is: you are given an array, and in each query you receive two subarrays. You need to tell whether these subarrays are almost similar.

Two subarrays are almost similar if after you sort them both, there's atmost one mismatch.

So how do I do this in O(logn) per query? Or maybe O(1) ?
I was extremely puzzled how shall I carry this forward and build a solution.
Using hashing, I can compute hash value of any subarray in O(1) using partial sums.
But this only allows to compare whether two subarrays are IDENTICAL, and what we need is to allow a mismatch.

If you do not understand any of the following, take time and think. It will be clear.

So, here is what I did:
1. Compute the hash values of both subarrays: $h1,h2$
2. If they are equal, we are done.
3. Otherwise, let $val = |h1-h2|$  and let $x,y$ be the mismatched elements in two subarrays.
4. Then I computed xor of both subarrays. This gives us xor of $x$ and $y$.
5. This can never be zero, so there's a bit set in this. Otherwise, print NO. Let the bit set be $k^{th}$ bit.
6. I found the xor of both subarrays such that I only took those numbers into consideration whose $k^{th}$ bit is set. Let that be $v1,v2$ respectively.

Now xor of $v1, v2$ will exactly give us that value of one of $x,y$.  Think why this is true.
For now, let's assume we get the value $x$.
Then I check whether the resultant value ($x$)is present in a subarray or not. If it isn't present in any subarray, print NO.

We can find the other variable i.e $y$. How?
1. Let $hash[x]$ be the hashed value of numebr $x$.
2. Then the hash sum of other elements that are common to both, $com=h1-hash[x]$.
3. Then what is $tem=(h2-com)$?

$tem$ is the hashed value of element $y$. So we check in reverse map to see the corresponding number, and finally get the value of $y$. If there is no number present in reverse map, print NO.


Now we have successfully found the mismatch pair.  But we must keep in mind that if we have come this far, this doesn't mean the answer exist. The subarrays still might NOT be almost similar.
See this
$A=\{1,3,5\}$
$B=\{1,5,6\}$
The mismatch elements are $x=3,y=6$ as other elements are same. But once we sort them, their are more than 1 indices where a mismatch occurs. This is because the rank of mismatch pairs wasn't same.
Now only thing left is to check if the rank of $x$ in first subarray and rank of $y$ in second subarray is same. For this I used a bit with nodes being an ordered multiset.

I really felt so good after doing this.

Finally the AC code for this problem is here.

A Tricky DP Problem on Trees

Rachit Jain, rachit iit roorkee, rachit iitr, rachit codechef, rachit hackerrank, rachit jain microsoft

Tags: small-to-large trick, dp, trees

Not many programmers are aware of this "small-to-large" trick.  I've picked up this problem from CsAcademy Round 31: you are given a tree rooted at 1 where every node $i$ has some value, $val[i]$. You need to find the number of ways of selecting nodes so that the induced tree is uniform.
1. A uniform tree is one where for every node, its direct child have same value.
2. Induced tree from a subset of nodes $X$ is one where:
         a. There exists exactly one node that doesn't have any ancestor present in $X$.
         b. For every other node, its parent is its lowest ancestor that is present in $X$.

The DP solution is as follows:
Let dp[i][j] be the number of uniform forests(i.e it can be a single uniform tree, or a collection of uniform trees) that exist in the subtree of $i^{th}$ node such that the root of every tree in the forest has value $j$.
Now $dp[i][j] = \left(\prod_{x\in child[i]}(dp[x][j]+1)\right)-1$ , if we do not include node $i$
This is because from every child $x$, it can contribute forests with root value $j$ in $dp[x][j]$ ways, plus $1$ extra way, when we do not select any forest from $x^{th}$ child.
So we need to subtract $-1$ from the total because we have also counted a way where all the children of node $i$ contribute no forest.

Note that we can also include node $i$. This will add more ways in $dp[i][val[i]]$.

If this is not clear, think more by drawing on paper. Also you can refer to editorial here.

So this takes $O(n^2)$ time as well as space, and we need to do better.
Note that for given subtree of node $i$, if none of the nodes in its subtree has $v$ value, then $dp[i][v]$ will be $0$.
So we only iterate on the required values for given subtree using a map.

Now here is the small-to-large technique part. When we are combining all the values for childs of node $i$, we can do that in a smarter way. We always iterate on the smaller sized map, and put its entries in the larger sized map.
So whenever an item is being moved, it is always moved from smaller map to bigger map.
This makes the size of resultant map greater than twice the size of smaller map. So each item can be moved upto max of $log_2(n)$ times, and we have $N$ items in total (one value per node). So we get $O(NlogN)$ time complexity as well as space.

As usual, here is the code implementing the above idea.

I hope you've learnt a bit about this small-to-large technique.  This is another problem based on it.
You can compare my 2 solutions for the same: based on Mo's, based on small-to-large. See how shorter and cleaner the code becomes using this trick.

Comment if you have any doubts. I'm always ready to help.

A Hard Problem on Bit Logic

Rachit Jain, rachit iit roorkee, rachit iitr, rachit codechef, rachit hackerrank, rachit jain microsoft

Tags: bits, analysis, math, counting problem

This time, you will have a lot of fun. Get ready for some high level analysis! :D

So this is some mind-boggling, extremely beautiful problem from AtCoder: you are having a collection of natural numbers from $L$ to $R(<10^{18})$ inclusive, you want to count the number of unique elements you can obtain by performing OR operation to the collection of your numbers.
The approach I am mentioning below will not pass TL, but is something worth mentioning.

I have solved a similar problem on CsAcademy, with the only difference being:
1. We can use AND operation between the numbers from our collection.
2. The collection of numbers was having no pattern, unlike here where we have nos from $L$ to $R$.

Approach 1(Slow):
You might not understand this if you are unaware of SOS DP. Also this solution will cause TLE.
So you can SKIP this, otherwise you also learn one more technique.
We can form a number $X$, only if $res = OR_i(a_i)$ is same as $X$, where $a_i$ is a number from our collection which is a subset of $X$ i.e $X\&a_i=a_i$.  So if we perform OR operation on all such nos and the result is still not $X$, then unfortunately $X$ cannot be formed.
This can be done in $O(A)$ or $O(Alg(A))$, where $A=max(a_1,a_2,...,a_n)$.
How?
Simple DP:
Let dp[i][j] be the OR of all such elements that are subsets of $i$ and differ from $i$ in first $j$ bits.
Then,
if $j^{th}$ bit is set in $i$, $dp[i][j]=dp[i][j-1] | dp[i$^$(1<<j)][j-1]$
otherwise $dp[i][j]=dp[i][j-1]$

This is commonly known as SOS DP. If you didn't understand the above thing, see it from the link mentioned.
Here is the code for implementation above.
So this will not pass TL. We need to make use of the fact that in our problem we just don't have any numbers. We are given nos from $L$ to $R$.

Approach 2:  
The analysis is very beautiful and I really enjoyed solving this.
Let $r$ be the 1st bit from left where $A,B$ differ. So we can remove the bits before this from both $A,B$ as they won't affect our answer because no matter what nos we select in OR operation those bits will remain as it is, and thus have just 1 choice.
Now, $A<2^r\le B <2^{r+1}$
This equation is really very important as we will see later on.
Let $T=2^r$, and lets partition the nos from $A$ to $B$ into 2 sets:
$X=\{A,A+1,...,T-1\}$ and $Y=\{T,T+1,...,B\}$

1. Taking nos from only X:
We can obtain all nos from $A$ to $T-1$. That's it. We can't obtain higher nos as $T-1$ is already a bit sequence of all ones.

2. Taking nos from only Y:
This is interesting.
Note that  $T\le B <2^{r+1}$, so $T,B$ have same number of bits.
The highest bit set in both $T,B$ is $r$. Infact $T$ has only one bit set.
Let the next highest bit set in $B$ be $k$.
Now refer to the pic below.

We can trivially obtain all nos from $T$ to $B$. Point is how far can we go from $B$.
Now refer to the image on left and read the following.
The nos between $2^r$ and $2^r+2^k$ will be of form $1000*****$.
The shaded portion of length $k-1$ bits will have all permutations of $0$s and $1$s(from $0$ to $2^k-1$).
So we can set any pattern of $0$s and $1$s in the first $k-1$ bits of $B$ by suitable OR operations.
This enables us to obtain any number from $B$ to $2^r+2^{k+1}-1$.  Voila!

So in this case, we can obtain nos from $T$ to $2^r + 2^{k+1}-1$.

3. Taking nos from X and Y:
The min number thus obtained will be the OR of $A,T$ = $A+T=A+2^r$.
Note that $T$ just has a bit set at $r^{th}$ position, while all nos from $X$ have bits from $0$ to $r-1$.
$\therefore$, OR of $T=2^r$ with elements from $X$ will give us nos from $A+T$ to $T-1+T=2T-1$.
Well, this is the highest number that we can achieve as it is $2^{r+1}-1$ i.e all bits set to $1$. So we can't go any further.

Finally we have 3 segments, some of which may overlap. All that is left is to find the total length spanned by these segments.  Phew!

Here is the SMALL code implementing the above too BIG an idea.

I loved this problem very much and had a lot of fun writing the explanation for it.
Hope you have also learnt SOS DP trick incase you didn't know about it.
Feel free to ask comment below incase of any queries.

A Connectivity Problem on Directed Graph

Rachit Jain, rachit iit roorkee, rachit iitr, rachit codechef, rachit hackerrank, rachit jain microsoft

Tags: bitsets, graphs, SCC, connectivity

So the Hackerrank Codesprint 11 ended, and here is the question that I will talk about today: you are given a directed graph, and you will be given 2 types of queries: introduce a new node with an edge from/to the existing nodes, or answer whether there is a path from node $x_i$ to node $y_i$.

If it were a undirected graph, DSU would have nailed it.
Anyway, this is a standard technique used for connectivity in directed graphs.
As for now, forget the type of query that modifies the graph structure.
1. Find all the SCCs in the directed graph.
2. Form a new graph, a DAG by compressing the SCCs and adding edges between the SCCs.
3. Now for each SCC $A$, maintain the list$(reach[A])$ of all the SCCs it can reach.
4. For given nodes $x$ and $y$, there is a path from $x$ to $y$ iff the SCC component $Y$ is present in $reach[X]$, where $X,Y$ refer to the SCC that contain $x,y$ respectively.

Note that this takes $O(n^2)$ because of step $3$. We can do it faster by using BITSETS. Click the above link which excellently outshows the applications of bitsets in C++.
So we replace the list $reach[A]$ by the bitset $bit[A]$.

So we now do this in $O(\frac{N^2}{32})$. This is pretty fast to pass the TL.

Now notice that queries modifying the structure of graph won't affect our algorithm much.
We first build the complete graph and then finally answer the queries.
The only thing that one can worry about is that there might be some case for which the answer to present query is "No" but since we have built the complete graph, we might get a "Yes".
So if answer for $x,y$ is "No", then this means that till now there isn't a path from $x$ to $y$. Notice that as we continue to modify the graph, we always bring a NEW node inside the structure and it's never possible in this way to add a path from $x$ to $y$.  Wow!

As usual, here is the code implementing the above idea.
I've seen similar questions in past hackerrank contest too(can't recall it).
So I learnt that using bitsets is a standard technique for connectivity queries on directed graphs.

A Hard Combinatorics Problem

Rachit Jain, rachit iit roorkee, rachit iitr, rachit codechef, rachit hackerrank, rachit jain microsoft

Tags: math, combinatorics, DSU

Now, this is a really beautiful problem from AtCoder: you are given an array of $N$ balls and two numbers $X,Y$.   $col[i], w[i]$ represent the color and weight of $i^{th}$ ball respectively. You can swap two balls,$i$ and $j$ of same color  if $w[i]+w[j] \le X$; you can swap two balls,$i$ and $j$ of different color if $w[i]+w[j] \le Y$. You need to find the total number of distinct permutations of colors that you can obtain.

The solution is as follows:
The key concept is that if you can swap balls $A,B$ and balls $B,C$, then you can also swap $A,C$ regardless of the condition. Why?
1. Let the original position be $A ... B ... C$
2. Swap $A,B$ to obtain  $B ... A ... C$
3. Swap $B,C$ to obtain  $C ... A ... B$
4. Swap $A,B$ to obtain  $C ... B ... A$

Voila! You can simply swap $A,C$.  

This means that we need to make clusters of balls. A cluster contains balls that can be swapped into each other's position and the total answer would be the product of total permutations for each cluster of balls.  

So the only problem is to make clusters.  Each ball can be connected to $n-1$ other balls. So we have around $O(n^2)$ edges that we need to see and add. We need something faster.

Note that each edge can be of two types, connecting balls of: same color or different color.  We use DSU to add edges between the balls.  

1. If for every color $C$, we connect the lightest ball of  color $C$ to all the balls of same color which can be joined as per the rules, we completely incorporate all the edges of type that connect two balls of same color.  

2. Now we find the two balls of different colors and minimum weight: let them be A,B.

3. Connect all the balls of color different from $col[A]$ to $A$ if we can connect them.  

4. Now connect balls with color same as $col[A]$ to $B$ if we can connect them.   

Each step takes $O(n)$ time.

How this works?
Consider $i^{th}, j^{th}$ balls, and assume that they can be swapped. We will prove that our idea of addng edges will already collect both these balls in the same cluster.
Case 1: Same Color
Let the lightest ball of that color be $k$.
Since they can be swapped,
$w[i]+w[j]\le X$
This means that $w[i]+w[k] \le X, w[j]+w[k] \le X$
$\therefore $ our idea of connecting ball to the lightest ball of that color makes the cluster complete and we never miss out any edge of this type.
Case 2: Different Color
You can work(similar to what we did above) out to see that if $w[i]+w[j] \le Y$, then our idea would also collect both these balls in the same cluster.

Now we have made clusters, all that is left is to compute answers for each and then multiply them.  

Check the code for implementation of above idea.  

Overall, I had too much fun solving this problem and I learnt something from it.

A Longest SubArray Problem

Rachit Jain, rachit iit roorkee, rachit iitr, rachit codechef, rachit hackerrank, rachit jain microsoft

Tags: data structures, constructive, math

Here is another interesting problem that I found as a subproblem while solving a difficult problem: you are given an array $A$, and you have to build up array $inc$ such that $inc[i]$ represents the length of  longest good subarray(LGD) starting from $i$. We call a subarray $(L, R)$ good if its first element($A_L$) $\ge 1$, its second element($A_{L+1}$) is $\ge 2$, ...., its last element is $\ge (R-L+1)$.

Eg: If the array given is $A = \{1,2,3,3,3\}$ ,
then the output will be $inc = \{3, 3, 3, 2, 1\}$.

Eg: If the array given is $A = \{4,2,3,5,9\}$ ,
then the output will be $inc = \{5, 4, 3, 2, 1\}$.

After a lot of thinking for about an hour, I had the following simple O(n) solution:

Let $LGS_i$ mean the longest good subarray starting from index $i$.
Let's modify our array $A$ as $A[i] = A[i] - i$,  then:
1. $LGS_0$ will continue to stretch till the maximum index $j$ such that $A[k]\ge 1$ for $k \le j$.  
2. $LGS_1$ will continue to stretch till the maximum index $j$  such that $A[k]\ge 0$ for $k \le j$.
3. $LGS_2$ will continue to stretch till the maximum index $j$  such that $A[k]\ge -1$ for $k \le j$.

Since at every step, the lower bound is always decreasing by 1, we can use one pointer to find the farthest ending point of good subarrays for all indices in $O(n)$.  Note that we are able to use 1 pointer technique because of the fact that ending point of $LGS_i$ will always be after the ending point of $LGS_{i-1}$.

Check the code for the implementation of above idea.

A Greedy, Math Problem

Rachit Jain, rachit iit roorkee, rachit iitr, rachit codechef, rachit hackerrank, rachit jain microsoft

Tags: math, greedy, constructive, combinatorics

So I have found questions from AtCoder interesting since the launch of the site.  

Here is another problem: you are given a  number $n(<10^{12})$ and you have to find an array of size $\le 200$, such that there exist exactly $n$ subsequences of the array which are good. A subsequence is good if it's first half is same as the second half like (1,2,3,1,2,3).   

I was amazed by looking at the solution for this. I wasn't able to solve it on my own. So here is the solution:  

Let $P_k$ denote any permutation of first $k$ natural nos. Then consider the array $A$ formed by adding the sequence of first $k$ natural nos to $P_k$  i.e $A$ = $\{P_k, 1, 2,3,4,...,k\}$  

Now the total no of good subsequences of $A$ is same as number of increasing subsequences in $P_k$.   

Now, note that if total no of good subsequences in $P_k$ are $x$, then we can place the next number $k+1$ in  

1. Front of $P_k$, resulting in total good subsequences to be $x+1$.
2. Back of $P_k$, resulting in total good subsequences to be $2x$.

Now when we need $n$ total good subsequences, we can recursively find the array that will generate it based on the parity of $n$.  Note that you scale down $n$ by half in atmost two steps, so we will need at max $2log_2(10^{12})$ steps i.e $80$ steps.

Check the code for details.