CHFAR - EDITORIAL (Unofficial)

[admin5]

PROBLEM LINK:

Practice
Contest

Author: mgch
Editorialist: admin5

DIFFICULTY:

Simple

PREREQUISITES:

Basic implementation

PROBLEM:

You are given a sequence of positive integers A₁,A₂,…,A_N and K, you can replace at most K element of sequence with any positive integer.
and check whether it is achievable or not A₁²+A₂²+⋯+A_N² ≤ A₁+A₂+⋯+A_N .

QUICK EXPLANATION:

• Sort the given sequence of numbers in descending order.
• Replace first K elements with 1.
• check whether it is achievable or not A₁²+A₂²+⋯+A_N² ≤ A₁+A₂+⋯+A_N .

EXPLANATION:

You are given a sequence of positive integers A₁,A₂,…,A_N and K.
Here we need to minimize the numbers which are large enough because contribution of large numbers to make given condition false than the small number.

A₁²+A₂²+⋯+A_N² ≤ A₁+A₂+⋯+A_N

in this equation we need to minimize the sum of squares so after sorting the given sequence of integers in descending order we can replace first K elements with 1 because 1² = 1, we can’t get minimum than this.

Check whether given condition is true or not.

Time Complexity

Time complexity is O(N*log(N)) per test case.

SOLUTIONS:

Editorialist’s solution can be found here.

Feel free to Share your approach, If it differs. Suggestions are always welcomed.

[utkalsinha]

If the idea is to replace first K non-ones with 1s, then why not simply count the number of non-ones in the array an check if the count is > K. No sorting is required. Time complexity is O(n). Sorting seems like an overkill.

[admin5]

this is great.