CHFAR - EDITORIAL (Unofficial)

PROBLEM LINK:

Practice
Contest

Author: mgch
Editorialist: admin5

DIFFICULTY:

Simple

PREREQUISITES:

Basic implementation

PROBLEM:

You are given a sequence of positive integers A1,A2,…,AN and K, you can replace at most K element of sequence with any positive integer.
and check whether it is achievable or not A12+A22+⋯+AN2 ≤ A1+A2+⋯+AN .

QUICK EXPLANATION:

  • Sort the given sequence of numbers in descending order.
  • Replace first K elements with 1.
  • check whether it is achievable or not A12+A22+⋯+AN2 ≤ A1+A2+⋯+AN .

EXPLANATION:

You are given a sequence of positive integers A1,A2,…,AN 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.

A12+A22+⋯+AN2 ≤ A1+A2+⋯+AN

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 12 = 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. :slight_smile:

1 Like

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.

1 Like

this is great. :wink: