11. Faraz's Blog + New Training Contests

- Faraz's Blog

Finally , I found my best English partner. Faraz joined me in learning English. He has created a blog with name : Story of contests . It seems he doesn't like to use both subject and verb at the same time, in each sentence he drops one of them :D Anyway , we are working on decreasing our mistakes.

Now our university ( Urmia ) students solved problems statistics is available there. Link to post

- New Training Contest

I have started a new type of training. Every night I create a contest with about 10 problems for next day and I try to solve them till noon. After that I try to find solution for unsolved problems and those that I think need better solution.

This is my first contest that I solved 9 problems out of 10 : 10. Mixed Problems

I am going to do it for about 5 days of week. ( I hope actually :)

10. Three days without my laptop !

- Used to Computer

I am so sad for myself because I am used to using computer and internet everywhere. Nowadays this is a typical issue, specially for computer students. I can't throw away my laptop and say "No more ...!" because It is my favorite field , future work and I have to prepare myself for next ACM competition. 

Sometimes I think that maybe it would better if I was born in 19th century and hadn't seen this digital life ! Everything was real , I could have long mustache with archery talent , Faraz was a big strong man and a mace bearer and we fought with king Yashar for his unkind orders :) :P :D ... I don't know everything except this type of life.

Anyway, Thank God for everything. I love my family and friends. Maybe if I wasn't in digital age , I couldn't watch and read Sherlock Holmes serials and stories and it was much worse ... ;)

- Update ...

Feedbacks after publishing the blog! :

Yashar : "I like too live in the woods. I hate chairs and desk. I like to hunt animals and cook them on fire. It's not natural to go to store and buy meat and cook it on the Oven."

Faraz : "I like to live in caves :|"

9. A day with little argument | Petya and Divisors

- Little Argument!

Rahmat is back again and we have more fun these days. Today at lunch time , Faraz and I , had a little argument that became to our funniest moment in this day. Rahmat started the game, he threw the water on Faraz for finishing the discussion, but it made situation worse :) Rahmat and I chased Faraz out the floor and threw water on him as much as we could , we forgot to took a picture of him after playing , but you can imagine him like this :D

- 112D. Petya and Divisors 

...

8. A bittersweet day | Matrix Multiplication!

   

- A Bittersweet Day!

Sometimes you want to be happy, but something sad inside of you has more control than your own on your feelings. Today we had a different day , bitter things happened , sweet news received.

. The Bitter Part : Today Faraz was depressed and he attempted suicide , he was on the roof of an 14 floors apartment and I was screaming for help buuuuut suddenly ... :( ... OK, I exaggerated again , I don't know why but i like it :) Actually he was depressed but I didn't know why and he didn't talk much. We went out for hours to have a rest after some tough days. Long story short things were not going well.

. The Sweet Part : Finally, we received the SnackDown email about sending T-Shirts and Goodies. We don't know what will be the goodies, but Faraz predicts that they will be Peppers because SnackDown is a Hindi competition ;) We had got rank 227 out of 13500 teams of all over the world.

- Matrix Multiplication

One of the must known methods for Codeforces D and higher problems is Matrix Multiplication.

Let's consider it with a simple example. Suppose you want to find the 10^18'th Fibonacci Number (modulo 1e9+7). How will you find it ?

I want to solve it with mentioned method. We need a master matrix[M] and a coefficient matrix[C] (these name are not official !).

In M we will put two of the consecutive Fibonacci numbers. C must be a matrix that  M*C receives the next 2 consecutive elements of the sequence.

Also we know that matrix multiplication has associative property , so we can do this : 

Well , We reduced the problem to finding the x'th power of the matrix C and multiplying it to M ! Now How we can find x'th power of the matrix fast ? 

Yes , Binary Exponentiation . As an example : 

2^12 = 2^6 * 2^6

  2^6 = 2^3 * 2^3

    2^3 = 2^1 * 2^1 * 2 = 8

  2^6 = 8 * 8 = 64

2^12 = 64 * 64 = 4096

OK this was a short explanation about Matrix Multiplication , I recommend you to read these well-written links for more details :

- Suhendry's Blog ( Some simple applications and codes )

- Fushar's Blog ( Advanced examples )

- Wikipedia

And some problems to solve :

- 583D. Once Again...

- 678D. Iterated Linear Function

You may check the second problem's implementation as a sample code.

7. A day with Waldner's amazing plays | Not Obvious Dijkstra

- Jan-Ove Waldner

Google : "Jan-Ove waldner is a Swidesh former table tennis player."

His playing style is very attractive and his calmness in playing shows his great dominant on the ball. I don't know what do you think about PingPong, but if you think that it is not a real sport , I recommend you to watch some of the Waldner's tubes on youtube. I think you will change your mind. 

Some of good ones : BestPoints , vs TimoBoll

Actually PingPong is Faraz's favorite sport and he downloads so many clips about it and we watch some of them in free time. I am not a PingPong fan but now I think it is good to try and learn it with faraz's helps :)

- Not Obvious Dijkstra!

Some of the Finding Minimum Distance on graph problems are solvable by variations of Dijkstra algorithm but maybe it was not obvious at first glance.

Read this problem 230D. Planets as an example and please try to think about using Dijkstra Algorithm as a direct solution for it , before reading the next paragraph.

Solution : Well , I hope you had came up with the solution by yourself , anyway , I explain my approach.

0 - For simplicity of the explanation , please open this link and follow the steps by checking the code.

1 - Create an ordinary graph with adjacency list.

2 - Do a simple dp on the travelers arrival time. Save for each of them , earliest time that you will be allowed to leave that planet.

3 - Write a function "calcExitTime" that gives the planet index and your arrival time and returns the earliest time that you will be allowed to leave that planet with help of dp's you have calculated at step 2.

4 - Now everything is ready to use the Dijkstra algorithm. Write classical Dijkstra with this difference that you must use the earliest allowed exit time of the destination planet instead of your arriving time in it with help of "calcExitTime" function. I mean this part :

lli t2 = found( xid , t + xt );
s.insert( A( t2 , xid ) );

5 - Note that we use the minimum arrival time on the n'th planet as solution, no exit time. So you must take care of it separately. Minimum time of the arrival times to the n'th planet, is the answer to the problem.

I will update the post with another problems , whenever I found the similar ones. Also It will be great if you suggest us some of them.