- "Sabokbar" song

How soft and silvery is Salar Aghili's voice. I like to hear his songs when I am coding or tired. The "Sabokbar" track is one of the soothing musics that I have ever heard. I have been using his "Khushechin" track as my Ahange Pishvaz since about 6 months ago :)

Also Google's Human documentary movie starts with his voice, a poem from Molana. It shows that even without understanding his words, you can enjoy his voice and music.

Anyway, because I have used to listen pop musics. I like Ehsan Khaje Amiri's musics more than of everyone's.

- Meet in the Middle

One of the special and rare tricks that you can use for solving some of the problems. 

You can read about it here. Also I show you an example of it's usage :

HackerEarth Xoring in Base 10 : You are given n numbers ( 1<=n<=40 ) and an integer k. You have to find maximum possible Xoring of exactly k numbers in base 10 from the array.

Solution :

Note that n<=40 and we can't brute force it because it will be O( 2^40 ) !!!

Let's first consider the best Xor part. Suppose problem says that you have an array of integer numbers and you have a number x , select best number from the array that (x xor ai in base 10) became maximum.

Now Let's create a Trie with all numbers in the array. ( You have to choose a fixed len for number such as 9 digits )

Then finding the best possible number for x needs O( log n ) time ( Greedily, at each level choose a way that maximizes the xor )

( For learning it, Try Little Xor problem when n <= 10^5 )

OK , now how we can do the same here , when we have to choose k numbers and n <= 40 !?

- Split the array to two arrays from the middle. I will call "Left" to the first half and "Right" to the second half.

- Create k Tries. ( 0 : empty , 1 : for single numbers , 2 : 2 numbers , 3 : 3 numbers , ... )

- Do brute force on Left and find all possible subsets of it and add them to the appropriate trie.

- Do brute force on Right and check all possible subsets of it in created Tries. i.e. if a subset contains 3 numbers , you have to try to find best possible solution for it in Trie[k-3].

- Get maximum of all of them. you got the answer.

- Complexity : 2 * O( 2^20 * log(ai) )

( You can check the implementation here. )

I hope, you found the article useful.