CHFCIRCL - Editorial

PROBLEM LINK:

Practice
Contest

Author: Shailesh Anand

DIFFICULTY:

EASY

PREREQUISITES:

Arrays, Sorting

PROBLEM

Given an array of n elements, determine whether it is possible to rearrange the elemtents in a circular list such that for any three consecutive numbers the sum of 1^{st} and 3^{rd} is greater than 2^{nd} number.

EXPLANATION

Here in this problem we have to print YES if the condition given in the question is being satisfied else we just have to print NO.
We have to check if the numbers given g by user the if they are kept in a circle then, the number should be strictly less than its neighbouring numbers.

For this after taking the input we will sort the list in the descending order. Now we only need to check if a[0] < a[1] + a[2] , that is biggest number in array is smaller than 2^{nd} and 3^{rd} biggest numbers. Why? Since we have sorted array in descending order, consider any random number say a[5] than one of its neighbour will be a[4] and a[6]. Since array is sorted a[4] is bigger than a[5] , a[5] < a[4] + a[6]. This holds for all the array elements except the largest element. a[0] must be greater than a[1] and a[2]. So we check only this condition.

if this condition is satisfied , we will print YES. Note that a is sorted in descending order and not the original array. Now you pick any random element a[3] its neighbours are a[2] and a[4]. Now a[2] > a[3] , hence a[3] < a[2] + a[4].

Time Complexity:

O(nlog(n))

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;

template <typename T>
void display(T x)
{
     cout << x << endl;
}

template <typename T>
vector<T> readvector(size_t l)
{
    vector<T> vec;
    size_t i;
    T a;
    for (i = 0; i < l; i++)
    {
        cin >> a;
        vec.push_back(a);
    }
    return vec;
}
void solve(vector<int32_t> nums, int32_t n)
{
    std::sort(nums.begin(), nums.end(), [](int32_t x, int32_t y) {
        return x > y;
    });
    if (nums[0] < nums[1] + nums[2])
    {
        display("YES");
    }
    else
   {
        display("NO");
   }
}
int main()
{
    int32_t n_test_cases = 1;
    cin >> n_test_cases;
    while (n_test_cases--)
    {
        int32_t n;
        cin >> n;
        vector<int32_t> nums = readvector<int32_t>(n);
        solve(nums, n);
    }
    return 0;
}