CAC101 Color Blind - CRACK-A-CODE 1.0 Editorial

editorial
, ,
1

PROBLEM LINK:

Color Blind

Author: mayureshpatle
Tester: mayureshpatle
Editorialist: utkd52

DIFFICULTY:

EASY

PREREQUISITES:

Math, Average

PROBLEM:

For each color there is exactly one color blind child in the sequence and there can be any number of normal children. A color blind child cannot see the candies of the color which he is blind to but can see all other candies. Chef knows the visible candies to each of the child in the sequence.
Chef has to identify the positions of the Color Blind children standing in the sequence.

QUICK EXPLANATION:

Let the total number of candies be C. As mentioned in the question each color has one color blind child standing in the sequence. So each child cannot see candies of one color each and thus the total number of candies unseen will be sum of candies of all color i.e C. We will apply sum formal.

1.Under Normal condition (No child is color blind): Sum = N*C
2.Each color has one color blind child: Sum = (N*C) - C
So, C= \frac{Sum}{N-1}

Now, we can easily find out children who are color blind i.e c_i != C

EXPLANATION:

Consider there are m colors and the same number of color blind children.
The candies of the respective colors be v_1, v_2, v_3.......v_m. Thus the total number of candies will be C = \sum_{i = 1}^{m} v_i
First color blind child cannot see v_1 candies
Second color blind child cannot see v_1 candies
Thus $m$th color blind child cannot see v_m candies
and we know that the sum of all v's is C, Thus we conclude that the total number of unseen candies are indeed C.

Now we take the sum of all c_i given as input
1.Under Normal condition (No child is color blind): Sum = N*C
2.Each color has one color blind child: Sum = (N*C) - C
So, C= \frac{Sum}{N-1}

Now we will simply traverse the inputted vector and mark the children with c_i != C as color blind.

SOLUTIONS:

Setter's Solution 
for _ in range(int(input())):
	n=int(input())
	l=list(map(int,input().split()))
	s=sum(l)//(n-1)
	for i in range(n):
		if s!=l[i]: print(i+1,end=' ')
	print()
Editorialist's Solution 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll t,n,s,i;
    cin>>t;
    while(t--)
    {
        cin>>n;
        ll a[n];
        s=0;
        for(i=0;i<n;++i)
        {
            cin>>a[i];
            s+=a[i];
        }
        s/=n-1;
        for(i=0;i<n;++i)
        {
            if(a[i]!=s) cout<<i+1<<" ";
        }
        cout<<endl;
    }
    return 0;
}
1 Like