CHEFZRON - Editorial

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. :slight_smile:

18 Likes

Can anyone share their code which doesn’t uses DP, (i am new)

if you are new, this problem is probably not suitable for you!
Solve some easier problems first and gradually increase the difficulty level of problems.

11 Likes

@rishup_nitdgp. I am a beginner so I am having difficulty understanding some things in your code.
In setters solution
ans = min(ans, solve());
has been used thrice. Why ?
And

dp[0] = 0;
dp[1] = 1e9;
dp[2] = v[1] - v[0];

What is the reason for setting the values above. What does it mean ?

Can Anyone Explain to me why the Setter’s logic in DP at index 1 is having 1e9 .??

if u have 0 number of 1’s the answer is 0
if u have 1 number of 1’s it is impossible to satisfy the condition hence 1e9/INF
if u have exactly 2 1’s then the answer is the difference between the positions as mentioned in the editorial

1 Like

Why do we to rotate till exactly 1 one comes from the start to the end? i thought one left shift will do…

okay got it

1 Like

Since you are new, i would recommend that you solve beginner and easy level practice problems first. Also, during competitions, first try the questions with maximum number of successful submissions and/or accuracy. As far as i remember, there were no more than 4 succesful submissions for CHEFZRON problem even after an hour or two :cry: :flushed:
(try solving the problems with lower difficulty levels first (like LUNCHTIME’S LOSTWKND, WWALK, TREEDIFF,CONVSTR,etc.)

1 Like

Great explanation!!!

1 Like

explain me plz…i didn’t undertand cyclic=3*acyclic with shifts

1 Like

The max value the array can contain is 3

Great editorial! Step by step process was very helpful, thanks

revisiting this problem, i have a doubt with how to deal with shifts…why are we shifting thrice until one 1 goes from left to right