PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Setter: S.Manuj Nanthan
Tester: Taranpreet Singh
Editorialist: Kanhaiya Mohan
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
There are 3 \cdot N balls of colours \texttt{Red,Green} and \texttt{Blue}. There are exactly N balls of each colour. These 3 \cdot N balls are divided into 3 boxes, such that each box has exactly N balls.
We have to make a series of operations, such that, at the end, 1^{st} box contains all the \texttt{Red} balls, 2^{nd} box contains all the \texttt{Green} balls and, 3^{rd} box contains all the \texttt{Blue} balls (in the given order).
One move is defined as: Pick any two boxes, pick 1 ball each from the boxes and swap them.
Find the minimum number of moves required to satisfy the conditions.
QUICK EXPLANATION:
- Start with moves which place 2 balls into their suitable boxes in a single move.
- Still, if there exists a ball which is not in its suitable box, there would be at least 2 more balls of different colours with the same condition. These 3 balls of different colours can be placed into their suitable boxes using exactly 2 moves.
EXPLANATION:
Try this test case
1
1
0 0 1
1 0 0
0 1 0
The correct answer for this test case is 2.
For simplicity, let us colour the boxes to \texttt{Red,Green} and \texttt{Blue} as well. From now on, the suitable place for a \texttt{Red} ball is a \texttt{Red} box and so on.
We start with N balls in each box. In one move, we swap one ball each from two boxes. Thus, we always maintain N number of balls in each box. This gives an intuition that the mismatches are present in such a way that there is always a possible sequence of moves to sort the balls into suitable boxes. We never move a ball which is already present in its suitable box.
Let us understand the moves using an example. Consider a \texttt{Red} ball which is currently placed in a \texttt{Blue} box. There can be two cases:
- \texttt{Red} box has at least 1 \texttt{Blue} ball: In this case, we can simply swap these two balls and place both of them in their suitable boxes in a single move.
-
\texttt{Red} box has at no \texttt{Blue} ball: This means that \texttt{Red} box has at least 1 \texttt{Green} ball. Now since \texttt{Blue} box has a \texttt{Red} ball and \texttt{Red} box has a \texttt{Green} ball, there must be a \texttt{Blue} ball in the \texttt{Green} box. Now, these three mismatches can be corrected using 2 moves.
Move 1 is swap \texttt{Red} ball from \texttt{Blue} box and \texttt{Blue} ball from \texttt{Green} box. Now, the \texttt{Blue} ball is placed suitably. Move 2 is swap \texttt{Red} ball from \texttt{Green} box and \texttt{Green} ball from \texttt{Red} box. Thus, all balls are in their suitable boxes.
All other possible cases are symmetric to the example explained above.
To sum up, we start with moves which place 2 balls into their suitable boxes in a single move. Then, all the balls which are still misplaced can be clubbed into group of 3. For each group, we need exactly 2 moves.
TIME COMPLEXITY:
The time complexity is O(1) per test case.
SOLUTION:
Setter's Solution
#from itertools import *
#from math import *
#from bisect import *
#from collections import *
#from random import * # ( : ): ( :) : (: ) : ( ): ) : )
#from decimal import *
#from heapq import *
from itertools import * # Things Change ....remember :)
import sys
input=sys.stdin.readline
def inp():
return int(input())
def st():
return input().rstrip('\n')
def lis():
return list(map(int,input().split()))
def ma():
return map(int,input().split())
t=inp()
while(t):
t-=1
n=inp()
r=[]
for i in range(3):
r.append(lis())
swaps=0
red_green=min(r[0][1],r[1][0])
green_blue=min(r[1][2],r[2][1])
red_blue=min(r[2][0],r[0][2])
swaps+=red_green+green_blue+red_blue
r[0][0]+=red_green
r[0][1]-=red_green
r[1][0]-=red_green
r[1][1]+=red_green #case1
r[1][2]-=green_blue
r[1][1]+=green_blue
r[2][1]-=green_blue
r[2][2]+=green_blue #case 2
r[2][0]-=red_blue
r[2][2]+=red_blue
r[0][2]-=red_blue
r[0][0]+=red_blue #case 3
swaps+=2*(n-r[0][0])
print(swaps)
Tester's Solution
import java.util.*;
import java.io.*;
class CRYCOLR{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
//should get WA
int N = ni();
int[][] box = new int[3][3];
for(int i = 0; i< 3; i++)
for(int j = 0; j< 3; j++)
box[i][j] = ni();
hold(box[0][0]+box[0][1]+box[0][2] == N);
hold(box[1][0]+box[1][1]+box[1][2] == N);
hold(box[2][0]+box[2][1]+box[2][2] == N);
hold(box[0][0]+box[1][0]+box[2][0] == N);
hold(box[0][1]+box[1][1]+box[2][1] == N);
hold(box[0][2]+box[1][2]+box[2][2] == N);
int ans = 0, x = 0;
x = Math.min(box[0][2], box[2][0]);
box[0][2] -= x;
box[2][0] -= x;
box[0][0] += x;
box[2][2] += x;
ans += x;
x = Math.min(box[2][0], box[1][2]);
box[2][0] -= x;
box[1][2] -= x;
box[2][2] += x;
box[1][0] += x;
ans += x;
x = Math.min(box[1][2], box[2][1]);
box[1][2] -= x;
box[2][1] -= x;
box[1][1] += x;
box[2][2] += x;
ans += x;
x = Math.min(box[2][1], box[0][2]);
box[2][2] += x;
box[0][2] -= x;
box[2][1] -= x;
box[0][1] += x;
ans += x;
ans += box[0][1];
pn(ans);
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
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 CRYCOLR().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;
}
}
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
#define sync {ios_base ::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}
#define rep(n) for(int i = 0;i<n;i++)
#define rep1(a,b) for(int i = a;i<b;i++)
#define int long long int
#define mod 1000000007
int n;
void solve()
{
cin>>n;
int a[3][3];
for(int i = 0; i<3; i++){
for(int j = 0; j<3; j++){
cin>>a[i][j];
}
}
int total_moves = 0;
int curr_moves = 0;
//Type-1 move
//Red-Blue
curr_moves = min(a[0][2], a[2][0]);
a[0][2] -= curr_moves;
a[2][0] -= curr_moves;
a[0][0] += curr_moves;
a[2][2] += curr_moves;
total_moves += curr_moves;
//Blue-Green
curr_moves = min(a[1][2], a[2][1]);
a[1][2] -= curr_moves;
a[2][1] -= curr_moves;
a[1][1] += curr_moves;
a[2][2] += curr_moves;
total_moves += curr_moves;
//Red-Green
curr_moves = min(a[0][1], a[1][0]);
a[0][1] -= curr_moves;
a[1][0] -= curr_moves;
a[0][0] += curr_moves;
a[1][1] += curr_moves;
total_moves += curr_moves;
//Type-2 moves
total_moves += 2*(a[0][1] + a[0][2]);
cout<<total_moves;
}
int32_t main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
sync;
int t = 1;
cin>>t;
while(t--){
solve();
cout<<"\n";
}
return 0;
}
yourself.
you really explain the problem to the core. 