CRYCOLR - Editorial

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;
}
5 Likes

please provide me a case where this code fails
#include <bits/stdc++.h>
using namespace std;

int main() {
// your code goes here
int t;
cin>>t;
while(t–){
int n;
cin>>n;
int b1[3],b2[3],b3[3],sum=0;
cin>>b1[0]>>b1[1]>>b1[2];
cin>>b2[0]>>b2[1]>>b2[2];
cin>>b3[0]>>b3[1]>>b3[2];
sum=sum+(n-b1[0]);
sum=sum+(n-b2[1]);
sum=sum+(n-b3[2]);
if(sum%2==0){
cout<<sum/2;
}
else{
cout<<(sum/2)+1;
}
cout<<"\n";
}
return 0;
}

1 Like
2
0 0 2
2 0 0
0 2 0

Try this test case.

4 Likes

Awesome logic explained in the above Editorial.
Here is my approach towards the problem.
** QUICK EXPLANATION:**

  • At first, we can select any one box out of the 3 boxes available, and then perform all the moves required to make that box fill with only the ball it wants.(required condition of that box)

  • And then we will be left with 2 boxes, and now it is very easy to determine the left over moves .

** EXPLANATION:**
If you analyse any test case ,then it can be seen clearly. Before reaching to the required condition( n 0 0 ) , the required condition of one box is
0 n 0
0 0 n
acheived( either (n 0 0) or (0 n 0) or (0 0 n) ).And then the left 2 boxes exchanges balls to have the suitable balls.
To see this thing clearly , let us take some examples
0 1 0 1 0 0 1 0 0
0 0 1 —> 0 0 1 —> 0 1 0
1 0 0 0 1 0 0 0 1
it can be seen clearly, that before reaching to the required condition, 1st box has its requires balls. Now , we can state this fact that , at first we are trying to make any one of the box has its suitable balls.(because which ever test case you take , this is gonna to happen).

so why not we take use of that. We will select any box and then calculate the requires no. of moves to make it fill with the suitable balls. and then calculate the remaining moves ,so that the other 2 boxes also have their requires balls.

suppose we have selected the first box then the answer will be
input: a1 a2 a3
b1 b2 b3
c1 c2 c3
output: (n-a1) + (n-(b2+min(b1,a2)))

Try to find the logic of this general formula :slight_smile: yourself.
Similarly when we will select 2nd and the 3rd box, a general answer can be calculated.

Atlast here is my solution: Solution: 56489272 | CodeChef

If any doubts, please ask I will be happy to see them:)

5 Likes

not understand the output logic

1 Like

Here’s a very simple approach.
For the input :
r1 g1 b1
r2 g2 b2
r3 g3 b3

We know r1 ,g2 and b3 are in their appropriate boxes so we focus on the rest.
As we can see , g1 , b1 and b2 forms an upper traingle and r2 ,r3 and g3 forms a lower triangle and all of these must be swapped.

While swapping , we won’t always be getting numbers that cancel out each other so we would require atleast the maximum out of the sum of each triangles.

The code would look like:

max(g1 + b1 + b2 ,r2 + r3 + g3)

Here’s my solution: Solution: 56526380 | Codechef

7 Likes

Thanks a lot. This really helped !!!

2 Likes

really the simplest approach to solve the question :fire:

1 Like

Leave this approach and see the below one. It is very easy to understand.

https://www.codechef.com/viewsolution/56434287
No need for this much calculation and the whole problem can be solved by just one formula.

im getting TLE. is there any flaw in the logic?
int main()
{
int t;
cin >> t;

while (t--)

{
    int N, color [4][4], count=0;
    cin >> N;        
    color[0][0] = color[0][1] = color[0][2] = color[0][3] = 0;
    color[1][0] = color[2][0] = color[3][0] = 0;
    for (size_t i = 1; i <= 3; i++)
    {
        for (size_t j = 1; j <= 3; j++)
        {
            cin >> color[i][j];
        }
    }
    /*
    0,0  0,1   0,2   0,3
    1,0  1,1   1,2   1,3
    2,0  2,1   2,2   2,3
    3,0  3,1   3,2   3,3
    */

    while(color[1][1] !=N || color[2][2] != N || color[3][3] != N)
    {
        if (color[1][2]>0 && (color[2][1]>0))
        {
            color[1][2]--;color[2][2]++;                
            color[2][1]--;color[1][1]++;
            count++;
        }
        if (color[1][3]>0 && color[3][1]>0)
        {
            color[1][3]--;color[3][3]++;                
            color[3][1]--;color[1][1]++;
            count++;
        }

        if (color[1][2]>0 && color[2][3]>0)
        {
            color[1][2]--;color[2][2]++;
            color[2][3]--;color[1][3]++;                
            color[1][3]--;color[3][3]++;
            color[3][1]--;color[1][1]++;
            count++;count++;
        }

        if (color[2][3]>0 && color[3][2]>0)
        {
            color[3][2]--;color[2][2]++;
            color[2][3]--;color[3][3]++;
            count++;
        }

        if (color[2][1]>0 && color[3][2]>0)
        {
            color[2][1]--;color[3][1]++;
            color[3][2]--;color[2][2]++;
            color[1][3]--;color[3][3]++;
            color[3][1]--;color[1][1]++;
            count++;count++;
        }        
    }
    cout << count << endl;
}
return 0}

how do you come up with this formula? btw nice solution

how the max value among two triangles is solving the solution? can you please explain. i lost you after the two triangles were formed.

Thanks!!

Consider this example:
1 3 3 ( r1 g1 b1)
4 2 1 ( r2 g2 b2)
2 2 3 ( r3 g3 b3)

Sum of the upper triangle = 7
Sum of the lower triangle = 8

Let x=0 be our variable in which we store our answer.
Lets swap, swap(g1,r2), swap(b1,r3) and swap(b2,g3)
Now x will become x = min(g1,r1) + min(b1,r3) + min(b2,g3)
x = 3 + 2 + 1 = 6
After the swaps we’ll be left with the following:
1 0 1
1 2 0
0 1 3

As you can see no more efficient swapping can be done and we’ll need atleast 2 more swaps (the sum of the lower triangle) in order to place all the balls in their respective boxes.
So adding +2 to our final answer makes, x = x + 2 = 6 + 2 = 8.
Ans as you can see 8 comes out to be the sum of the balls in the lower triangle.

Hope you got it :blush:

1 Like

Here was my solution which passed all test all cases in c.

#include <stdio.h>

int main()
{
int t;
scanf("%d", &t);

while (t--)
{
    int n;
    scanf("%d", &n);
    int b1[3], b2[3], b3[3];

    for (int i = 1; i <= 3; i++)
    {
        scanf("%d", &b1[i]);
    }

    for (int i = 1; i <= 3; i++)
    {
        scanf("%d", &b2[i]);
    }

    for (int i = 1; i <= 3; i++)
    {
        scanf("%d", &b3[i]);
    }

    int c = 0;

    while (b1[2] != 0)
    {
        if (b2[1] == 0)
        {
            b1[2]--;
            b3[1]--;
            b1[1]++;
            b3[2]++;
            c++;
        }

        else
        {
            b1[2]--;
            b2[1]--;
            b1[1]++;
            b2[2]++;
            c++;
        }
    }

    while (b1[3] != 0)
    {
        if (b3[1] == 0)
        {
            b1[3]--;
            b2[1]--;
            b1[1]++;
            b2[3]++;
            c++;
        }

        else
        {
            b1[3]--;
            b3[1]--;
            b1[1]++;
            b3[3]++;
            c++;
        }
    }

    while(b2[3]!=0)
    {
        b2[3]--;
        b3[3]++;
        b2[2]++;
        b3[2]--;
        c++;
    }

    printf("%d\n", c);
}

return 0;

}

oh thanks buddy :slight_smile: you really explain the problem to the core. :ok_hand:

1 Like

Here’s My approach for solving this problem.

As we know we have to find the minimum swaps required.

Box 1—>R[0] G[0] B[0]
Box 2—>R[1] G[1] B[1]
Box 3—>R[2] G[2] B[2]

#include <iostream.h>
using namespace std;

int main(){
int T,i,N,ans,big;
cin>>T;
while(T–){
cin>>N;
short int R[3],G[3],B[3];
for(i=0;i<3;i++){
cin>>R[i]>>G[i]>>B[i];
}
if(G[2]>B[1]){
big=G[2];
}
else{
big=B[1];
}
ans=R[1]+R[2]+big;
cout<<ans<<endl;

}

return 0;
}