 Author: Tianyi
Tester: Riley Borgard
Editorialist: Istvan Nagy

MEDIUM

# PROBLEM:

Chef has failed miserably in several cooking competitions, which makes him think that he’s been out of luck recently. And that’s why he decided to build a magic circle using his chopsticks, hoping this would somehow improve his luck.

The magic circle consists of n chopsticks set on an infinite straight line (yeah… so it’s not actually a circle). The line is drawn on the ground, and chopsticks should be set perpendicular to the ground surface.

The chopsticks are of lengths x_1,x_2,⋯,x_n and the lengths are given to you in input. Each chopstick can be set on the line at any integer position y, after which it will cast a shadow on the range [y,y+x_i]. The chopsticks’ positions y_1,y_2,⋯,y_n should satisfy that, distances between neighbouring chopsticks (i.e. ∣y_i−y_j∣ where chopsticks i,j are adjacent) always fall in the range [L,U], where L and U are fixed integers given in input.

The magic power of the circle depends on the total shadowed length S=∣⋃_i[yi,yi+xi]∣. While Chef expects the circle to take its maximum effect, he can’t help preparing for the worst-case scenario - due to his recent bad luck. So please, help Chef find the minimum AND maximum value of S.

# EXPLANATION

Observation 1: There is a minimum solution where the chopsticks positions are:

0, L, 2*L,..,(n-1)*L.

Proof. If one of the distance is larger than L then we decrease that distance to L without generating more shadow.

Observation 2: There is a maximum solution where the chopsticks positions are:

0, U, 2*U,..,(n-1)*U

We will call a group of chopsticks continuous group if the chopsticks shadow is continuous.
Firstly check a simpler problem when every chopstick is longer than U. In that case it looks quite obvious that we have to order from the longest to the shortest to get the minimum and the opposite order is optimal for the maximum. Unfortunately this algorithm doesn’t give an optimal solution for the original problem in the maximum case E.g:
U=3, x_1=1, x_2=5, x_3=5, the above algorithm gives a solution with a length of shadow 9, but the optimal solution is 10.

Algorithm for the minimum:

• sort the chopsitcks by length
• put the chopsticks from the longest to the shortest from left to right

Algorithm for the maximum:

• put the longest chopstick to the rightest position (n-1)*U

Do the following steps n-1 times:

• select the longest chopstick from the remaining chopsticks
• if the the selected chopstick is longer than U then brake it to get a new one with length U and put back the remaining part to the remaining chopsticks.
• if we are in the i-th step then put this chopstick to the (i-1)*U position

Proof (Minimum):

Observation: If we have a longer chopstick in a continuous group after a shorter we can swap those two without increasing the generated shadow by the group.

Observation 2: If we have two continues group then we can merge it to one or can make two new group where one of the group contains only the shortest chopstick.

Proof: Place the chopsticks next to each other from the shortest chopstick group except the last/ shortest chopstick, after use the chopsticks from the other group in the same order as in the optimal solution, and finally put the shortest chopstick to rightest position (from the first group). The generated shadow cannot be longer than in the optimal solution, and we’ve got a continuous group or a continuous group except the shortest.

Proof (Maximum):

Observation: If we have a continuous group we can move the longest to the rightest position.
Observation 2: We can put the longest chopstick group to the rightest position.

Consider an optimal solution, where the longest chopstick already on the rightest position, so we have remained (n-1) slot with length of U what we would like to cover as much as we can with the remaining chopsticks. Its clear the algorithm is an upper bound for the optimal solution. For the lower bound we can construct a solution which has the same generated shadow as the algorithm:

Sort the used chopsticks by its (original chopstick id, part id) and place the chopstick where its id and the 0 parts occur.

# TIME COMPLEXITY:

O(n\log(n)) per test case

# SOLUTIONS:

Setter's Solution
``````#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair < int , int > pii;
typedef pair < LL , LL > pll;
#define mpr make_pair
#define FS first
#define SC second
#define PB push_back
template < typename T > void UMAX(T &a,T b){a=(a>b?a:b);}
template < typename T > void UMIN(T &a,T b){a=(a<b?a:b);}
char c=getchar();
LL ret=0ll;
bool neg=0;
while(!(c>='0' && c<='9')){
if(c=='-') neg=1;
c=getchar();
}
while(c>='0' && c<='9'){
ret=ret*10ll+(LL)(c-'0');
c=getchar();
}
return neg?-ret:ret;
}
void putint(LL v){
if(v<0){
putchar('-');
v=-v;
}
if(!v){
putchar('0');
return;
}
if(v>=10ll) putint(v/10ll);
putchar('0'+(v%10ll));
}
int n,L,R,a;
LL getlow(){
sort(a,a+n);
LL rr=(LL)(n-1)*L,rl=(LL)(n-1)*L-a[n-1];
int sr=n-1;
for(int i=0;i<n-1;++i){
if(a[i+1]>L){
if(sr==n-1) sr=i;
UMIN(rl,(LL)i*L-a[i]);
}
}
LL res=rr-rl;
for(int i=sr-1;i>=0;--i){
LL cl=(LL)i*L-a[i],cr=min((LL)i*L,rl);
res+=max(0ll,cr-cl);
}
return res;
}
LL gethigh(){
sort(a,a+n);
reverse(a,a+n);
LL res=a+(LL)(n-1)*R;
priority_queue < int > ls;
for(int i=1;i<n && a[i]>R;++i){
ls.push(a[i]-R);
}
for(int i=n-1;i>0 && a[i]<R;--i){
if(ls.empty()){
res-=R-a[i];
}
else{
int tp=ls.top();
ls.pop();
res-=R-min(R,max(a[i],tp));
if(tp>R){
ls.push(tp-R);
}
}
}
return res;
}
int main(){
while(t--){
putint(getlow());putchar(' ');
putint(gethigh());putchar('\n');
}
return 0;
}
``````
Tester's Solution
``````#include <bits/stdc++.h>

#define ll long long
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define pii pair<int, int>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;
template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;

void solve() {
int n; ll L, U;
cin >> n >> L >> U;
vi x(n);
rep(i, 0, n) cin >> x[i];
vector<pair<ll, ll>> ve;
auto overlap = [&]() -> ll {
ll ans = 0;
vector<pair<ll, int>> e;
for(auto &pa : ve) {
e.push_back({pa.first, 1});
e.push_back({pa.second, -1});
}
sort(all(e));
ll x = -1; int cnt = 0;
for(auto &pa : e) {
if(cnt > 0) ans += pa.first - x;
x = pa.first;
cnt += pa.second;
}
return ans;
};
sort(all(x), greater<>());
rep(i, 0, n) {
ve.push_back({L * i, L * i + x[i]});
}
ll Smin = overlap();

ll Smax = x + U * (n - 1);
ll sum = 0;
rep(i, 1, n) {
sum += x[i] / U;
x[i] = U - (x[i] % U);
}
sort(1 + all(x));
rep(i, 1, n - sum) {
Smax -= x[i];
}

cout << Smin << ' ' << Smax << '\n';
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int te;
cin >> te;
while(te--) solve();
}
``````
Editorialist's Solution
``````#include <iostream>
#include <cassert>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <random>
#include <cstdint>

#ifdef HOME
#include <windows.h>
#endif

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }

using namespace std;

int main(int argc, char** argv)
{
#ifdef HOME
if(IsDebuggerPresent())
{
freopen("../in.txt", "rb", stdin);
freopen("../out.txt", "wb", stdout);
}
#endif
int T;
cin >> T;
forn(tc, T)
{
int n, L, U;
cin >> n >> L >> U;
vector<int> x(n);
for (auto& xi : x)
cin >> xi;
sort(x.begin(), x.end());
reverse(x.begin(), x.end());

int64_t mi = 0;
int64_t mxpos = 0;
int64_t cpos = 0;
for (auto xi : x)
{
mxpos = max<int64_t>(cpos + xi, mxpos);
mi += min<int64_t>(mxpos - cpos, L);
cpos += L;
}
if (mxpos > cpos)
mi += mxpos - cpos;
multiset<int, greater<int>> xs;
for (auto xi : x)
{
xs.insert(xi);
}
int64_t mx = *xs.begin();
xs.erase(xs.begin());
int insertcounter = 1;
while (!xs.empty() && insertcounter < n)
{
int largest = *xs.begin();
xs.erase(xs.begin());
if (largest > U)
{
mx += U;
xs.insert(largest - U);
}
else
{
mx += largest;
}
++insertcounter;
}
printf("%lld %lld\n", mi, mx);
}
return 0;
}

``````

If you have other approaches or solutions, let’s discuss in comments.

1 Like

The problem statement did not mention the word “join”/“break” anywhere, i.e., we were not told we can break or join chopsticks. So when you mention:

then brake it to get a new one with length U and put back the remaining part to the remaining chopsticks

I had a bit of trouble understanding why we are doing it. Maybe worth mentioning why we are doing it.

As far as I can tell, this works because the broken up parts of the original chopstick will be successively placed back right next to each other (if no longer chopsticks exist). For example, if x_i=50 and U=10, then we may end up placing 10,10,10,10,10 into the queue (if other chopsticks of length longer than 10 don’t exist). We can treat these multiple chopsticks as one single chopstick of length 50, without invalidating any requirement of original question.

If eventually some broken part does not get placed anywhere, we can just assume its shadow overlaps with the shadow of some other chopstick that was already in place.

I hope this understanding is correct.

Hey guys,
please provide some test cases on which my programme not works.I solved this but it is giving wrong ans.Seems like some edge case is missing from my analysis…Please help me.

#include<bits/stdc++.h>
using namespace std;

int main()
{
int t; cin >> t;
while(t–)
{
int smax = 0, smin = 0;
int * x, n, l, u;
cin >> n >> l >> u;
x = new int[n];
for(int i = 0; i < n; i++)cin >> x[i];
sort(x, x + n);
int remain = 0;
for(int i = 0; i < n; i++)
{
remain = max(remain, x[i]);
if(remain >= u)
{
smax += u;
remain -= u;
}
else
{
smax += remain;
remain = 0;
}
}
smax += remain;
remain = 0;
for(int i = n - 1; i >= 0; i–)
{
remain = max(remain, x[i]);
if(remain >= l)
{
smin += l;
remain -= l;
}
else
{
smin += remain;
remain = 0;
}
}
smin += remain;
cout << smin << " " << smax << endl;
}
return 0;
}