HLPNISHANT - Editorial

editorial
, , ,
1

PROBLEM LINK:

Contest

DIFFICULTY:

EASY

PREREQUISITES:

Greedy

PROBLEM:

Given positive integer K. Calculate the length of the largest sequence A such that

  • 2\cdot A_i > A_{i-1}+A_{i+1} for all valid i, and
  • 1\le A_i\le K for all valid i.

EXPLANATION:

A sequence is considered optimal if it satisfies the constraints given in the problem, and no other valid sequence of longer length exists.

Claim: There exists an optimal sequence such that its largest element is equal to K.

Proof

Let S be any optimal sequence such that \max S_i < K.

Add K-\max S_i to every element of S. It is clear that \max S_i = K after this. Showing the resultant sequence also satisfies the constraints of the problem is trivial and left to the reader.

Thus, we have an optimal sequence whose largest element equals K.

Let’s now find the length of the largest possible sequence whose greatest element is equal to K. Set A_i=K for some currently unknown i.

Claim: A_1\le A_2\le\dots\le A_i and A_i\ge\dots\ge A_{N-1}\ge A_N.

Proof

We only prove the first claim, by induction (the proof of the second claim can be derived similarly).

Say A_k\le A_{k+1}\le\dots\le A_i holds for some k. Then,

2\cdot A_k > A_{k-1}+A_{k+1}\ge A_{k-1}+A_k\\ \implies A_k \ge A_{k-1}

proving our proposition.
For the base case - all elements are \le K and A_i = K, which implies that A_{i-1}\le A_i, completing the proof.

We now solve greedily.
Either (but not both) of A_{i-1} or A_{i+1} can be equal to K. Without loss of generality, set A_{i+1}=K. Next, greedily assign values for elements A_{i+2},A_{i+3},\dots, to maximise the number of elements.

Example

Let K=12. An optimal greedy assignment would be

[A_i,A_{i+1},A_{i+2},\dots] = [12,12,11,9,6,2]

A bit of experimentation shows us that:

[A_{i+1},A_{i+2},A_{i+3},A_{i+4},\dots] = [K,K-1,K-3,K-6,\dots]

is the best possible assignment, to maximise the number of elements.

Similarly extrapolating the construction for the elements to the left of A_i gives us the complete optimal sequence -

[\dots,K-6,K-3,K-1,K,K,K-1,K-3,K-6,\dots]

So, how many elements are there in it?
Let x equal the number of elements in the subarray [\dots,K-6,K-3,K-1,K]. We know that the value of every element should be greater than 0. A bit of mathematical manipulation shows that -

K-\frac{x(x-1)}{2} > 0\implies 2\cdot K > x(x-1)

Finding the largest possible y such that y(y-1) < 2\cdot K can be done efficiently using binary search (or the std::sqrt() function provided in the math header in C++).

Therefore, since there can be a maximum of y elements in the left and right half of the sequence, the maximum total number of elements is equal to 2\cdot y.

TIME COMPLEXITY:

O(\log K)

per test case.

SOLUTIONS:

Editorialist’s solution can be found here

Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

  • 1
  • 2
  • 3
  • 4
  • 5

0 voters