The statement of Problem B is really ugly...

The Standings must look very cool with all these popping red colors! :D

Curiously... then we won't be able to be Legendary grandmasters.

i think the magic color will not change before 10/1 but your rating will change after the contest

Finally after contest both magic color and my own color wasn't changed through i have up my rank...:(

Спасибо, поправил.

And data structure?

Just wait for PrinceOfPersia to prepare another Hello 201X contest.

Maybe "cheers!2016" is nicer... Dala!

The platform that contests are hosted at. Their own, handwritted (handbuilt?) Ejudge. A pretty neat thing, if you ask me. Link.

Polygon (https://polygon.codeforces.com) is a system to prepare programming problems and contests. It is used for each Codeforces round, but not only: many other contests are prepared in Polygon.

i think it depends on your rate not on your color and if what you say is right most of Div2 contestants will not be able to participate in this contest as they change their color into red "or any other Div1 color" and in this case this contest will change from Div2 contest into Div1 contest XD except form a few contestants who doesn't change their color XD

First time as Legendary Grandmaster as well for me! Feeling so nervous ^_^

We were not changing any constraints or time limits during the contest. However, they were changed just before the contest, so it may happen that you got old version because of caching. We apologize for the inconvenience.

I guess the checker is case-insensitive. How do you think that person's solution would pass the pretests if the checker was indeed case-sensitive?

but i cant find the pattern. can you tell me?

Why problem E problem E?

I just read the problem in the last few mins, after solving D (I didn't attempt C first), and realize that it is quite easy -_-

I didn't solve B. I think C was easier than B

Iterate over each vertex and fix it as the end of tail. Now however long the tail you choose(ending at current vertex) the spine will be same, which is the number of edges originating from current vertex. So, that value needs to be multiplied with dp[x], which is the longest decreasing sequence originating from current vertex. You can precompute dp easily in O(N).

my solution is
for node 1 to N
it can be a node of a tail(a,b,c...N)
a<b<c<...<N
can build max tail for each node

ans is max (len(max_tail[N]) * connection[N])

B is killing me.

I've spent like 20 minutes reading and reading and reading the statement. So overwhelming.

And after that got hacked 5 mins before the end, couldn't figure out whats wrong with my solution in that time.

Какая попытка?

Contestant's mistake: (a^b)%MOD ≠ (a^(b%MOD))%MOD

What it actually is (a^b)%MOD = (a^{(b%(MOD - 1))})%MOD

Contestants solution were working if b < MOD - 1

Please don't paste in long code, link to submission.

Please, use pastebin, ideone, paste.ubuntu or github for your code.
It would be much better to read your code there.

Use formula:

p(n) = n ^ (d(n) / 2)

where: * p(n) is multiplication of all the divisiors of n. * d(n) is count of divisors.

Formula.(I think this is the formula. Feel free to correct me)

let k=frequency of a prime

then, ans=product of((prime^(2^k-1))^(sum/f(prime)))

sum=product of(frequency of prime+1)

f(prime)=frequency of prime+1.

If n is not a perfect square, then every divisor d1 can be paired with the divisor n/d1, which is distinct from d1; the product of these two is n. So the product of all divisors is equal to n^k, where 2k is the number of divisors. (Note that a positive integer has an odd number of distinct divisors if and only if it is a square).

If n is a perfect square, then it will have 2k+1 divisors for some k; the product will be n^k×√n=n^(k+0.5).

First of all you want to bundle all primes with the same value. You now have n = p₁^e₁p₂^e₂...p_m^e_m

All divisors must be written in the form d = p₁^f₁p₂^f₂...p_m^f_m, where 0 ≤ f_i ≤ e_i.

Then we know that the product of all divisors d is:

We see that all factors from i₁ to i_m - 1 are not depending on i_m so we can put them outside the last product when we raise it to the (e_m + 1)'th power. In fact we can repeat this process for every term, and so we can split this product into m terms to get the following result:

Which is equal to:

The inner product should be calculated by using two precalculated tables:

One table for the products from i=0 to i=j-1

One table for the products from i=j+1 to i=m-1

To prevent overflow, everything in the exponent of p_j can be taken modulo 10⁹ + 7 - 1, using Euler's theorem.

I have exactly the same trouble with you.

So, it's turned out that the second pretest is different from the second example. Never seen this in the past...

I don't know about E I read till D. So according to me, the difficulty was A < D~=C < B.

I'm sorry, if the question is silly, but how do you make these formulas here? :)

Я пока не знаю, прошло ли моё решение, поэтому пока просто сделаю набросок словами.

Будем перебирать в цикле все вершины (вообще все). Каждую вершину мы считаем за начало хвоста. Дальше мы удлиняем хвост с помощью dfs до тех пор, пока есть смежная вершина с номером больше текущего.
После каждого удлинения на одну вершину, мы смотрим количество ВСЕХ смежных вершин с текущим концом хвоста. Это количество смежных вершин — все иголки ёжика. Умножаем количество иголок в данный момент времени, на размер текущего хвоста и сравниваем с лучшим результатом, который мы когда-либо достигали.

Если мой подход пройдёт и никто не сделает более менее красивого описания этого решения, я сделаю более подробный комментарий с картинками =)

Это задача на динамическое программирование (очень простая). Перебираешь вершины от 1 до n и смотришь, какой самый длинный хвост оканчивается в текущей вершине. А в ответ идёт максимум из степени вершины помноженную на длину хвоста.

I think it was a case for perfect squares because when i fixed my code for perfect squares it passed for pretest 4. Not totally sure though because I haven't checked the test cases manually yet

Fuck, I always compute sqrt(n*t(n)), but there are 2 sqrt by module p...

only the edges from tail endpoint will be considered as spine . in this case the tail end point is 5 (maximum node value in the tail), so the spines in this case are 2-5, 5-3 and 5-4

For each vertex x, find the longest increasing sequence ending in it, we save it in L[x]. We can do this with a dfs starting with the largest integer, and setting the maximum length of a sequence ending in x as 1 + max, where max is the longest sequence ending in a neighbour of x that is smaller than x. You can look at my submission for more details.

After that, we just have to calculate the maximum of d(x) * L[X]. Where d(x) is the degree of vertex x.

I don't know whether my solution passed yet, so I'll make a sketchy description.

Let's enumerate all the vertices. At every step of that loop we'll consider the current vertex as the beginning of the tail. Inside the loop we're going the grow our tail step by step using dfs. On each step, dfs processed the last vertex of the tail, so it must have the biggest number among those we've already encountered. If the current vertex we are processing is the last, then we can also count how many spines there are. The number of the spines is the number of the adjacent vertices to the current back of the tail. So, we multiply the current length of the tail and the number of adjacent vertices and store that number in some global variable. If, during our dfs processing we're encountering bigger beauty, then we update that global variable. DFS continues till it can find the next vertex with the number bigger than the current number.

If my approach is correct and there wouldn't be any beautiful descriptions of the solution, I'll make a more detailed description with pictures :)

recently it comes out real fast.so I don't think it will take more than "a few" hours

Usually we publish editorial immediately or in one hour after the contest ends. However, this time that may take a bit longer. Anyway, solutions for all the problems are already mentioned in comments.

same ! got tle on test #20 ... I assume they were expecting some trie based solution for that :|