VKURI - Editorial



First of all, Sorry for the immature stories in the problem statement in the contest. We thought of having it as a closed contest, that’s why we chose those kind of weird statements and name.

Anyways, lets dive into the problem.

Problem statement:

Maximize the number of positive distinct integers that can be used to get a sum N(N<=1e18).


We can always greedily choose distinct integers to be as small as possible to maximize the number of distinct integers that can be used.

Lets say we are going to use the first X natural numbers, let their sum be F(X). So we need to find a maximum X such that F(X) <= N.

We can solve the above equation by either quadratic formula(X=floor((-1+sqrt(1+8$*$N))/2) or by binary search.

Why does the above mentioned observation always works?

Lets say our method found the value to be P but there exists a way to write N as P+1 distinct positive integers. Since an answer of P+1 exists F(P+1) must be <= N. If F(P+1) <= N then our method would have found it, which is clearly a contradiction.

Time Complexity : O(1)

C++ Solution

how to solve this question by using binary search?

check the following link for the concept of how to solve monotonic functions using binary search.https://www.google.co.in/amp/s/www.geeksforgeeks.org/find-the-point-where-a-function-becomes-negative/amp/ .also look at this beautiful application of binary search called “aggressive cows problem”