- "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.
