Dadas dos arrays R[] y C[] que constan de N enteros tales que se puede formar una array de dimensiones N x N cuyo elemento en el índice (i, j) viene dado por (R[i] + C[j]) para todos los pares posibles de las dos arrays. Dada una array Consultas[][] en la que cada fila representa una consulta del tipo {A, B, X, Y} , la tarea de cada consulta es verificar si existe una ruta desde la celda (A, B) a ( X, Y) en la array que consta solo de números pares o no. Si es cierto, escriba » Sí» . De lo contrario, imprima “No” .
Nota: Para una ruta desde la celda actual (i, j), los únicos movimientos posibles son (i + 1, j) , (i, j + 1) , (i – 1, j) y (i, j – 1) .
Ejemplos:
Entrada: R[] = {6, 2, 7, 8, 3}, C[] = {3, 4, 8, 5, 1}, Consultas[][] = {{2 2 1 3}, {4 2 4 3}, {5 1 3 4}}
Salida: Si Si No
Explicación:
La array formada es:
{{9, 10, 14, 11, 7}
{5, 6, 10, 7, 3}
{10, 11, 15, 12, 8}
{11, 12, 16, 13, 9}
{6, 7, 11, 8, 4}}
Consulta1: Existe una ruta con número par desde la celda (2, 2) a la (1) , 3) con todas las celdas como número par. El camino es (2, 2) -> (2, 3) -> (1, 3).
Consulta 2: existe una ruta con número par desde la celda (4, 2) a (4, 3) con todas las celdas como número par. El camino es (4, 2) -> (4, 3).
Consulta 3: No existe ninguna ruta con todos los elementos parejos.Entrada: R[] = {1, 2, 4, 8, 5}, C[] = {2, 5, 9, 7, 6}, Consultas[][] = {{2 2 1 3}, {1 4 1 3}, {5 1 3 4}}
Salida: No Si No
Explicación:
La array formada es:
{{3, 6, 10, 8, 7}
{4, 7, 11, 9, 8}
{6, 9, 13, 11, 10}
{10, 13, 17, 15, 14}
{7, 10, 14, 12, 11}}
Consulta 1: No existe una ruta con todos los elementos pares.
Consulta 2: existe una ruta con número par desde la celda (1, 4) a (1, 3) con todas las celdas como número par. El camino es (1, 4) -> (1, 3).
Consulta 3: No existe ninguna ruta con todos los elementos parejos.
Enfoque: la idea es precalcular la suma del prefijo de las arrays R[] y C[] y luego verificar la ruta válida con las condiciones dadas. A continuación se muestran los pasos:
- La idea es iterar desde la celda (r, c) a (r + 1, c) solo si la paridad de R[r] y R[r + 1] es la misma porque solo cambia un elemento.
- De manera similar, para las columnas de (r, c) a (r, c + 1) , la paridad de C y C debe ser la misma.
- Realice las operaciones anteriores para (r – 1, c) y (r, c – 1) .
- Ahora, para cada consulta, procede comprobando si todos los elementos de R[] desde r = (min(A, B) hasta max(A, B)) tienen la misma paridad y si todos los elementos de C[] desde c = (min (X, Y) a max(X, Y)) tienen la misma paridad. Esto se puede verificar en tiempo O (1) por consulta precalculando la suma de paridad de elementos del prefijo.
- Si la condición anterior se cumple para todas las celdas, imprima «Sí» . De lo contrario, imprima «No» .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find whether the path // exists with all element even or not void answerQueries(int n, int q, vector<int>& a, vector<int>& b, vector<vector<int> >& Queries) { // Add 0 to beginning to make // 1-based-indexing a.insert(a.begin(), 0); b.insert(b.begin(), 0); // Change elements based on parity // and take prefix sum // 1 is odd and 0 is even // Traverse the array R[] for (int i = 1; i <= n; i++) { // Taking & to check parity if (a[i] & 1) a[i] = 1; else a[i] = 0; // Build prefix sum array a[i] += a[i - 1]; } // Traverse the array C[] for (int i = 1; i <= n; i++) { // Taking & to check parity if (b[i] & 1) b[i] = 1; else b[i] = 0; // Build prefix sum array b[i] += b[i - 1]; } // Traverse the matrix Queries[][] for (int i = 0; i < q; i++) { int ra = Queries[i][0]; int ca = Queries[i][1]; int rb = Queries[i][2]; int cb = Queries[i][3]; int r2 = max(ra, rb), r1 = min(ra, rb); int c2 = max(ca, cb), c1 = min(ca, cb); // Check if all numbers are of // same parity between (r1 to r2) if ((a[r2] - a[r1 - 1] == 0) || (a[r2] - a[r1 - 1] == r2 - r1 + 1)) { // Check if all numbers are of // same parity between (r1 to r2) if ((b[c2] - b[c1 - 1] == 0) || (b[c2] - b[c1 - 1] == c2 - c1 + 1)) { // Path exists cout << "Yes" << ' '; continue; } } // No path exists cout << "No" << ' '; } } // Driver Code int main() { // Given N, Q int N = 5, Q = 3; // Given array R[] and C[] vector<int> R{ 6, 2, 7, 8, 3 }; vector<int> C{ 3, 4, 8, 5, 1 }; // Given queries[][] vector<vector<int> > Queries{ { 2, 2, 1, 3 }, { 4, 2, 4, 3 }, { 5, 1, 3, 4 } }; // Function Call answerQueries(N, Q, R, C, Queries); return 0; }
Java
// Java program for the above approach import java.util.*; import java.lang.*; import java.io.*; class GFG{ // Function to find whether the path // exists with all element even or not static void answerQueries(int n, int q, int[] a, int[] b, int[][] Queries) { // Add 0 to beginning to make // 1-based-indexing // a[0]=0; // b[0]=0; // Change elements based on parity // and take prefix sum // 1 is odd and 0 is even // Traverse the array R[] for(int i = 1; i <= n; i++) { // Taking & to check parity if ((a[i] & 1) != 0) a[i] = 1; else a[i] = 0; // Build prefix sum array a[i] += a[i - 1]; } // Traverse the array C[] for(int i = 1; i <= n; i++) { // Taking & to check parity if ((b[i] & 1) != 0) b[i] = 1; else b[i] = 0; // Build prefix sum array b[i] += b[i - 1]; } // Traverse the matrix Queries[][] for(int i = 0; i < q; i++) { int ra = Queries[i][0]; int ca = Queries[i][1]; int rb = Queries[i][2]; int cb = Queries[i][3]; int r2 = Math.max(ra, rb), r1 = Math.min(ra, rb); int c2 = Math.max(ca, cb), c1 = Math.min(ca, cb); // Check if all numbers are of // same parity between (r1 to r2) if ((a[r2] - a[r1 - 1] == 0) || (a[r2] - a[r1 - 1] == r2 - r1 + 1)) { // Check if all numbers are of // same parity between (r1 to r2) if ((b[c2] - b[c1 - 1] == 0) || (b[c2] - b[c1 - 1] == c2 - c1 + 1)) { // Path exists System.out.print("Yes" + " "); continue; } } // No path exists System.out.print("No" + " "); } } // Driver Code public static void main (String[] args) throws java.lang.Exception { // Given N, Q int N = 5, Q = 3; // Given array R[] and C[] int R[] = { 0, 6, 2, 7, 8, 3 }; int C[] = { 0, 3, 4, 8, 5, 1 }; // Given queries[][] int[][] Queries = { { 2, 2, 1, 3 }, { 4, 2, 4, 3 }, { 5, 1, 3, 4 }}; // Function call answerQueries(N, Q, R, C, Queries); } } // This code is contributed by bikram2001jha
Python3
# Python3 program for # the above approach # Function to find whether the path # exists with all element even or not def answerQueries(n, q, a, b, Queries): # Add 0 to beginning to make # 1-based-indexing # a[0]=0; # b[0]=0; # Change elements based on parity # and take prefix sum # 1 is odd and 0 is even # Traverse the array R for i in range(1, n + 1): # Taking & to check parity if ((a[i] & 1) != 0): a[i] = 1; else: a[i] = 0; # Build prefix sum array a[i] += a[i - 1]; # Traverse the array C for i in range(1, n + 1): # Taking & to check parity if ((b[i] & 1) != 0): b[i] = 1; else: b[i] = 0; # Build prefix sum array b[i] += b[i - 1]; # Traverse the matrix Queries for i in range(0, q): ra = Queries[i][0]; ca = Queries[i][1]; rb = Queries[i][2]; cb = Queries[i][3]; r2 = max(ra, rb); r1 = min(ra, rb); c2 = max(ca, cb); c1 = min(ca, cb); # Check if all numbers are of # same parity between (r1 to r2) if ((a[r2] - a[r1 - 1] == 0) or (a[r2] - a[r1 - 1] == r2 - r1 + 1)): # Check if all numbers are of # same parity between (r1 to r2) if ((b[c2] - b[c1 - 1] == 0) or (b[c2] - b[c1 - 1] == c2 - c1 + 1)): # Path exists print("Yes", end = " "); continue; # No path exists print("No", end = " "); # Driver Code if __name__ == '__main__': # Given N, Q N = 5; Q = 3; # Given array R and C R = [0, 6, 2, 7, 8, 3]; C = [0, 3, 4, 8, 5, 1]; # Given queries Queries = [[2, 2, 1, 3], [4, 2, 4, 3], [5, 1, 3, 4]]; # Function call answerQueries(N, Q, R, C, Queries); # This code is contributed by shikhasingrajput
C#
// C# program for // the above approach using System; class GFG{ // Function to find whether the path // exists with all element even or not static void answerQueries(int n, int q, int[] a, int[] b, int[,] Queries) { // Add 0 to beginning to make // 1-based-indexing // a[0]=0; // b[0]=0; // Change elements based on parity // and take prefix sum // 1 is odd and 0 is even // Traverse the array R[] for(int i = 1; i <= n; i++) { // Taking & to check parity if ((a[i] & 1) != 0) a[i] = 1; else a[i] = 0; // Build prefix sum array a[i] += a[i - 1]; } // Traverse the array C[] for(int i = 1; i <= n; i++) { // Taking & to check parity if ((b[i] & 1) != 0) b[i] = 1; else b[i] = 0; // Build prefix sum array b[i] += b[i - 1]; } // Traverse the matrix Queries[,] for(int i = 0; i < q; i++) { int ra = Queries[i, 0]; int ca = Queries[i, 1]; int rb = Queries[i, 2]; int cb = Queries[i, 3]; int r2 = Math.Max(ra, rb), r1 = Math.Min(ra, rb); int c2 = Math.Max(ca, cb), c1 = Math.Min(ca, cb); // Check if all numbers are of // same parity between (r1 to r2) if ((a[r2] - a[r1 - 1] == 0) || (a[r2] - a[r1 - 1] == r2 - r1 + 1)) { // Check if all numbers are of // same parity between (r1 to r2) if ((b[c2] - b[c1 - 1] == 0) || (b[c2] - b[c1 - 1] == c2 - c1 + 1)) { // Path exists Console.Write("Yes" + " "); continue; } } // No path exists Console.Write("No" + " "); } } // Driver Code public static void Main(String[] args) { // Given N, Q int N = 5, Q = 3; // Given array R[] and C[] int []R = {0, 6, 2, 7, 8, 3}; int []C = {0, 3, 4, 8, 5, 1}; // Given [,]queries int[,] Queries = {{2, 2, 1, 3}, {4, 2, 4, 3}, {5, 1, 3, 4}}; // Function call answerQueries(N, Q, R, C, Queries); } } // This code is contributed by Princi Singh
Javascript
<script> // Javascript program to implement // the above approach // Function to find whether the path // exists with all element even or not function answerQueries(n, q, a, b,Queries) { // Add 0 to beginning to make // 1-based-indexing // a[0]=0; // b[0]=0; // Change elements based on parity // and take prefix sum // 1 is odd and 0 is even // Traverse the array R[] for(let i = 1; i <= n; i++) { // Taking & to check parity if ((a[i] & 1) != 0) a[i] = 1; else a[i] = 0; // Build prefix sum array a[i] += a[i - 1]; } // Traverse the array C[] for(let i = 1; i <= n; i++) { // Taking & to check parity if ((b[i] & 1) != 0) b[i] = 1; else b[i] = 0; // Build prefix sum array b[i] += b[i - 1]; } // Traverse the matrix Queries[][] for(let i = 0; i < q; i++) { let ra = Queries[i][0]; let ca = Queries[i][1]; let rb = Queries[i][2]; let cb = Queries[i][3]; let r2 = Math.max(ra, rb), r1 = Math.min(ra, rb); let c2 = Math.max(ca, cb), c1 = Math.min(ca, cb); // Check if all numbers are of // same parity between (r1 to r2) if ((a[r2] - a[r1 - 1] == 0) || (a[r2] - a[r1 - 1] == r2 - r1 + 1)) { // Check if all numbers are of // same parity between (r1 to r2) if ((b[c2] - b[c1 - 1] == 0) || (b[c2] - b[c1 - 1] == c2 - c1 + 1)) { // Path exists document.write("Yes" + " "); continue; } } // No path exists document.write("No" + " "); } } // Driver Code // Given N, Q let N = 5, Q = 3; // Given array R[] and C[] let R = [0, 6, 2, 7, 8, 3 ]; let C = [0, 3, 4, 8, 5, 1 ]; // Given queries[][] let Queries = [[2, 2, 1, 3], [4, 2, 4, 3 ], [5, 1, 3, 4 ]]; // Function call answerQueries(N, Q, R, C, Queries); // This code is contributed by avijitmondal1998. </script>
Yes Yes No
Complejidad temporal: O(N + Q)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por rohitpal210 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA