oh, excuse me.

I try to hold another contest and show you Appleman again :)

You love appleman? But..but..Tanya...

Same here, for Japanese :) that's why the time is unusual.

En.. If it is the 'usual time', it will be 00:00 ~ 02:00 in China ..

Maybe all competitive programmers should live in the same longitude :| Where is reasonable?

the "dislike me" loop will start as usual -_-

:)

That was a 24 hour contest you could have given it anytime :P

Maybe someone else would have an English class at another time :D

But it's clear that this is for the problemsetters' convenience.

Мне тоже не понравилось. У меня конечно нет достаточного опыта, но, думаю, надо было дать нескольким людям разных цветов порешать задачи до контеста, и такой проблемы бы не было.

Есть довольно объективный критерий "гробовости" раунда — сравнить число участников в мониторе и число зарегистрированных участников.

Сегодня результаты этого сравнения даже не требуют дополнительных комментариев.

It would've passed :P

Yes, of course

Codeforces is very fast you can use about 5*10^8 operations in 1sec.You probably talk about problem B (dfs-O(n^2)).You can't find tescase where you use 10^8 operations beacuse m(number of edges) is so small.

in second cf server can do more than 10^8 operations i think

10^8 is very fast. Sometimes even fast 10^9 works

Normal DP with F(i, j), where i is current position and j current jump length, but notice that j won't vary that much (~250).

Edit: I came up with this in the last minutes. T_T

Imagine the game is finished, and your final jump length equal to j. It can be proven, that |j - d| is . That's why you can write dynamic programming dp[position][|j-d|].

UPD. The simple thought that can help you prove the fact. Imagine you start from the very start, and you have d=1. You cannot finish with large d, because almost equal to n.

UPD2. Fix a mistake, thanks Svyat.

Don't worry, 1364 registered for DIV1 and only 362 solved problem A :-D

We all will be kicked out of the division :-D

У меня корневая.

Для цветов, у которых много ребер — сделаем DSU по всему графу и просмотрим все запросы втупую — таких цветов будет немного.

Для цветов, у которых мало ребер — для каждой вершины просмотрим все доступные из нее по этому цвету, и проверим, есть ли такие запросы. Это мы тоже можем сделать, потому что если мало ребер данного цвета — то и компонента связности будет маленькой.

По-моему, тут работает наивное решение. Запишем для каждой вершины пары "цвет, номер компоненты связности по этому цвету, которому принадлежит эта вершина".

Дальше при запросе будет тупо проходить вектор пар для вершины, для которой этот вектор короче, и проверять, верно ли для второй вершины, что по такому цвету она в такой же компоненте.

Проверок, как ни странно, будет в сумме O((N + M)^3 / 2) — для вершин, у которых этот список длиной меньше корня, это очевидно. Для вершин, у которых список длины больше корня, суммарное число проверок для пар со всеми остальными вершинами не привысит М,а самих таких вершин не больше корня.

Значит, если кешировать ответы для уже пройденных пар и использовать для проверки, какая у вершины компонента по цвету, хэшмап, получим общую ассимптотику O((N + M)^3 / 2). Вроде все верно?..

А теперь посмотрим, пройдет ли у меня это с мапом и дополнительным логарифмом сложности:)

UPD: Нифига себе, хвала могучему кодфорсесу! Прошло за 1.1с, однако..

Infinite reccursion. You don't initialize values of parent with parent[c][i] = i
And in find:
if(parent[c][v] =  = v)

It will fail with this testcase:

4 4 1 2 1 1 3 1 2 3 1 2 4 1 0

You do not check if they are already in same component and the recursion never ends.

Imagine easy dp with [coordinate][lastJumpLen] state. Replace second argument with difference between the first jump's length and last jump's length. You know that it won't exceed 300.

I think that B was much easier.

Solution of A

Maybe other 4 problems were just too easy, obvious and uninteresting for him...

I think we'll see his explanation in weekly digest :)

D was easy :>. Only one in that contest :D

Hmmm... you're totally right. After 0,5h of contest when I haven't got any idea how to solve any of those problems I considered not submitting anything : p.

I though, that once I'm registered, I'm competing — I expected my rating to be changed, even when I had no submition... On TC once I open the problem, my rating would be changed... But in fact the one who solved problem and ended at the end, his rating change is worse then mine, I think this is unfair...

See above: http://codeforces.me/blog/entry/15842#comment-207412

I think it is dynamic programming problem(but I couldn't implement it). It is because d can be only in segment (d-700,d+700) otherwise sum of jumpings at least d^2/2>30000. So dp[30000,1500] kills it. Am I right?

I solved it with Union Disjoint sets in 2D. I think it can pass for m as large as 10^5

Didn't submit (edit: Accepted ), but here's what I thought during the contest:

You want to simulate to see if a certain max_height is possible, then you can use binary search to get final answer. Hit the bamboos from the last day to the first day. Every bamboo i has to be hit before you get to a certain day hit_by[i] on the reverse simulation -- this means that even if you use all hammers possible on bamboo i before hit_by[i] you will not decrease height of bamboo enough, so you need to hit it at least once on a day after hit_by[i].

I haven't proven it formally, but I think greedily hitting the bamboo with the largest hit_by works.

My solution is based on the idea that it's optimal to hit a tree when its height is less than P at most once per tree. If this is true, then that hit should be at the first moment when (tree's height)  ≥  (tree's final height if left unchecked — target height) % P.

I don't have a proof for that, though, so we'll see what happens in systests...

I think such difficulty is good, AS LONG AS there is at least one problem that 75% of participants can solve (and it is the first problem :P)

Median of times I need to came up with solutions to B problems is probably less than a minute and here I didn't have any idea how to solve A and B took me something like 30 mins xD. Though I like hard problems, so this contest was really fun for me, because problems were interesting and that's what really counts :)!

Hard problem's have benefits . Solve hard problem to learn a new something :)

I think Problem B is easier than D.

The same algorithm passed pretests here.