This Forum is in read only mode now.

You are not logged in. Please login at www.codechef.com to post your questions!

×

CHFAR - EDITORIAL

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[i] > 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. :P

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. :)

This question is marked "community wiki".

asked 29 Oct '18, 01:27

taran_1407's gravatar image

6★taran_1407
4.0k34106
accept rate: 22%

edited 01 Nov '18, 19:41

1

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

(29 Oct '18, 22:27) the_extractor4★

Perfect :)

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

(29 Oct '18, 22:36) taran_14076★
1

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

(29 Oct '18, 22:43) the_extractor4★

Seems like I'm running out of math challenges. :P

(29 Oct '18, 22:47) taran_14076★

Hehe......

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

(29 Oct '18, 23:04) the_extractor4★

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)
link

answered 01 Nov '18, 11:16

pankajdevesh's gravatar image

4★pankajdevesh
412
accept rate: 0%

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

(01 Nov '18, 19:41) taran_14076★

any real number lying between 0 and 1

link

answered 29 Oct '18, 23:46

sandipan789's gravatar image

4★sandipan789
111
accept rate: 0%

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.

link

answered 04 Feb, 22:20

drdang's gravatar image

0★drdang
11
accept rate: 0%

edited 04 Feb, 22:28

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12166

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;

    for(i=0;i<n;i++)
    {
        cin>>a[i];
    }

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

}

link

answered 13 Feb, 20:39

abhhishek's gravatar image

2★abhhishek
1
accept rate: 0%

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.

link

answered 26 Mar, 01:36

refu's gravatar image

3★refu
1
accept rate: 0%

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,191
×890
×729
×61
×12

question asked: 29 Oct '18, 01:27

question was seen: 1,302 times

last updated: 26 Mar, 01:36