PROBLEM LINK:Setter: Misha Chorniy DIFFICULTY:Simple PREREQUISITES:Basic Math. PROBLEM:Given a sequence $A$ of length $N$, by changing at most $K$ elements, can we make $A_1^2+A_2^2+A_3^2 \dots A_N^2 \leq A_1+A_2+A_3 \dots A_N$? SUPER QUICK EXPLANATION
EXPLANATIONFirst of all, It can be seen that for every integer $X$, $X \leq X^2$. So, we can prove that we can never achieve $A_1^2+A_2^2+A_3^2 \dots A_N^2 < A_1+A_2+A_3 \dots A_N$. Only option is, to achieve $A_1^2+A_2^2+A_3^2 \dots A_N^2 == A_1+A_2+A_3 \dots A_N$. Now, Let's find all integers, for which $X^2 == X$. We can find, that This holds for only $X = 0$ and $X = 1$. But we can assign only positive values to elements. Hence, to achieve this inequality, we need all elements to be 1. Hence, just count the number of elements greater than 1 and if this count is $\leq K$, we can achieve this inequality, otherwise, we cannot achieve. Challenge Find any real value for which $X^2 < X$. Enjoy solving. :P Time ComplexityTime complexity is $O(N)$ per test case. AUTHOR'S AND TESTER'S SOLUTIONS:Setter's solution Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)
This question is marked "community wiki".
asked 29 Oct '18, 01:27

The Time Complexity is going to O(n)According to the solution you are providing 
answered 01 Nov '18, 11:16

Minimum value for k is 1 ,$1 \leq K \leq N \leq 10^4$ So if initially suppose all numbers are one,for eg. $n=3$ $k=2$ $A=\{1,1,1\}$ Now because minimum value of k is 1 not zero so in all cases we have to consider value of k=1 But non $1$ number count is zero as all three numbers are $1$ from example above.
so according to your solution result should be But as we have to consider at least $k=1$ So your solution fails as changing any of the three 1's to other value will not yield the desired result. Please reply if i am wrong. answered 04 Feb, 22:20

the code i'm using is this : and i'm getting segmentation fault on submission but not while compiling . include <iostream>using namespace std; int main() { // your code goes here int t; int a[100]; cin>>t; while(t){ int n,k,count=0,i; cin>>n>>k;
} answered 13 Feb, 20:39

I don't get it... This is a counter example for this solution or not? array = [2, 2, 1, 2] k = 2 "Count number of A[i]>1, say C. If C≤K, we can achieve inequality, otherwise no." The number of elements where the value is greater than 1 is 3 in the array [2, 2, 1, 2], so C = 3, and if K = 2, then this is a possible solution: [1^2, 1^2, 1^2, 2^2] <= [2, 2, 1, 2] // We change 2 of the elements to 1 7 <= 7 But the algorithm in this editorial is give the answer "NO" for this input. And I think my solution can't accepted because of this. answered 26 Mar, 01:36

Challenge: All values lying in the interval $(0, 1)$.
Perfect :)
Find real values for which $X^3 < X$. Enjoy :P
All values lying in $(0, 1)$ or $( \infty, 1)$.
Seems like I'm running out of math challenges. :P
Hehe......
(Added dots to make 10 characters needed for making a comment)