Блог пользователя M_H_M

Автор M_H_M, история, 8 лет назад, По-английски

Hi. I’m Mohammad hasan Mousavi.My nickname is MooSooL.
For about 6 months I’ve been far from OI, and sadly that’s because I have to get ready for a hard and tedious exam called konkur! It’s for entering universities in Iran and consists of nasty subjects like Arabic & chemistry. At first this was really hard for me and I hated the atmosphere(!) and I saw my life wasted. last year I got trilled by posting blogs and receiving upvotes; I even named myself “MooSooL Contribute” .
I’ve missed posting blogs, and contribution doesn’t matter anymore maybe .But it feels good! maybe even more!

Peace and love!
MooSooL Contribute :D

Полный текст и комментарии »

  • Проголосовать: нравится
  • +54
  • Проголосовать: не нравится

Автор M_H_M, история, 9 лет назад, По-английски

Codeshark is an Iranian judge. ( like ProjectEuler )
Me ( M_H_M ), Iman ( IMAN_GH ) & Hamid ( ITDOI ) prepared the round #4 :

It is my problem :

In MooSooLestan, there are lots of strange trees with unlimited vertices.
strangest one is MooSooLi's tree :
---- The degree of each vertex(the number of adjacent's vertices) is equal to the id of that vertex.
---- The tree is rooted from vertex with id 1.
---- If x < y, the whole id of x's children fewer than y's children. ---- The id of vertices are natural numbers.

There is another tree named MoosMasak which is really same as MooSooLi's tree with one difference.
The difference is the number of each vertex's children with x is equal to biggest power of 2 that x is divisible by that.

Left : MooSooLi ---- Right : MoosMasak

Subtasks :

1) What is the sum of ancestors of 10 ^ 12 in MooSooLi?
2) What is the sum of ancestors of 10 ^ 12 in MoosMasak?
3) What is the sum of subtree of 17 in heights [0, 9) in MooSooLi?
4) What is the sum of subtree of 17 in heights [0, 18) in MoosMasak?
All of them mod 10 ^ 9 + 7

Полный текст и комментарии »

  • Проголосовать: нравится
  • +49
  • Проголосовать: не нравится

Автор M_H_M, история, 9 лет назад, По-английски

Round 349 B Div1 : 666B - World Tour.
The Idea of problem is fixing two middle cities!
But I solved the problem by this Idea :
Consider that the answer's cities are a, b, c, d and a < b < c < d
---- dp[ k ][ i ] = the maximum length with k cities so that k'th city is i(labels are increasing!).
---- We can update dp with O(n ^ 2) [ dp[ k ][ i ] = max(j < i : dp[ k — 1 ][ j ] + d[ j ][ i ]) ]

We shuffle the labels of cities while the labels of answer's cities become increasing!
The mathematical expectation of the above algorithm is (4! * 4 * N ^ 2) :))
My implementation : 17588529.
We can have a harder problem with five cities : (5! * 5 * N ^ 2)

Полный текст и комментарии »

  • Проголосовать: нравится
  • +154
  • Проголосовать: не нравится

Автор M_H_M, история, 9 лет назад, По-английски

Hello :)

Consider permutation p from 1 to N
Every permutation has a decomposition to decreasing substrings.
Step : Reverse all decreasing substrings.
Prove or disprove that p will be sorted after N steps.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +73
  • Проголосовать: не нравится

Автор M_H_M, история, 9 лет назад, По-английски

Hello

Consider Array A. For any suffix of A compute the prefix with maximum average.

Example : A => 1 3 2 5 3
Suffix [2, 5) => 2 5 3
Answer => 3.5

Is there a better solution than O(N ^ 2) ??

UPD

IMAN_GH's comment :

Haghani solved the problem and here we have his solution :

sum[i] = a[0] + a[1] + .. + a[i — 1]
for any i consider point (i, sum[i])
if answer for suffix i equals j then (sum[j] — sum[i]) / (j — i) is maximum in all j > i.
it's solution is somthing like upper hull of some points. it solves by using stack with insert points in the hull and updating it.
if we insert points from right to left then answer for suffix i equals to the second point in the upper hull after adding point i.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +113
  • Проголосовать: не нравится