CHFAR - EDITORIAL

chfar
math
simple
snck1b19
taran_1407

#1

PROBLEM LINK:

Practice
Contest

Setter: Misha Chorniy
Tester: Hasan Jaddouh
Editorialist: Taranpreet Singh

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

  • Count number of A* > 1, say C. If C \leq K, we can achieve inequality, otherwise no.

EXPLANATION

First 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. :stuck_out_tongue:

Time Complexity

Time complexity is O(N) per test case.

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution
Tester’s solution
Editorialist’s solution

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


#2

any real number lying between 0 and 1


#3

The Time Complexity is going to O(n)

According to the solution you are providing -

For all integers we have to check -
      ( x != 1 )

which will take O(n) time !
(if we check in linear fashion)

#4

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 YES.

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.


#5

the code i’m using is this :
and i’m getting segmentation fault on submission but not while compiling .
#include
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;

    for(i=0;i<n;i++)
    {
        cin>>a*;
    }
    
    for(i=0;i<n;i++)
    {
        if(a*>1)
        count++;
    }
    if(k>count)
    {
        cout<<"YES"<<endl;
    }
    else{
        cout<<"NO"<<endl;
    }
}
return 0;

}


#6

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*>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.


#7

Challenge: All values lying in the interval (0, 1).


#8

Perfect :slight_smile:

Find real values for which X^3 < X. Enjoy :stuck_out_tongue:


#9

All values lying in (0, 1) or (- \infty, -1).


#10

Seems like I’m running out of math challenges. :stuck_out_tongue:


#11

Hehe…

(Added dots to make 10 characters needed for making a comment)


#12

Thanks for catching. I missed it up. Corrected now :slight_smile:


#13

@setters and testers,
sorry dude, but your algorithm fails at certain test cases. as you just counting the elements which are not ones.
just try your algorithm on my testcase
N = 5, K = 2;
A[] = {1, 2, 3, 5, 8}
sum = 1 + 2 + 3 + 5 + 8 = 19
your algo shows NO for this…

I am just sorting array in reverse order,
so now array will be : A[] = {8, 5, 3, 2, 1}
replace K (2 in this case) elements from start by 1.
now array becomes A[] = {1, 1, 3, 2, 1}
and sum of squares = 1 + 1 + 9 + 4 + 1 = 16, which is less than 19, i.e. answer will be “YES” instead of “NO”.