PROBLEM LINK:
Practice
Contest: Division 3
Contest: Division 2
Contest: Division 1
Author: Tianyi
Tester: Riley Borgard
Editorialist: Istvan Nagy
DIFFICULTY:
MEDIUM
PREREQUISITES:
Sort, Binary search tree, ad-hoc
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:
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:
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);}
LL readint(){
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[100005];
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[0]+(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(){
int t=readint();
while(t--){
n=readint();L=readint();R=readint();
for(int i=0;i<n;++i) a[i]=readint();
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[0] + 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.