PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Ritesh Gupta
Tester: Radoslav Dimitrov
Editorialist: Taranpreet Singh
DIFFICULTY
Easy-Medium
PREREQUISITES
Dynamic programming and observations.
PROBLEM
Given a circular array A of length N i.e. A_i and A_{i+1} are considered adjacent. Also, A_1 and A_N are also considered adjacent. Initially, the whole sequence consists of 0s and 1s only. In one operation, you must choose a position p such that A_p = 1, set A_p = 0 and choose any position adjacent to p and increment it by 1.
A sequence is considered good if all its elements are different from 1. Find out the minimum number of operations
QUICK EXPLANATION
- The base cases are when the sequence A contains at most one 1.
- The final sequence shall consist of 0s, 2s, and 3s.
- Considering the non-cyclic version, the problem becomes to divide the set of positions of 1s into groups of size 2 and 3 such that the total cost is minimum. The cost for a group is the minimum number of operations required to get all 1s in the same group at the same position.
- For the cyclic variant, we just need to solve the non-cyclic variant 3 times, each time doing a cyclic rotation of sequence such that exactly one 1 moves from start to end of the sequence.
EXPLANATION
First off, let’s consider base cases.
- If the sequence consists of 0s only, then the sequence is already good, hence the answer is zero.
- If the sequence consists of exactly one 1, then it’s impossible to make the sequence good.
In all other cases, it is possible to make the sequence good by a sequence of operations.
Proof: Just perform operations till all 1s are merged into a single position. Since the number of 1s is greater than 1, the sequence won’t contain any occurrence of 1 at the end.
Let’s move to find the minimum number of operations.
Lemma: The final sequence shall consist of 0s and 2s and 3s.
Proof: Let us assume that the final sequence contains an occurrence of 4. Let us assume the positions of 1s to be p_1 < p2 < p3 < p4 and the position containing 4 is p. But, it is better to bring 1s at p1 and p2 in the same position, and at p3 and p4 at the same position (technically splitting 4 into two 2s). We can similarly prove that values \geq 4 cannot appear in the final sequence in minimum operations.
Let’s ignore the cyclic condition for now.
Consider S as the sequence of positions p such that A_p = 1, in sorted order. We can now see that the problem has now become to partition the whole sequence S into groups of size 2 and 3 at minimum cost such that each position is a part of exactly one group. The cost of partitioning is sum of the cost of each group, and the cost of each group is just the absolute difference between the leftmost and rightmost position in the group.
Didn't understand, We want more!
Consider only two 1s, one at position p1 and one at position p2 such that p1 < p2. What is the minimum number of operations?
Answer
p2-p1
Consider only three 1s, one at position p1, one at position p2 and one at position p3 such that p1 < p2 < p3. What is the minimum number of operations?
Answer
p3-p1
The above problem can be easily solved with dynamic programming. Let DP_x denote the minimum cost of partitioning first x positions into groups. It is easy to deduce the recurrence by considering groups of size 2 and 3 ending at position x and taking the minimum.
Give us the recurrence
DP_x = min(DP_{x-2} + S_x-S_{x-1}, DP_{x-3}+S_x-S_{x-2})
The minimum number of operations is given by DP_{|S|}
Coming back to the cyclic variant. Let us suppose we have split the sequence of positions into groups of size 2 and 3. By considering the cyclic sequence, the only case we have missed is when in optimal partitioning, some 1s from the end of the sequence S grouping with some 1s at the start give lower cost.
But since the group size is at most 3, an easy way to deal with this would be to solve the non-cyclic version of this problem three times, each time rotating the sequence A till exactly one 1 moves from start to end.
This way, we are guaranteed that in one shift, the border of non-cyclic array coincides with the border of the group, in which case the answer of the non-cyclic version on this rotation is the required answer.
TIME COMPLEXITY
The time complexity is O(N) per test case.
SOLUTIONS
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
vector <int> v,v1;
int dp[1000010];
int solve()
{
dp[0] = 0;
dp[1] = 1e9;
dp[2] = v[1] - v[0];
for(int i=2;i<v.size();i++)
dp[i+1] = min(v[i]-v[i-1]+dp[i-1], v[i]-v[i-2]+dp[i-2]);
return dp[v.size()];
}
int main()
{
int t;
cin >> t;
while(t--)
{
int n;
cin >> n;
v.clear();
for(int i=1;i<=n;i++)
{
int x;
cin >> x;
if(x == 1)
v.push_back(i);
}
if(v.size() == 0)
{
cout << 0 << endl;
continue;
}
if(v.size() == 1)
{
cout << -1 << endl;
continue;
}
int ans = 1e9;
ans = min(ans, solve());
v1.clear();
v1.push_back(1);
for(int i:v)
v1.push_back(n-v.back()+1+i);
v1.pop_back();
v = v1;
ans = min(ans, solve());
v1.clear();
v1.push_back(1);
for(int i:v)
v1.push_back(n-v.back()+1+i);
v1.pop_back();
v = v1;
ans = min(ans, solve());
cout << ans << endl;
}
}
Tester's Solution
#include <bits/stdc++.h>
#define endl '\n'
#define SZ(x) ((int)x.size())
#define ALL(V) V.begin(), V.end()
#define L_B lower_bound
#define U_B upper_bound
#define pb push_back
using namespace std;
template<class T, class T1> int chkmin(T &x, const T1 &y) { return x > y ? x = y, 1 : 0; }
template<class T, class T1> int chkmax(T &x, const T1 &y) { return x < y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);
int n;
int a[MAXN];
void read() {
cin >> n;
for(int i = 0; i < n; i++) {
cin >> a[i];
}
}
const int OFFSET = 3;
int dp[MAXN][2 * OFFSET + 2];
int myabs(int x) { return x > 0 ? x : -x; }
int rec(int pos, int bal) {
if(pos == n) {
return bal == 0 ? 0 : (int)1e9;
}
int &memo = dp[pos][bal + OFFSET];
if(memo != -1) return memo;
// place 0 here
memo = (int)1e9;
if(-OFFSET <= bal + a[pos] && bal + a[pos] <= OFFSET) {
chkmin(memo, myabs(bal + a[pos]) + rec(pos + 1, bal + a[pos]));
}
for(int place_here = 2; place_here <= 3; place_here++) {
int need = place_here - a[pos];
int new_bal = bal - need;
if(new_bal >= -OFFSET && new_bal <= OFFSET) {
chkmin(memo, myabs(new_bal) + rec(pos + 1, new_bal));
}
}
return memo;
}
void solve() {
int cnt = 0;
for(int i = 0; i < n; i++) cnt += a[i];
if(cnt == 1) cout << -1 << endl;
else if(cnt == 0) cout << 0 << endl;
else {
int ans = (int)1e9;
for(int cnt_rotations = 0; cnt_rotations <= 3; cnt_rotations++) {
int _cnt = a[0], second_one_pos = 0;
while(_cnt <= 1) _cnt += a[++second_one_pos];
// Set second one as first element
rotate(a, a + second_one_pos, a + n);
for(int i = 0; i <= n; i++) {
for(int bal = 0; bal < 2 * OFFSET + 1; bal++) {
dp[i][bal] = -1;
}
}
chkmin(ans, rec(0, 0));
}
cout << ans << endl;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
cin >> T;
while(T--) {
read();
solve();
}
return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class CHEFZRON{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int N = ni();
ArrayList<Integer> pos = new ArrayList<>();
for(int i = 0; i< N; i++)if(ni() == 1)pos.add(i);
if(pos.isEmpty())pn(0);
else if(pos.size() == 1)pn(-1);
else{
int ans = N;
for(int IT = 0; IT < 3; IT++){
//Solve for current shift
ans = Math.min(ans, solveNonCyclic(pos));
//Moving one 1 from start to end
pos.add(pos.remove(0)+N);
}
pn(ans);
}
}
int solveNonCyclic(ArrayList<Integer> pos){
int N = pos.size(), INF = (int)1e6;
int[] DP = new int[1+N];
DP[1] = INF;
for(int i = 2; i<= N; i++){
DP[i] = pos.get(i-1)-pos.get(i-2)+DP[i-2];
if(i >= 3)DP[i] = Math.min(DP[i], pos.get(i-1)-pos.get(i-3)+DP[i-3]);
}
return DP[N];
}
//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 CHEFZRON().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. 
