THENECKL - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice

Contest

Author: Sibasish Ghosh

Tester: Pritish Nayak

Editorialist: Sibasish Ghosh

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

You are given N beads connected in a cyclic manner to form a necklace. Every bead can has some colour. The cost of the necklace is equal to the number of distinct colours present in the necklace. You have to tell the minimum possible cost of the necklace.

QUICK EXPLANATION:

Just move to next section.

EXPLANATION:

The solution is based on some simple observations:

  • If N == 1, then answer is directly 1. Cause there can’t be more one colour.
  • Else if N is even, then you can always use 2 colours to make the necklace. Let the colours be a and b. So you can just follow the scheme a,b,a,b,a,b...
  • Else if N is odd, then you can always use 3 colours to make the necklace. We can use the same colouring as in the even case, but the catch is with the last bead. It’s neighbouring elements will be both a and b. So we will be forced to introduce a third colour c.

SOLUTIONS:

Setter's/Editorialist's Solution 
#include<bits/stdc++.h>
#define mod 1000000007
#define F first
#define S second
#define pb push_back
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
 
using namespace std;
typedef long long int ll;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen("input2.txt","r",stdin);
    // freopen("output2.txt","w",stdout);
    ll t=1;
    cin>>t;
    while(t--)
    {
        ll n;
        cin>>n;
        if(n == 1)
            cout<<"1\n";
        else if(n & 1)
            cout<<"3\n";
        else cout<<"2\n";
    }
    return 0;
}
Tester's Solution 
#include<bits/stdc++.h>
using namespace std;
 
int main()
{
  ios_base::sync_with_stdio(false);cin.tie(NULL);
  int t;
  cin>>t;
  while(t--)
  {
    long long n;
    cin>>n;
    if(n==1)cout<<1;
    else if(n%2==0)cout<<2;
    else cout<<3;
    cout<<'\n';
  }
  return 0;
}

Feel free to write your approach in the comments :slight_smile:

4 Likes