Thanks for nice problems и fast Разбор

Интересно, почему в задаче D решение работает за O(N), а ограничения на N до 1000?

Thanks for the lightning speed EDITORIAL.

In F problem, I haven't seen the limit that must have an unchanged cell... So I wrote a code in O(sqrt(min(k, 1e15)).. When k > 1e15 print "NO", then enumerate the factor of k, use dsu to solve it, and got WA4. After contest I found the limit and add it then accepted...sad..

The best contest i've seen so far, I really liked the problemset and the fact that is was a 7 problem round instead of the regular one. Great job!

why this 17050130 gets WA in problem E?!!

any one can provide a small case which make it fail ?!

I feel guilty for doing this 17058751 for 659D - Велосипедная гонка:

• I simply used java.awt.Polygon class to create the lake polygon.

• If Maria misses turn i, she would proceed by dx = signum(x(i) - x(i+1)), dy = signum(y(i) - y(i + 1))

• Then I simply checked if lake polygon contains (x(i) + 0.5*dx, y(i) + 0.5*dy)

Hello everyone , Why testcase 53 is not correct in my answer since my answer totally matched with jury answer here is the link... for problem 2

There is a parsing error in the editorial of F

А как можно оценить такую штуку (По задаче F). Количество таких a, что k / a >= n * m. Просто не понимаю, случайность или нет, что решение зашло за O((количество таких а) * n * m)).

I solved D by finding point inside a polygon . I had to code almost from the scratch because somehow geeksforgeeks code was not working -_- . And after seeing this O(1) solution.....

Can anybody tell me why i have a WA in test 15 of problem B?

Could anyone help me with that http://mirror.codeforces.com/contest/659/submission/17057892 ?

My solution for problem D is to count the number of left turn and the number of right turn then take the minimal of them. I have no idea why it works. It was a desperate attempt. Can somebody provide a proof? Thank you!

My submission: http://mirror.codeforces.com/contest/659/submission/17055311

Can someone explain problem F in more detail please? Basically for each cell with value v, you want to know C(v) = how many cells are connected to it that are at least v. When you sort by decreasing value and DSU, won't your calculation of C(v) for cells with the same value be wrong? For example this grid:

2 4 5

6 4 3

I didn't notice that in problem D we may only drop into water on left turn and solved the more generalized version of the problem.

The idea is we can record all the vertical and horizontal segments, and for each turning point we can count how many segments we may intersect if we keep going straight. If the count of segments is odd then this point is dangerous, and not while the count is even.

How does that formula come in problem number A ? Can somebody illustrate please ?

In 2nd Problem, why is the output on terminal and Codeforces Judge different??

I got WA on 1st pretest again and again because of this..

My solution is :- http://mirror.codeforces.com/contest/659/submission/17065952

Hello for problem D, I have a doubt what property does this test case violate:

5
1 1
1 2
-1 2
-1 1
1 1

First of all, thank you for the quick editorial!! I would like to mention 2 points regarding the editorial:

1. The phrase "as soon as" is used in places where "since" or simply "as" should be used. It is not that important(since the intention is very much clear), but feels odd! :P

2. For problem E, I did not understand the part "...as chosen vertex belongs to a cycle, at least one of its edge will not be taken to account in the DFS, so it can be given to a root. This way all the vertices will be satisfied." clearly. Can someone explain it in more details?

У меня небольшая проблема с задачей C. Мои локальные результаты отличаются от результатов теста CF.

http://mirror.codeforces.com/contest/659/submission/17051531 — код

C++ я начал изучать недавно, может кто, пожалуйста, объяснить новичку в чем здесь проблема?

Заранее спасибо!

can any one tell why am i getting RTE on problem B

this my submission

Can someone explain solution for F in more details ?

Problem G has a divide and conquer solution too ... :P *I wanst able to arrive at the formula stated in the editorial but divide and conquer was a bit more intuitive to me *

Link to submission- http://mirror.codeforces.com/contest/659/submission/17075860

can anyone explain solution of problem E in detail.

В задаче F зашел DFS от каждой "подходящей" точки, то есть по сути O(m * n * n), где m — это количество — делителей k, которые у нас есть в таблице и при этом с их помощью можно получить объем k. Долгое время в max-тесте был TL, потому что неудачно занулял массив used вершин для DFS. После AC появился вопрос: Количество делителей равное ~3000 это максимум для данных ограничений задачи?

Thanks. Some beautiful problems and elegant solutions out there. :)

There is O(1) solution for problem E. http://www.codeforces.com/contest/659/submission/17067296 Can anyone explain me this.

Please it would be really grateful if someone can explain editorial of Problem F.

Problem G

please explain how S(r + 1) = S(r) × min(hr - 1 - 1, hr - 1, hr + 1 - 1) + min(hr - 1, hr + 1 - 1).

O(1) for bicycle race its superb

Problem E

why N — BPM getting WA?

Graph :

Edge 1 | Node1

Edge 2 | Node2

Edge 3 | Node3

83363813 can anyone provide a smaller test case where my sol fails

Sorry, I am too late but in problem E, what about individual components with no roads why we have to add 1 as I was getting WA earlier but question states a city is separate only when it has no road leading into it and only leading out of it.

My hand at a more "human" explanation for problem G from someone bad at maths:

First, let's solve this task for constant h[i] (assuming each element of h is reduced by 1 from now on).

If we only consider the first plank, we can cut off any part of plank 0 from 1 to h[0]. The total answer for this plank is h[0] — dp[0] = h[0].

If we consider the second plank, we can either only cut off part of plank 1 from 1 to h[1], or do the same in addition to any possible cutoff ending at the previous plank (it's clear that no matter whether we cut off 1 or h[1], we still can cut off any part of h[0]). The answer for this plank is h[1]+h[1]*h[0], and the total answer is h[0]+h[1]+h[1]*h[0].

We can advance infinitely, storing the answer for the previous plank:

dp[i] = h[i] + h[i] * dp[i-1]
ans = sum(dp)

Now let's consider the case where h[i] is non-decreasing.

The start is obviously the same, but things change starting from the second plank.

If we want to cut h[1] but leave h[0] (and everything before) as-is, nothing changes for us, so h[i] is still part of dp[i].

But if we want to also cut off part of h[0] and h[0] < h[1], then we can only cut off any part of h[0] if we also cut h[1] to the same height as we will cut h[0]. For example, if h[0] = 3 and h[1] = 10, we can cut h[0] and h[1] to length 0, length 1 or length 2, but cutting h[1] to length 3 makes h[0] impossible to cut.

This means that in this case:

dp[0] = h[0]
dp[i] = h[i] + min(h[i], h[i-1])*dp[i-1]
ans = sum(dp)

Finally, let's consider the hardest case — non-increasing sequences.

If we want to cut off h[0] alongside h[1] and h[0] > h[1], then we can only cut h[0] to the same or smaller height as h[1]. If h[0] = 10 and h[1] = 2, we can cut h[1] to 0 (in which case h[0] must be cut to 0 as well), or we can cut h[1] to 1 (in which case h[0] can be cut to either 0 or 1). In addition, all options that depend on h[0] being higher than h[1] are unreachable from h[1].

So in this case, only part of dp[i-1] must be used — instead of dp[i-1], use the same formula as before dp[i-1] but with changed height:

calc_dp(0, height) = height
calc_dp(i, height) = height + min(height, h[i-1]) * calc_dp(i-1, min(h[i-1], h[i]))
dp[i] = calc_dp(i, h[i])
ans = sum(dp)

Or, to put it in a different way:

# h2 is needed to account for increasing sizes (h[i]<h[i+1])
h2[i] = min(h[i-1], h[i])
# dp2 is needed to account for decreasing sizes
# dp2[i]: how many options ending at plank i are reachable from plank i+1
dp2[0] = h2[1]
# specifically min(h2[i], h[i+1]) on the next line is needed to account for decreasing sizes, otherwise dp2 is equivalent to dp
dp2[i] = h2[i+1] + dp2[i-1] * min(h2[i], h[i+1])
# dp[i]: how many options end at plank i
dp[0] = h[0]
dp[i] = h[i] + dp2[i-1] * h2[i]
ans = sum(dp)

Still pretty convoluted, but hopefully a bit easier to understand. See 223426302