We're working on it. It'll be posted soon.

wow ._.

I have time, but unfortunately, I lack patience.

Can you give me some hint / any tutorial about that algorithm?

On rng_58GP of Poland, 3 years ago

How to solve E?

Let us first calculate the expected gain of NSU for a given fixed entrance day t (1 ≤ t ≤ T).

Suppose, S =  The set consisting of the students who applied to NSU.


P(i, t) = Probability that the i-th student will be available till the t-th day.

Gi = Value of the i-th student.

If you can calculate E(t) in O(K), then the total complexity of your solution will be O(TK) (as you can iterate over all possible valid t ). You can speed up the solution with this optimization.

How to calculate P(i, t):


C =  The set consisting of the colleges where the i-th graduate has applied.

rij =  The day on which the i-th graduate applied to the j-th college.

G(c, l, r) =  Probability that the c-th college will have its entrance day between the l-th day and r-th day.


For problem 4(Universities), Is O(T * K) fast enough to pass? I got TLE on test 9.

On rng_58AtCoder Grand Contest 016, 4 years ago

I can solve this problem if both the arrays are some permutation of the first n numbers. But what if one number appearance more than once? How to create a graph in such case?

On bertho_coderWF Visa Application, 4 years ago

We applied 2nd time for the visa today and we got accepted. May be you can think about applying for the second time if it is possible.

I've gone through the "Advanced Topics" part and my reaction while reading this book can be described as: wow wow wow wow wow wow.....

Thank you for sharing it.

Why does it work?

"For the arrangement to be liked by Jon each of the f + 1 partitions created by f food boxes must contain either 0 or greater than h wine barrels"- I don't get the "must contain either 0 or..." part. Is it possible for a stack to be empty?

Yes I also think that it's similar to rectilinear Steiner tree problem. So yes, may be it's NP-hard.

I first misunderstood problem D and thought that I'm allowed to change " * " sign to ".". I found this problem interesting but couldn't come up with any solution.

But this guy managed to pass :)

Oh thanks! Didn't see that the editorial was there.

That's a cool trick :)

I tried to solve the problem "Make n00b land great again" but couldn't figure out how to efficiently update the queries. Can you please explain how to do it efficiently?

Me too. I don't know why :/

Break the problem into two cases: when k > sqrt(n) and when k <= sqrt(n). Deal with them in different ways.

Case 1: For any k > sqrt(N) there will be less than sqrt(N) alternating segment. If you have an array, having cumulative sum, you can get the sum of a contiguous segment in O(1). So you can just loop over the alternating parts and get the sum in O(sqrt(N)) for a single query.

Case 2: Now when k <= sqrt(n), you need to do some preprocessing.

let arr[k][i] be the "k alternating sum" of a subarray which starts at position i and keeps alternating untill it reaches a position x such that if you add another segment of size k then it will go out of the array. [ This array can be computed in O(N) , and as you're doing it for every k < sqrt(n), the total complexity is O(N * sqrt(N))] With the help of this array, you can answer every query having k < sqrt(N) in O(1).

Hope that helps.

wow :D Awesome experience :D

I enjoyed the contest very much :)

On DeemoTernary Search on Integers!, 6 years ago

Does it work correctly in case f(mid) == f(mid + 1) ? For example: f = {0, 1, 0, 0, 0}

For every edge (x<->y), we need to calculate how many edges (p<->q) intersect it. In order to make sure that we are not overcounting, we'll only consider such edges (p<->q) where x < p < y < q [They surely intersect each other]

We can do that in O(log n). Maintain a segment tree where a node in the segment tree having range [i..j], holds the end points of the such edges (u <-> v) such that i <= min(u,v) <= j, in sorted order.

Now suppose we want to know how many edges (p <-> q) intersects with (x<->y) where x < p < y < q. To get this, we'll query on the range [x+1..y-1]. As we have the end points in sorted order in the segment tree, we'll binary search on y to get the answer.

Can you please elaborate?

We can use dp for checking half-palindromes.

Suppose our good[][] array works correctly for substrings of length 1,2,3...i-1 Now we have to consider the substrings of length i and update the good[][] array.

It's obvious that good[i][j] = 1 if and only if,
- char at position i equals char at position j and
- (i+2 > j-2) or (dp[i+2][j-2] == 1)


On EndagorionCodeforces Round #295, 7 years ago

1699 to 1699 ._.