PROBLEM LINK:
(CodeChef: Practical coding for everyone)
Author: Nitish Dubey
Tester: Manik Goenka
Editorialist: Bratati Chakraborty
DIFFICULTY:
EASY
PREREQUISITES:
Basic Math
Loops
Array
Sorting
PROBLEM:
There is a lake of perimeter K units and there are N coconut trees around it. The i-th tree is located at a distance of A_i from the northern-most point of the lake. We have to traverse around the lake in such a way that each tree is passed at least once. Then, we need to return the minimum distance covered to do the same.
QUICK EXPLANATION:
We can find out the distance between every two consecutive trees while traveling in the clockwise direction. Then, we need to figure out the maximum of these distances. Let’s name this max\_diff. Also, you have to find the total sum of all the distances in between the consecutive trees and add the distance between the last tree and the first tree as well. Let’s call this final sum ans. Now, I can get the minimum required distance by simply subtracting max\_diff from ans.
EXPLANATION:
Since, we need to find the minimum distance traveled to pass by every tree once, we can always ignore the longest distance between two consecutive trees. So, now you can store the distance between every two adjacent trees in an array considering clockwise traversal. And you need to include the anticlockwise distance between the last tree and the starting point as well (n-th to 0-th index of the array).
Then, you can find the maximum of these distances (max\_diff) and the sum of all these distances (ans) that includes sum up to n-1 index plus the anti-clockwise distance from 0 to n-1 index. Finally, execute ans - max\_diff to get the minimum distance required.
An easier way to do this would be to sort the array that consists of the distances between the adjacent trees. Then, you can find the sum of all these distances and subtract the last distance in this array from the sum (because the last distance in the array is the largest distance).
TIME-COMPLEXITY:
O(n)
SPACE-COMPLEXITY:
O(1)
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
//ABBREVIATION/
#define ll long long int
#define mod 1000000007
#define vi vector<ll>
#define vic vector<char>
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define sz(x) (x.size())
#define CASE(t) cout<<"Case #"<<(t)<<": "
#define mii map<ll,ll>
#define mci map<char,ll>
//LOOPS//
#define f(i,a,b) for(ll i=a;i<b;i++)
#define rf(i,a,b) for(ll i=a;i>=b;i--)
#define rep(i,n) f(i,0,n)
#define rrep(i,n) rf(i,n-1,0)
#define w(t) ll t; cin>>t; while(t--)
//max-min/
#define max3(a, b, c) max(max(a, b), c)
#define min3(a, b, c) min(min(a, b), c)
//PRINT//
#define no cout<<"NO"<<endl
#define yes cout<<"YES"<<endl
#define print(a) cout<<a<<endl
#define line cout<<endl
// SORTING//
#define all(V) (V).begin(),(V).end()
#define srt(V) sort(all(V))
#define sortGreat(V) sort(all(V),greater<ll>())
//INPUT//
#define in ll n;cin>>n;
#define input rep(i,n){cin>>a[i];}
using namespace std;
void nitishcs414()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}
int main()
{
nitishcs414();
w(t)
{
ll k,n;
cin>>k>>n;
ll a[n],sum=0,mn=1000000;
rep(i,n)
{
cin>>a[i];
}
f(i,1,n)
{
sum=k-a[i]+a[i-1];
mn=min(mn,sum);
}
print(min(mn,a[n-1]-a[0]));
}
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
#define int long long int
#define mod 1000000007
#define f(i,a,b) for(int i=a;i<b;i++)
#define rf(i,a,b) for(int i=a;i>=b;i--)
#define rep(i,n) f(i,0,n)
#define rrep(i,n) rf(i,n-1,0)
#define w(t) int t; cin>>t; while(t--)
#define vi vector<int>
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define mii map<int,int>
#define mci map<char,int>
#define inf (int)(1e18)
using namespace std;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int bin_expo(int x, int n, int m)
{
x %= m;
int res = 1;
while (n)
{
if (n & 1)
res = res * x % m;
x = x * x % m;
n >>= 1;
}
return res;
}
void coder99()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}
int32_t main()
{
coder99();
w(t)
{
int k, n;
cin >> k >> n;
int a[n];
rep(i, n)
{
cin >> a[i];
}
int max_diff = 0, ans = 0;
rep(i, n - 1)
{
max_diff = max(max_diff, (a[i + 1] - a[i]));
ans += a[i + 1] - a[i];
}
ans += k - a[n - 1] + a[0];
max_diff = max(max_diff, k - a[n - 1] + a[0]);
ans -= max_diff;
cout << ans << "\n";
}
return 0;
}