Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### M_H_M's blog

By M_H_M, history, 3 years ago, , 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

By M_H_M, history, 4 years ago, , Codeshark is an Iranian judge. ( like ProjectEuler )
Me ( M_H_M ), Iman ( IMAN_GH ) & Hamid ( HamidReza_H ) 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 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

By M_H_M, history, 4 years ago, , Round 349 B Div1 : 666B - Мировое турне.
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)

By M_H_M, history, 4 years ago, , 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. By M_H_M, history, 4 years ago, , 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

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 + a + .. + 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.