Queries to check if it is possible to join boxes in a circle
Consider n boxes numbered arranged in a circle in increasing order in clockwise direction (numbered from 1 to n). You are given q queries, each containing two integer i and j. The task is to check whether it is possible to connect box i to box j by a rod without intersecting rods used to join other boxes in previous queries. Also, every box can be connected to at most one other box and no box can be connected to itself.
Examples:
Input: n = 10, q = 7
q1 = (1, 5)
q2 = (2, 7)
q3 = (2, 3)
q4 = (2, 4)
q5 = (9, 9)
q6 = (10, 9)
q7 = (8, 6)
Output:
YES
NO
YES
NO
NO
YES
YES
Box 1 and v 5 can be connected by a rod.
Box 2 and Box 7 cannot be connected by a rod because this rod intersects with the rod connecting Box 1 and Box 5.
Box 2 and Box 3 can be connected without criss-cross.
Box 2 and Box 4 cannot be connected as Box 2 is already connected to Box 3.
Box 9 and Box 9 cannot be connected as no box can be connected to itself.
Box 10 and Box 9 can be connected.
Box 8 and Box 6 can be connected.
Approach:
Suppose box x is already connected to box y. And we need to connect box i to box j.
Now, observe there can be two cases where two rods connecting box i and box j will intersect with rod connecting box x and box y.
Case 1: x < i and y lies between i and j:
Case 2: x lies between i and j and y >j:
We will explicitly check the case of whether a rod is intends to connect to itself or if the rod intends to connect two boxes such that at least one of them is already connected.
Hence, we will check the above two condition. If any of two meet, it is not possible to connect else we can connect the boxes.
Below is the implementation of the above approach:
C++
// C++ implementation of above approach #include <bits/stdc++.h> using namespace std; #define MAX 50 // Print the answer to each query void solveQuery( int n, int q, int qi[], int qj[]) { int arr[MAX]; for ( int i = 0; i <= n; i++) arr[i] = 0; for ( int k = 0; k < q; k++) { // setting the flag for exception int flag = 0; // replacing the greater element in i and j if (qj[k] < qi[k]) { int temp = qi[k]; qi[k] = qj[k]; qj[k] = temp; } // checking if that box is not // used in previous query. if (arr[qi[k]] != 0 || arr[qj[k]] != 0) flag = 1; // checking if connecting to the same box else if (qi[k] == qj[k]) flag = 1; else { // case 1: x < i and y lies between i and j for ( int i = 1; i < qi[k]; i++) { if (arr[i] != 0 && arr[i] < qj[k] && qi[k] < arr[i]) { flag = 1; break ; } } // case 2: x lies between i and j and y >j if (flag == 0) { for ( int i = qi[k] + 1; i < qj[k]; i++) { if (arr[i] != 0 && arr[i] > qj[k]) { flag = 1; break ; } } } } // if flag is not reset inbetween. if (flag == 0) { cout << "YES\n" ; arr[qi[k]] = qj[k]; arr[qj[k]] = qi[k]; } else cout << "NO\n" ; } } // Driver code int main() { int n = 10; int q = 7; int qi[] = { 1, 2, 2, 2, 9, 10, 8 }; int qj[] = { 5, 7, 3, 4, 9, 9, 6 }; solveQuery(n, q, qi, qj); return 0; } |
Java
// Java implementation of // above approach class GFG { static int MAX = 50 ; // Print the answer to each query static void solveQuery( int n, int q, int qi[], int qj[]) { int [] arr = new int [MAX]; for ( int i = 0 ; i <= n; i++) arr[i] = 0 ; for ( int k = 0 ; k < q; k++) { // setting the flag for exception int flag = 0 ; // replacing the greater // element in i and j if (qj[k] < qi[k]) { int temp = qi[k]; qi[k] = qj[k]; qj[k] = temp; } // checking if that box is not // used in previous query. if (arr[qi[k]] != 0 || arr[qj[k]] != 0 ) flag = 1 ; // checking if connecting // to the same box else if (qi[k] == qj[k]) flag = 1 ; else { // case 1: x < i and y lies // between i and j for ( int i = 1 ; i < qi[k]; i++) { if (arr[i] != 0 && arr[i] < qj[k] && qi[k] < arr[i]) { flag = 1 ; break ; } } // case 2: x lies between // i and j and y >j if (flag == 0 ) { for ( int i = qi[k] + 1 ; i < qj[k]; i++) { if (arr[i] != 0 && arr[i] > qj[k]) { flag = 1 ; break ; } } } } // if flag is not reset inbetween. if (flag == 0 ) { System.out.println( "YES" ); arr[qi[k]] = qj[k]; arr[qj[k]] = qi[k]; } else System.out.println( "NO" ); } } // Driver code public static void main(String[] args) { int n = 10 ; int q = 7 ; int qi[] = { 1 , 2 , 2 , 2 , 9 , 10 , 8 }; int qj[] = { 5 , 7 , 3 , 4 , 9 , 9 , 6 }; solveQuery(n, q, qi, qj); } } // This code is contributed // by ChitraNayal |
Python 3
# Python 3 implementation of # above approach MAX = 50 # Print the answer to each query def solveQuery(n, q, qi, qj): arr = [ None ] * MAX for i in range (n + 1 ): arr[i] = 0 for k in range (q): # setting the flag # for exception flag = 0 # replacing the greater # element in i and j if (qj[k] < qi[k]): qj[k], qi[k] = qi[k], qj[k] # checking if that box is not # used in previous query. if (arr[qi[k]] ! = 0 or arr[qj[k]] ! = 0 ): flag = 1 # checking if connecting # to the same box elif (qi[k] = = qj[k]): flag = 1 else : # case 1: x < i and y # lies between i and j for i in range ( 1 , qi[k]) : if (arr[i] ! = 0 and arr[i] < qj[k] and qi[k] < arr[i]): flag = 1 break # case 2: x lies between # i and j and y >j if (flag = = 0 ): for i in range (qi[k] + 1 , qj[k]) : if (arr[i] ! = 0 and arr[i] > qj[k]): flag = 1 break # if flag is not reset inbetween. if (flag = = 0 ): print ( "YES" ) arr[qi[k]] = qj[k] arr[qj[k]] = qi[k] else : print ( "NO" ) # Driver code if __name__ = = "__main__" : n = 10 q = 7 qi = [ 1 , 2 , 2 , 2 , 9 , 10 , 8 ] qj = [ 5 , 7 , 3 , 4 , 9 , 9 , 6 ] solveQuery(n, q, qi, qj) # This code is contributed # by ChitraNayal |
C#
// C# implementation of // above approach using System; class GFG { static int MAX = 50; // Print the answer to each query static void solveQuery( int n, int q, int [] qi, int [] qj) { int [] arr = new int [MAX]; for ( int i = 0; i <= n; i++) arr[i] = 0; for ( int k = 0; k < q; k++) { // setting the flag for exception int flag = 0; // replacing the greater // element in i and j if (qj[k] < qi[k]) { int temp = qi[k]; qi[k] = qj[k]; qj[k] = temp; } // checking if that box is not // used in previous query. if (arr[qi[k]] != 0 || arr[qj[k]] != 0) flag = 1; // checking if connecting // to the same box else if (qi[k] == qj[k]) flag = 1; else { // case 1: x < i and y lies // between i and j for ( int i = 1; i < qi[k]; i++) { if (arr[i] != 0 && arr[i] < qj[k] && qi[k] < arr[i]) { flag = 1; break ; } } // case 2: x lies between // i and j and y >j if (flag == 0) { for ( int i = qi[k] + 1; i < qj[k]; i++) { if (arr[i] != 0 && arr[i] > qj[k]) { flag = 1; break ; } } } } // if flag is not reset inbetween. if (flag == 0) { Console.Write( "YES\n" ); arr[qi[k]] = qj[k]; arr[qj[k]] = qi[k]; } else Console.Write( "NO\n" ); } } // Driver code public static void Main() { int n = 10; int q = 7; int [] qi = { 1, 2, 2, 2, 9, 10, 8 }; int [] qj = { 5, 7, 3, 4, 9, 9, 6 }; solveQuery(n, q, qi, qj); } } // This code is contributed // by ChitraNayal |
PHP
<?php // PHP implementation of // above approach $MAX = 50; // Print the answer to each query function solveQuery( $n , $q , & $qi , & $qj ) { global $MAX ; $arr = array_fill (0, $MAX , NULL); for ( $i = 0; $i <= $n ; $i ++) $arr [ $i ] = 0; for ( $k = 0; $k < $q ; $k ++) { // setting the flag // for exception $flag = 0; // replacing the greater // element in i and j if ( $qj [ $k ] < $qi [ $k ]) { $temp = $qi [ $k ]; $qi [ $k ] = $qj [ $k ]; $qj [ $k ] = $temp ; } // checking if that box is not // used in previous query. if ( $arr [ $qi [ $k ]] != 0 || $arr [ $qj [ $k ]] != 0) $flag = 1; // checking if connecting // to the same box else if ( $qi [ $k ] == $qj [ $k ]) $flag = 1; else { // case 1: x < i and y lies // between i and j for ( $i = 1; $i < $qi [ $k ]; $i ++) { if ( $arr [ $i ] != 0 && $arr [ $i ] < $qj [ $k ] && $qi [ $k ] < $arr [ $i ]) { $flag = 1; break ; } } // case 2: x lies between // i and j and y >j if ( $flag == 0) { for ( $i = $qi [ $k ] + 1; $i < $qj [ $k ]; $i ++) { if ( $arr [ $i ] != 0 && $arr [ $i ] > $qj [ $k ]) { $flag = 1; break ; } } } } // if flag is not reset inbetween. if ( $flag == 0) { echo "YES\n" ; $arr [ $qi [ $k ]] = $qj [ $k ]; $arr [ $qj [ $k ]] = $qi [ $k ]; } else echo "NO\n" ; } } // Driver code $n = 10; $q = 7; $qi = array ( 1, 2, 2, 2, 9, 10, 8 ); $qj = array ( 5, 7, 3, 4, 9, 9, 6 ); solveQuery( $n , $q , $qi , $qj ); // This code is contributed // by ChitraNayal ?> |
Javascript
<script> // Javascript implementation of above approach var MAX = 50 // Print the answer to each query function solveQuery(n, q, qi, qj) { var arr = Array(MAX); for ( var i = 0; i <= n; i++) arr[i] = 0; for ( var k = 0; k < q; k++) { // setting the flag for exception var flag = 0; // replacing the greater element in i and j if (qj[k] < qi[k]) { var temp = qi[k]; qi[k] = qj[k]; qj[k] = temp; } // checking if that box is not // used in previous query. if (arr[qi[k]] != 0 || arr[qj[k]] != 0) flag = 1; // checking if connecting to the same box else if (qi[k] == qj[k]) flag = 1; else { // case 1: x < i and y lies between i and j for ( var i = 1; i < qi[k]; i++) { if (arr[i] != 0 && arr[i] < qj[k] && qi[k] < arr[i]) { flag = 1; break ; } } // case 2: x lies between i and j and y >j if (flag == 0) { for ( var i = qi[k] + 1; i < qj[k]; i++) { if (arr[i] != 0 && arr[i] > qj[k]) { flag = 1; break ; } } } } // if flag is not reset inbetween. if (flag == 0) { document.write( "YES<br>" ); arr[qi[k]] = qj[k]; arr[qj[k]] = qi[k]; } else document.write( "NO<br>" ); } } // Driver code var n = 10; var q = 7; var qi = [1, 2, 2, 2, 9, 10, 8 ]; var qj = [5, 7, 3, 4, 9, 9, 6 ]; solveQuery(n, q, qi, qj); </script> |
YES NO YES NO NO YES YES
Time Complexity: O(q*val) where val is the maximum element in the query array.
Auxiliary Space: O(MAX)