PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Hasan
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh
DIFFICULTY:
Medium-Hard
PREREQUISITES:
Dynamic Programming, Slope Trick
PROBLEM:
For an exam, there are N seats in a line numbered from 1 to N, where some seats may be initially empty while others may be occupied. You want to move participants in such a way that in the final arrangement, no two participants are adjacent to each other. Calculate the minimum number of operations to achieve that, where each operation consists of moving one participant from one seat to an adjacent seat.
QUICK EXPLANATION
- If the number of participants is more than \lceil N/2 \rceil, then we cannot arrange them at all. Also, If the number of participants is zero, then the number of operations needed is also 0.
- If we make a list of initial positions of participants L, reduce L_i by 2*i and apply slope trick to get a non-decreasing sequence P attainable at minimum cost and then increase each P_i by 2*i, we can obtain the optimal final positions for participants giving minimum cost.
- The above step ignores the limited number of seats, so we either may use the weighted variant of slope trick, or manually adjust out of bound positions and then calculate minimum operations needed.
EXPLANATION
Let’s suppose there are cnt participants. Firstly, if cnt > \lceil N/2 \rceil, then it is guaranteed that every arrangement shall have at least one adjacent pair of participants, hence, making it impossible to suitably arranging participants. Hence, the answer is impossible in this case.
Also, if cnt is zero, there is no participant, hence the existing arrangement is valid, so we need 0 operations.
Now that we have handled all corner cases, let’s try the original problem.
First subtask solution
Suppose we make a list L where L_i denotes the position of i-th participant from the left. Our aim becomes to apply the minimum number of operations where each operation is to either decrement or increment value at a position, such that after applying operations, L_{i+1} \geq L_i+2 holds for each valid i and 0 \leq L_i < N also holds.
We can use dynamic programming here, where the DP state A(i, j, filled) corresponds to the minimum number of operations required to arrange first j participants in first i seats where filled determines whether seat numbered i is empty or filled.
The base case of this DP would be A(i, 0, 0) = 0 as we do not place any participant, so no operations required.
When considering i-th seat, we may choose to leave it empty, or place a participant here. If we leave it empty, we have state A(i, j, 0) = min(A(i-1, j, 0), (i-1, j, 1)) as we do not care whether the previous seat was empty or filled, and we take the minimum of those.
But, if we want to place a participant at seat i, the minimum number of operations needed become A(i, j, 1) = A(i-1, j-1, 0) + |L_j-i| which is the sum of number of operations needed to place first j-1 participants in first i-1 seats while leaving last seat empty, and the number of operations to move j-th participant to seat i
The required answer is min(A(n, cnt, 0), A(n, cnt, 1)). There are total N^2 states and each state takes constant time computation, so this DP can be computed in O(N^2) time, getting first 50 points.
Code for first subtask
import java.util.*;
import java.io.*;
import java.text.*;
class CCDSAP{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int n = ni();
int[] a = new int[1+n];
int[] ind = new int[1+n];int cnt = 0;
String s = n();
for(int i = 1; i<= n; i++)if(s.charAt(i-1) == '1')ind[++cnt] = i;
long[][][] dp = new long[1+n][2][1+n];
for(int i = 0; i<= n; i++)for(int t = 0; t< 2; t++)Arrays.fill(dp[i][t], (long)1e14);
dp[0][0][0] = 0;
for(int i = 1; i<= n; i++){
for(int j = 0; j<= n; j++){
dp[i][0][j] = Math.min(dp[i-1][0][j], dp[i-1][1][j]);
if(j>0)dp[i][1][j] = dp[i-1][0][j-1]+Math.abs(i-ind[j]);
}
}
long ans = Math.min(dp[n][0][cnt], dp[n][1][cnt]);
if(ans == (long)1e14)pn("impossible");
else pn(ans);
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
DecimalFormat df = new DecimalFormat("0.00000000000");
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new CCDSAP().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Full Solution
Let us view the problem in a different light. We want L_{i+1} \geq L_i+2. So, defining B_i = L_i - 2*i for each valid i, our goal become to convert sequence B into a non-decreasing sequence in minimum operations. Please ignore the bounds for now.
This is a well-known problem, solved by DP trick known as the Slope Trick which considers the exact same problem.
Explaining briefly, it defines function f_i(X) as the minimum cost to make first i elements into a non-decreasing sequence with A_i \leq X. Specifically, f_i(X) = min_{Y \leq X}(f_{i-1}(Y)+|A_i-Y|) for i > 1 and f_1(X) = min_{Y \leq X}(|A_1-x|) noticing that the function f_i(X) is non-increasing and keeping a set of points where slope of this function changes. It is easy to prove that the number of points where the slope changes is up to N.
Now, if we directly apply slope trick to obtain the minimum cost to convert B non-decreasing sequence P, we have run into the issue of bounds.
Considering example 000111, we get L = [3, 4, 5] which gives B = [3, 2, 1]. Now, By applying above trick, we obtain P = [2, 2, 2] as the non-decreasing sequence. Adding back 2*i to P_i, we get P = [2, 4, 6] as the optimal positions for participants. But there is no seat numbered 6.
We can handle this in two ways.
-
Adding
10at the start of the sequence and01at the end of the sequence, and assign weights to all participants. Here, the cost to apply operations becomes the weight assigned to the participant times the absolute distance. We assign weight 1 to all original participants and INF weight to the fictitious participants at both ends, as these ensure trying all arrangements without moving the border participants, thus solving the problem. -
Another way is to actually recover the non-decreasing sequence P and 2*i to P_i for each valid i. Now, considering 0 based numbering for both participants and seats, notice that i-th participant from the left can never be seated in a seat numbered less than 2*i. Also, i-th participant from the right can never be seated in a seat numbered more than N-1-2*i in a valid arrangement. We can, for each participant, find the range of seats where this participant can sit in a valid arrangement.
Now, if the positions P_i lies in the range for i-th participant, well and good. Otherwise, we set P_i to the seat within the participant’s range which is closest to P_i.
Lemma: There shall be a prefix of participants for whom P_i would be to the left of participant’s range and a suffix of participants for whom P_i would be to the right of participant’s range. This lemma can be used to prove that the above process is optimal.
Adhoc Solutions
Interestingly, there also exist Adhoc solutions too. I’ll describe one of them as follows.
Suppose for the given arrangement, we find the number of empty seats between each pair of adjacent participants and also empty seats before the first participant and after the last participants. Say for 01100101, we get [1, 0, 2, 1, 0]. We want all values to be strictly positive and border values to be non-negative. For ease, let’s increment both border values by one, giving [2, 0, 2, 1, 1] and we want to make all values strictly positive.
Our operation now becomes to choose two values, increase one value and decrease the other value by 1. The cost of this operation is the absolute distance between the positions of two chosen values.
Now, considering positions from left to right, whenever we get a 0, we need to increase this value and decrease some other by 1. It can be proved that it is optimal to choose the nearest positioned value which is greater than 1 and apply the operation. Say the nearest position chosen was j We can visualize it as a flow from position j to position i. After repeating this process, we get a set of flows, and it may happen that there is an overlapping canceling flow. So, we need to use Data Structures to process this fastly. The sum of the distance covered by each unit of flow gives the total number of operations.
Code demostrating above idea
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int T;
int arr[1001001];
int nn,n,x;
vector<int> rgt;
vector<int> lft;
int sgt[1001001];
void inc(int l,int r){
for(int i=l;i<=r;i++){
sgt[i]++;
}
}
void dec(int l,int r){
for(int i=l;i<=r;i++){
if(sgt[i] > 0)sgt[i]--;
}
}
int cnt(int l,int r){
int ret=0;
for(int i=l;i<=r;i++){
if(sgt[i] > 0)ret++;
}
return ret;
}
int main(){
cin>>T;
while(T--){
cin>>nn;
int prv= -2;
n=0;
int count =0;
string s;
cin>>s;
for(int i=0;i<nn;i++){
int x = s[i]-'0';
count += x;
if(x == 1){
arr[n++] = i - prv -1;
prv = i;
}
}
if(count > (nn+1)/2){
cout<<"impossible"<<endl;
continue;
}
arr[n++] = nn - prv;
for(int i=0;i<=n;i++){
sgt[i]=0;
}
rgt.clear();
lft.clear();
for(int i=n-1;i>=0;i--){
while(arr[i] > 1){
rgt.push_back(i);
arr[i]--;
}
}
long long sol = 0;
for(int i=0;i<n;i++){
if(arr[i] != 0){
while(rgt.size() > 0 && rgt.back() <= i){
lft.push_back(rgt.back());
rgt.pop_back();
}
continue;
}
bool take_left;
if(rgt.size() == 0){
take_left=true;
} else if(lft.size() == 0){
take_left=false;
} else {
int L_i = lft.back();
int R_i = rgt.back();
if(i - L_i - 2*cnt(L_i,i-1) <= R_i - i){
take_left=true;
} else {
take_left=false;
}
}
if(take_left){
int L_i = lft.back();
lft.pop_back();
sol += i - L_i - 2*cnt(L_i,i-1);
dec(L_i,i-1);
} else {
int R_i = rgt.back();
rgt.pop_back();
sol += R_i - i;
inc(i,R_i-1);
}
}
cout<<sol<<endl;
}
}
Do share your approach, if it differs.
TIME COMPLEXITY
The time complexity is O(N*log(N)) per test case.
SOLUTIONS:
Tester's Solution
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout)
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// find_by_order() // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
#define int ll
main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
//freopen("chairs.in","r",stdin);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
std::priority_queue<int> Q;
//cout<<n<<endl;
int i,val,cnt=0;
vi vec;
string s;
cin>>s;
rep(i,n){
val=s[i]-'0';
if(val==1){
vec.pb(i);
cnt++;
}
}
if(cnt>(n+1)/2){
cout<<"impossible"<<endl;
continue;
}
if(cnt==0){
cout<<0<<endl;
continue;
}
int maxopt=n+1-2*cnt,curopt=-10,sofar=0;
rep(i,vec.size()+4){
Q.push(0);
}
rep(i,vec.size()){
if(Q.top()+2*i<=vec[i]){
curopt=min(maxopt,vec[i]);
Q.push(curopt-2*i);
}
else{
Q.push(vec[i]-2*i);
curopt = Q.top()+2*i;
Q.pop();
Q.push(vec[i]-2*i);
}
sofar+=abs(curopt-vec[i]);
//cout<<sofar<<" "<<Q.top()+2*i<<" "<<vec[i]<<endl;
//cout<<vec[i]<<" "<<curopt<<endl;
maxopt+=2;
}
cout<<sofar<<endl;
}
return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class CCDSAP{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int n = ni();
String s = n();
int[] ar = new int[n];int cnt = 0;
for(int i = 0; i< n; i++)if(s.charAt(i) == '1'){
ar[cnt] = i-2*cnt;
cnt++;
}
//Special Cases
if(cnt > (n+1)/2){
pn("impossible");
return;
}
if(cnt == 0){
pn(0);
return;
}
//The slope trick
//Max Heap
PriorityQueue<Integer> q = new PriorityQueue<>((Integer i1, Integer i2) -> Integer.compare(i2, i1));
q.add(ar[0]);
int[] seq = new int[cnt];
seq[0] = ar[0];
for(int i = 1; i< cnt; i++){
q.add(ar[i]);
if(q.peek() > ar[i]){
q.poll();
q.add(ar[i]);
}
seq[i] = q.peek();
}
//Finding the sequence with minimum cost
for(int i = cnt-2; i>= 0; i--)seq[i] = Math.min(seq[i], seq[i+1]);
//Restoring the sequence of positions with minimum cost
for(int i = 0; i< cnt; i++){
ar[i] += 2*i;
seq[i] += 2*i;
}
//Handling if the position went out of range [0, n-1]
for(int i = 0, pos = 0; i< cnt; i++, pos += 2)seq[i] = Math.max(seq[i], pos);
for(int i = cnt-1, pos = n-1; i >= 0; i--, pos -= 2)seq[i] = Math.min(seq[i], pos);
//Calculating the cost
long ans = 0;
for(int i = 0; i< cnt; i++)ans += Math.abs(ar[i]-seq[i]);
pn(ans);
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
DecimalFormat df = new DecimalFormat("0.00000000000");
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new CCDSAP().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always. 