Next to Farid's Gallery

I am trying to improve my English language and that's why I have made this blog. Forgive me for my mistakes and if you found free time , give me some advice to rectify my wrong statements.

6. A day with "Who am I" Movie


- "Who am I" Movie

Have you seen this movie ? The movie is about a hacker team that wants to get the attention of MRX biggest hacker ... OK OK I don't want to ruin the movie ... I suggest that you watch it if you are interested in mysterious movies. It's IMDB score is 7.6 .

I watched the movie twice later and I really enjoyed it. Tonight because we were bored , decided to watch a movie and since "Sakene Tabaghe ye Vasat" couldn't attract us ( maybe it is for artists ) , I suggested to watch this movie again.


- Another usage of Fermat's Little Theorem

One of the well-known Fermat's Little Theorem applications is finding inversion of a number according to this relation when p is a prime : a^(p-2) ~ 1/a

Today I want to tell another usage of it according to : a^(p-1) ~ 1 [ original relation ]


Problem : we get numbers x and n and then n numbers a1,a2,...,an and we want to find x^(a1*a2*...*an) modulo 1e9 + 7. ( 1 <= n <= 1e5 , 2 <= x , ai <= 1e9 )

Solution : If there was + instead of * in the formula , then we could simply calculate x^a1 * x^a2 * ... but they are * and the multiplied number can be so huge. so what we can do ?


According to this formula x^(p-1) ~ 1 [ modulo prime p ] and knowing that here p = 1e9 + 7 , Then we conclude that --> x^y ~ x^(y%(p-1)) [ modulo prime p ]

That's it! For solving the problem we just need to find x^( (a1*a2*...*an) % (p-1) ). And it is solvable in logarithmic time with Binary Exponentiation.


As a training you can try this problem : 615D. Multipliers 

۲۵ مرداد ۹۵ ، ۰۱:۰۸ ۱ نظر موافقین ۲ مخالفین ۰
محمد افتخاری

5. A day with-out Rahmat | Symmetry in GameTheory!


- Without Rahmat

Today Rahmat left the dorm for helping his family till Wednesday. They are going to work in their garden, they have to manage their yield. I wish plague doesn't ruin their crops and have good crops.

Today was a bit boring because we had used to each other and Rahmat and I were good at making fun of Faraz :)

Faraz and I went out and eat ice cream again. Without Rahmat we can't play Rocket League and I have missed it so much.


- Using Symmetry in Game Theory Problems

I have encountered many game theory problems that needs to use Symmetry for solving them. 

Today I stuck on one of them : 120E. Put Knight

Problem says that 2 players A and B are playing on a chessboard with size n*n. They take turns to put a Knight on board such that no two Knight threat each other. The player who can't move loses.


Solution : At first glance it seems so hard problem but actually it is so easy if you know how to use symmetry rules!


If n was odd : A can put first knight at center of the board and after that if B can find any place to put his knight then A also has a place to put his next knight , exactly in symmetric place of the B's knight respect to the center that certainly is empty ( also new 2 pieces can't threat each other ), so A is the winner !


If n was even : Divide the board to 2 same parts vertically. Every place that A puts his knight , B can put his knight at exact same row but in symmetric place of A's knight respect to the divider line ( also new 2 pieces can't threat each other ), so B is the winner !


۲۳ مرداد ۹۵ ، ۲۳:۵۳ ۱ نظر موافقین ۱ مخالفین ۰
محمد افتخاری

4. A day with Awesome T-Shirts


- Awesome T-Shirts

Have you seen such T-Shirts ? I like the ideas of their photos. Sometimes a simple photo on them , talks more than a book. The photo on this T-Shirt is short description of our life in last 2 months. Wake up , have breakfast , code till noon , have some rest , have lunch , read or code till night , have dinner , rest , write a blog , sleep , Wake up , ... that's nice :) Ok maybe I exaggerated , but at least we are trying to be like that ...


- New problem about LinkLists

I am so glad that I saw another problem that needs to be solved using linklists , because this is a scarce thing! Yesterday I couldn't solve the problem in contest time, also after it and today i checked the editorial that was a surprise for me.

Problem says that we have a matrix and in queries we want to swap 2 submatrices of it with some conditions. For solving the problem we need to create a linklist with matrix members , each member is linked to it's neighbors. For each query we just need to change the links of the borders of the submatrices, because members at inside of the submatrices will remain in the same positions related to the borders. ( check the comment )


- News

. Unfortunately today Rahmat and Faraz put some restrictions on eating the Pickled Peppers and I missed watching them after dinner while crying and screaming. It is not funny again :|

. I learnt new formula about binary operators : a+b = (a^b) + (a&b)*2

۲۲ مرداد ۹۵ ، ۲۳:۵۵ ۰ نظر موافقین ۱ مخالفین ۰
محمد افتخاری

3. A day with FIFA16 and Pickled Peppers!


- Playing FIFA

Have you played FIFA and PES ? Honestly, I am one of the PES fans , because it is easy to play and you have fun with your friends during the game because of fast movements and killer shoots , but I can't ignore how great is FIFA16! 

It has great graphic and players moves are like real life players moves ! Its gameplay is so harder than PES and you have to think about everything you are doing otherwise you can't keep the ball more than some seconds! It makes tired your brain if you play much. 

I remember that we played FIFA15 before Lahijan University Contest. We were really tired during the contest and we did awful in it ! :(


- Faraz's MemoryLimit

We had a contest today , Codeforces Round #367 (Div. 2).

Faraz had a strange mistake in his code. He had used string "zz....z" as biggest lexicographically string in problem C. He didn't know that it can be like suicide for him! because 10^5 strings with length 10^5 will be 10^10 and ... yes MemoryLimit because of silly mistake. 

Fortunately he corrected his mistake. Actually he could use a single letter ('z'+1) for this purpose! It is good to remember it and don't repeat it again. 


- News :

. Faraz and Rahmat have bought Pickled Peppers again and they eat so much of it with dinner. After dinner they scream and cry for minutes and eat yoghurt ... it is so funny to watch them :D :D :D

. Finally after a month we found kitchen lamp's switch :D it was behind the oven.

۲۲ مرداد ۹۵ ، ۰۰:۱۹ ۱ نظر موافقین ۲ مخالفین ۰
محمد افتخاری

2. A day with Mark Zuckerberg's Movie

It was nice to watch "The Social Network" movie that is about how facebook has been created. I don't know how much it was accurate in depicting the truth but anyway it had a narrow view about what had happened.


Today I solved 6 problems and one of them was really awesome : Babaei and Birthday Cake

( I have written some hints about it's solution at bottom of the page )


Faraz solved his first Segment Tree problem and is working on improving his skill on it with solving more problems. Also he has became Expert  in last contest and I think it will motivate him more than before :)


But we really need to manage our time better than this , because i think we have many wasted time.


We went out today and had some fun with eating ice cream. Faraz fell down his ice cream very soon and he was watching us when we were eating :D it was nice day.



---------------------------------------------------------

Problem Solution : 

It is like LIS problem and I have used a method like that.

Also it is necessary to be good in Data structure . I solved it with 2 different DS , one with ordered_set and one with segment tree.

۲۱ مرداد ۹۵ ، ۱۶:۴۳ ۰ نظر موافقین ۲ مخالفین ۰
محمد افتخاری