AVGARR-Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Jeevan Jyot Singh
Tester: Nishank Suresh, Satyam
Editorialist: Devendra Singh

DIFFICULTY:

Simple

PREREQUISITES:

The mean of an array B of size M is defined as: \texttt{mean}(B) = \dfrac{\sum_{i = 1}^{M} B_i}{M}.

PROBLEM:

You are given two integers N and X. Output an array A of length N such that:

  • -1000 \le A_i \le 1000 for all 1 \le i \le N.
  • All A_i are distinct.
  • \texttt{mean}(A) = X.

If there are multiple answers, print any. It is guaranteed that under the given constraints at least one array satisfying the given conditions exists.

As a reminder, the mean of an array B of size M is defined as: \texttt{mean}(B) = \dfrac{\sum_{i = 1}^{M} B_i}{M}.

For example, \texttt{mean}([3, 1, 4, 8]) = \frac{3 + 1 + 4 + 8}{4} = \frac{16}{4} = 4.

EXPLANATION:

The problem can be divided into two cases:

\textbf{Case 1}: N is even. To achieve an average of X , the sum of all the values of array A must be N\cdot X. We simply create N/2 pairs such that their sum is 2\cdot X each. Total sum of these pairs would be 2\cdot X\cdot N/2 = N\cdot X
Therefore the average of these N values is (N\cdot X)/N = X . One possible way to create these pairs is to pair values around X i.e X-1\: and\: X+1 ,X-2\: and\: X+2 and so on.
To print the answer for this case run a loop from i=1 to i=N/2 and on each iteration print two values X-i and X+i.
\textbf{Case 1}: N is odd. To achieve an average of X , the sum of all the values of array A must be N\cdot X. We simply create (N-1)/2 pairs such that their sum is 2\cdot X each and append X to the end of the array. Total sum of these pairs would be 2\cdot X\cdot (N-1)/2 +X= N\cdot X - X +X= N\cdot X
Therefore the average of these N values is (N\cdot X)/N = X . One possible way to create these pairs is to pair values around X i.e X-1\: and\: X+1 ,X-2\: and\: X+2 and so on.
To print the answer for this case run a loop from i=1 to i=(N-1)/2 and on each iteration print two values X-i and X+i. Then print X in the end.

The value of A_i never exceeds 600 and never drops below -500 in this approach which satisfies the given constraints.

TIME COMPLEXITY:

O(N) for each test case.

SOLUTION:

Setter's solution
#ifdef WTSH
    #include <wtsh.h>
#else
    #include <bits/stdc++.h>
    using namespace std;
    #define dbg(...)
#endif

#define int long long
#define endl "\n"
#define sz(w) (int)(w.size())
using pii = pair<int, int>;

const long long INF = 1e18;

const int N = 1e6 + 5; 

void solve()
{
    int n, x; cin >> n >> x;
    vector<int> a;
    for(int i = 1; i <= n / 2; i++)
        a.push_back(x - i), a.push_back(x + i);
    if(n % 2)
        a.push_back(x);
    for(int x: a)
        cout << x << " ";
    cout << endl;
}

int32_t main()
{
    ios::sync_with_stdio(0); 
    cin.tie(0);
    int T; cin >> T;
    for(int tc = 1; tc <= T; tc++)
    {
        // cout << "Case #" << tc << ": ";
        solve();
    }
    return 0;
}
Tester-1's Solution(Python)
for _ in range(int(input())):
	n, x = map(int, input().split())
	for i in range(n//2):
		print(x-i-1, x+i+1, end = ' ')
	if n%2 == 1:
		print(x)
	else:
		print('')
Tester-2's Solution
#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE    
#define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline;
#else
#define debug(x);  
#endif 
 
 
/*
------------------------Input Checker----------------------------------
*/
 
long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        if(g=='-'){  
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);
 
            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            if(is_neg){
                x= -x;
            }
 
            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }
 
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        assert(g!=-1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}
 
 
/*
------------------------Main code starts here----------------------------------
*/
int MAX=100000;
void solve(){
    int n=readIntSp(1,1000);
    int x=readIntLn(0,100);
    if(n&1){
        cout<<x<<" "; n--;
    }
    int l=-5,r=2*x+5;
    for(int i=1;i<=n;i+=2){
        cout<<l--<<" "<<r++<<" "; 
    }
    cout<<"\n";
    return;
}
int main(){
    ios_base::sync_with_stdio(false);                         
    cin.tie(NULL);                              
    #ifndef ONLINE_JUDGE                 
    freopen("input.txt", "r", stdin);                                              
    freopen("output.txt", "w", stdout);  
    freopen("error.txt", "w", stderr);                          
    #endif         
    int test_cases=readIntLn(1,100); 
    while(test_cases--){
        solve();
    }
    assert(getchar()==-1);
    return 0;
}

Editorialist's Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
const int N = 1e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void sol(void)
{
    int n, x;
    cin >> n >> x;
    if (n & 1)
    {
        cout << x << ' ';
        for (int i = 1; i <= (n / 2); i++)
            cout << x - i << ' ' << x + i << ' ';
        cout << '\n';
    }
    else
    {
        for (int i = 1; i <= (n / 2); i++)
            cout << x - i << ' ' << x + i << ' ';
        cout << '\n';
    }

    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int test = 1;
    cin >> test;
    while (test--)
        sol();
}

In the problem statement you have mentioned an example in which the mean is coming as a decimal number but the editorial part is saying mean is in integer and in whole contest i am struggling to solve only because of this.

And now in editorial part @devendra7700 you have change the problem statement example by replacing 5 with 8 and now it is giving the mean value as an integers why u have replace this?

https://www.codechef.com/viewsolution/62903077
why did my soln fail ?? Any guide will be appreciated !
my approach is as follows :

  1. set two pointers, one at 1 and another at 1000

  2. make a sliding window of size ( n - 1 ) such that sum of these consecutive elements in the window is >= ( n*x )
    [will be operating using the above two pointers ]

  3. Then I will initialize first n-1 values of my ans array with these values of sliding window I found.

  4. nth element of ans array will be ( req_sum - tot_sum ) where,
    tot_sum = sum of n-1 elements of the sliding window and
    req_sum = n*x

n=100, x=10

req=1000
news=(100*99)/2=4950

a[n-1]=1000-4950=-3950
a[n-1]<-1000

every element of your answer array should be in the range (-1000<=a[i]<=1000)

hey @jatin2929
Thanks for sharing your doubt.
That was a just example that explains how the mean is calculated. Although it is clearly mentioned in the problem that X is an integer.

You are given two integers N and X

I think you misread the problem statement.

2 Likes

Can someone tell me for which testcase am I getting wrong?
sol

thnx a lot !! got the mistake

https://www.codechef.com/viewsolution/62804926

can someone tell me for which sample testcase my approach would give wrong answer? I can’t seem to find the corner case.

Hey @musharafzm :wave: ,
Your code is failing for the test case
1
1000 14

Here your code is printing 77 two times and that is the reason one of a TC is failing.

https://www.codechef.com/viewsolution/62970920

Can anyone please tell me whats wrong in this code and how I can find out and debug that particular error during a contest?

Hey @codersidhant :wave: ,
Your logic is right but question also have a condition that is -1000 >= Ai <= 1000.
1
7 1000
Your code is printing an array that has element not satisfying the condition.
You can debug by giving inputs that are strict (means corner cases) just like you did here check always that for every worst case scenario how your code will print you will soon get the error then.

@jatin0308_adm But sir the constraint on X is 0≤X≤100 this no?
Also according to the editorial the ans should be 997 998 999 1000 1001 1002 1003 which also is not satisfying the condition.

Hey @codersidhant ,
yes you are right x <= 100 my bad. Your code is giving WA on this test case
1
1000 100
printing 10^5 which violates the condition.

@jatin0308_adm Yes now I got it thank you very much.

I did not understand use of “if(n&1)” . is it for odd numbers?

#include<bits/stdc++.h>

using namespace std;

void Solve(vector& v, int n, int x){

if(n == 0)  cout<<0<<endl;

int res =  n*x;

int coff = 0;

vector<int> ans;

if(n>1){

    for(int i = 1; i < n;i++){

        coff += i;

    }

}

if(n>0){

    int f = (res-coff)/n;

    int itr= 0;

     while (itr<n)

     {

         ans.push_back(f);

        f++;

        itr++;

    }

    for(int i = 0; i < n;i++){

        cout<<ans[i]<<" ";

     }cout<<"\n";

}

}

int main(){

int t;

cin>>t;

while (t--)

{

    int n,x;

    cin>>n>>x;

    vector<int> v(n);

    Solve(v,n,x);

}



return 0;

}

can any one explain why i am getting wrong answer? thanks in advance

I am using simple math x +x+1+x+2+…+x+n-1 = X;

Yes “&” is a bitwise and operator which checks if a number is odd or even.
For example:3 & 1=1 and 4 & 1=0 .