PROBLEM LINK:
Setter: Raj Khandor
Tester: Michael Nematollahi
Editorialist: Taranpreet Singh
DIFFICULTY:
PREREQUISITES:
Observation, Bitwise operations.
PROBLEM:
You are given the initial state in form of a triplet (a, b, c) and a final state triplet (x, y, z), we need to determine the minimum cost to achieve this transformation, if we are allowed the following operation.
- Choose one element of triplet (a, b, c) and either add or subtract 1 from that element. Cost of this operation is 1 unit.
- Merge operation, which transforms triplet (a, b, c) to either one from (a-1, b-1, c+1), (a-1, b+1, c-1) or (a+1, b-1, c-1). Cost of this operation is zero.
- The split operation, which transforms triplet (a, b, c) to either one from (a-1, b+1, c+1), (a+1, b+1, c-1) or (a+1, b-1, c+1). Cost of this operation is zero.
Additionally, at all time during this process, all elements of this tuple shall be non-negative.
EXPLANATION
An important fact to notice is that Split operation can only be applied when there’s at least one element > 0, and Merge operation can be applied when there are at least two elements > 0.
Let us consider special cases first.
- If the Initial triplet is the same as the final triplet already, the answer is zero.
- If the initial triplet is (0,0,0) we can apply neither split nor merge operation, since applying operation shall lead to at least one negative value, which is not allowed. So, we need to incur 1 unit cost increasing exactly one element from the triplet, and then apply the general idea explained below.
- If the final triplet is (0,0,0), then even after applying a series of split and merge operations, we cannot reach the triplet (0, 0, 0) so here too, we are required to decrease at least one element by 1 after reaching triplet containing exactly one occurrence of 1 and rest elements being 0. So we can get the total cost as the cost to reach a triplet with exactly one occurrence of 1 and rest elements being zero, and add one to it.
The General Case
Now, we can safely assume we can apply split and merge operations. If the start tuple is (a, b, c), we can apply split operation resulting in (a+1, b-1, c+1). Again applying split operation, we can reach (a+2, b, c). So we have managed to increase individual element by 2 without incurring any cost. The only requirement for this is b > 0 which is satisfied here.
Also, we can similarly apply merge operations to reduce any value by 2.
Secondly, consider the sequence of operation applying split operation thrice. We can increase all elements by 1 at no cost. Similarly, applying merge operation thrice allows us to reduce all elements by 1 at no cost.
Above observations may lead to a nice solution if carefully written, but there is a better solution using bitwise operations.
Since we can increase or decrease each element by 2 at no cost, only the parities of elements matter (in the general case only). For example, triplet (5, 3, 4) can be seen as (1,1,0), triplet (6,4,8) can be seen as (0,0,0). Let us consider triplet (5,3,4) as mask 110 and triplet (6,4,8) as mask 000 for ease. (mask 000 is not forbidden, now, since we are considering parities and not actual numbers.)
Try applying each merge and split operation one by one and we can see that each operation only flips the whole masks. After one operation, mask 000 turns into 111, mask 001 turns into 110, and so on.
Adding or subtracting one to an element is the same as flipping a specific bit of mask.
So, we get a reduced problem. We are given an initial mask A of 3 bits and final mask B, we are allowed to flip the whole mask at zero cost, or flip any individual bit of initial mask at cost 1.
It is easy to see now that we can either choose to flip or not to flip the initial mask, and make masks equal by flipping individual bits. The minimum number of operations of cost 1 needed to reach from mask X and mask Y is the number of set bits in X \oplus Y. So, we can consider Y = B and X = A, and Y = B and X = A \oplus 111, find the minimum number of operations required in each case and take the minimum.
We have solved the problem with this.
About the special cases, since we can increase (or decrease) any element, we can try all three possibilities and take the minimum cost out of those and add 1 to cost.
Refer implementations if anything still not clear.
TIME COMPLEXITY
The time complexity is O(1) per test case.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
/**
Some observations:
* (a,b,c) can be converted to (a-1,b-1,c-1) with 0 cost.(and vice versa provided initial state is not (0,0,0))
* Applying Merge and Split operations flips the parity of all the 3 numbers. That is to say that (Even,Even,Even) becomes (Odd,Odd,Odd)
* A given pair of numbers (a,b,c) can be converted to (x,y,z) in 0 cost provided their parity is same or negated.
Else you will have to add or subtract.
* State (x,y,z) = (0,0,0) is unachievable.
**/
bool same_parity(ll a, ll b, ll c, ll x, ll y, ll z)
{
/**
* Convention in comments of this and the following function
* abc is the bits a%2 b%2 c%2 concatenated together
* And similarly for xyz
**/
/// Check if abc is equivalent to xyz or ~xyz
ll n,m;
n = a%2;
n = (n<<1) + b%2;
n = (n<<1) + c%2;
m = x%2;
m = (m<<1) + y%2;
m = (m<<1) + z%2;
ll m_neg = (~m)&7;
if((n^m) == 0 || (n^m_neg) == 0)
return true;
return false;
}
ll xor_func(ll a, ll b, ll c, ll x, ll y, ll z)
{
/// Return the minimum of set bits in abc^xyz and abc^(~xyz)
ll n,m;
n = a%2;
n = (n<<1) + b%2;
n = (n<<1) + c%2;
m = x%2;
m = (m<<1) + y%2;
m = (m<<1) + z%2;
ll m_neg = (~m)&7;
return min(__builtin_popcount(n^m), __builtin_popcount(n^m_neg));
}
int main()
{
ll t,a,b,c,x,y,z;
//fstream cin("4.in");
//fstream cout("4.out",fstream::in|fstream::out|fstream::trunc);
cin>>t;
while(t--)
{
cin>>a>>b>>c>>x>>y>>z;
ll ans;
if(a == x && b == y && c == z)
ans = 0;
else if((a == 0 && b == 0 && c == 0) || (x == 0 && y == 0 && z == 0))
{
/**
* State (0,0,0) is unachievable in any case
* If abc and xyz have same parity then you have to add/subtract 2
* else you can always reach by adding/subtracting 1
**/
if(same_parity(a,b,c,x,y,z))
ans = 2;
else
ans = 1;
}
else
ans = xor_func(a,b,c,x,y,z);
assert(ans >= 0 && ans <= 2);
cout<<ans<<"\n";
}
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define F first
#define S second
ll a[2][3];
int solve2(){
int mask = 0;
for (int i = 0; i < 3; i++)
mask |= 1<<(a[0][i] - a[1][i] & 1);
return mask==3;
}
int solve1(){
if (max({a[1][0], a[1][1], a[1][2]}) == 0){
int ret = 100;
for (int i = 0; i < 3; i++){
a[1][i]++;
ret = min(ret, solve2()+1);
a[1][i]--;
}
return ret;
}
return solve2();
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int te; cin >> te;
while (te--){
for (int w = 0; w < 2; w++)
for (int i = 0; i < 3; i++)
cin >> a[w][i];
bool same = true;
for (int i = 0; i < 3; i++)
same &= a[0][i] == a[1][i];
if (same)
cout << "0\n";
else {
int ans = 100;
if (max({a[0][0], a[0][1], a[0][2]}) == 0) {
for (int i = 0; i < 3; i++){
a[0][i]++;
ans = min(ans, solve1() + 1);
a[0][i]--;
}
}
else{
ans = min(ans, solve1());
}
cout << ans << "\n";
}
}
return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class FUZZYCON{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
long a = nl(), b = nl(), c = nl(), x = nl(), y = nl(), z = nl();
if(a == x && b == y && c == z)pn(0);
else if(a+b+c == 0)pn(1+Math.min(ans(0, 1, 0, x, y, z), Math.min(ans(1,0,0,x,y,z), ans(0, 0, 1, x, y, z))));
else if(x+y+z == 0)pn(1+Math.min(ans(0, 1, 0, a, b, c), Math.min(ans(1,0,0,a,b,c), ans(0, 0, 1, a, b, c))));
else pn(ans(a, b, c, x, y, z));
}
int ans(long a, long b, long c, long x, long y, long z){
int A = mask(a, b, c);
int X = mask(x, y, z);
return Math.min(bit(A^X), bit(A^flip(X)));
}
int mask(long a, long b, long c){
int mask = 0;
if(a%2 == 1)mask |= 4;
if(b%2 == 1)mask |= 2;
if(c%2 == 1)mask |= 1;
return mask;
}
int flip(int mask){return 7&(~mask);}
//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 FUZZYCON().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, if you want to. (even if its same 
) . Suggestions are welcomed as always had been. 