Dada una secuencia bitónica ‘S’ y ‘Q’ no. de consultas Cada consulta contiene un número entero x i , 1 <= i <= Q. La tarea es imprimir la longitud de la secuencia bitónica después de insertar el número entero para cada consulta. Además, imprima la secuencia bitónica después de todas las consultas.
Ejemplos:
Entrada: S = { 1, 2, 5, 2 }, Q = 4, x = { 5, 1, 3, 2 }
Salida:
4
5
6
6
Secuencia bitónica: 1 2 3 5 2 1
Explicación:
- Para la primera consulta, necesitamos insertar x 1 = 5, pero dado que 5 es el elemento máximo y solo podemos tener una aparición del elemento máximo en S, no insertaremos 5 en S. Por lo tanto, tamaño = 4.
- Para la segunda consulta, necesitamos insertar x 2 = 1, por lo que lo insertamos en la parte decreciente ya que la parte creciente ya tiene 1. Por lo tanto, tamaño = 5.
- Para la tercera consulta, insertamos x 3 = 3 en el lado creciente para que el tamaño sea 6.
- Para la cuarta consulta, no podemos insertar x 2 = 2 ya que 2 está tanto en el lado creciente como en el decreciente.
Entrada: S = { 1, 2, 5, 2 }, Q = 4, x = { 5, 6, 4, 4 }
Salida:
4
5
6
7
Secuencia bitónica: 1 2 4 5 6 4 2
Planteamiento: La idea es hacer dos conjuntos, uno de secuencia creciente y otro de secuencia decreciente.
- Ahora, para cada consulta, primero verifique si x i es mayor que el elemento máximo en la secuencia bitónica o no.
- En caso afirmativo, actualice la secuencia máxima e incluya ese elemento en el conjunto para secuencia creciente.
- De lo contrario, verifique si ese elemento está presente en el conjunto de secuencias crecientes, si no lo incluye en el conjunto de secuencias crecientes, de lo contrario, inclúyalo en el conjunto de secuencias decrecientes.
A continuación se muestra la implementación de este enfoque:
C++
// C++ implementation of above approach #include <bits/stdc++.h> using namespace std; // Function to find the bitonic sequence void solveQuery(int a[], int n, int x[], int q) { int maxx = INT_MIN; // Finding the maximum element for (int i = 0; i < n; i++) maxx = max(maxx, a[i]); set<int> s1, s2; s1.insert(a[0]); s2.insert(a[n - 1]); // set to include increasing sequence element for (int i = 1; i < n; i++) if (a[i] > a[i - 1]) s1.insert(a[i]); // set to include decreasing sequence element for (int i = n - 2; i >= 0; i--) if (a[i] > a[i + 1]) s2.insert(a[i]); // removing maximum element from // decreasing sequence set s2.erase(s2.find(maxx)); // for each query for (int i = 0; i < q; i++) { // checking if x is greater than // maximum element or not. if (maxx <= x[i]) { maxx = x[i]; s1.insert(x[i]); } else { // checking if x lie in increasing sequence if (s1.find(x[i]) == s1.end()) s1.insert(x[i]); // else insert into decreasing sequence set else s2.insert(x[i]); } // finding the length int ans = s1.size() + s2.size(); cout << ans << "\n"; } // printing the sequence set<int>::iterator it; for (it = s1.begin(); it != s1.end(); it++) cout << (*it) << " "; set<int>::reverse_iterator rit; for (rit = s2.rbegin(); rit != s2.rend(); rit++) cout << (*rit) << " "; } // Driver code int main() { int a[] = { 1, 2, 5, 2 }; int n = sizeof(a) / sizeof(a[0]); int x[] = { 5, 1, 3, 2 }; int q = sizeof(x) / sizeof(x[0]); solveQuery(a, n, x, q); return 0; }
Java
// Java implementation of above approach import java.util.*; class GFG { // Function to find the bitonic sequence static void solveQuery(int a[], int n, int x[], int q) { int maxx = Integer.MIN_VALUE; // Finding the maximum element for (int i = 0; i < n; i++) maxx = Math.max(maxx, a[i]); Set<Integer> s1 = new HashSet<>(), s2 = new HashSet<>(); s1.add(a[0]); s2.add(a[n - 1]); // set to include increasing sequence element for (int i = 1; i < n; i++) if (a[i] > a[i - 1]) s1.add(a[i]); // set to include decreasing sequence element for (int i = n - 2; i >= 0; i--) if (a[i] > a[i + 1]) s2.add(a[i]); // removing maximum element from // decreasing sequence set s2.remove(maxx); // for each query for (int i = 0; i < q; i++) { // checking if x is greater than // maximum element or not. if (maxx <= x[i]) { maxx = x[i]; s1.add(x[i]); } else { // checking if x lie in increasing sequence if (!s1.contains(x[i])) s1.add(x[i]); // else insert into decreasing sequence set else s2.add(x[i]); } // finding the length int ans = s1.size() + s2.size(); System.out.print(ans + "\n"); } // printing the sequence for (Integer it : s1) System.out.print((it) + " "); for (Integer it : s2) System.out.print((it) + " "); } // Driver code public static void main(String[] args) { int a[] = { 1, 2, 5, 2 }; int n = a.length; int x[] = { 5, 1, 3, 2 }; int q = x.length; solveQuery(a, n, x, q); } } // This code is contributed by Rajput-Ji
Python3
# Python3 implementation of above approach import sys # Function to find the bitonic sequence def solveQuery(a, n, x, q): maxx = -sys.maxsize # Finding the maximum element for i in range(n): maxx = max(maxx, a[i]) s1, s2 = set(), set() s1.add(a[0]) s2.add(a[n - 1]) # set to include increasing sequence element for i in range(1, n): if a[i] > a[i - 1]: s1.add(a[i]) # set to include decreasing sequence element for i in range(n - 2, -1, -1): if a[i] > a[i + 1]: s2.add(a[i]) # removing maximum element from # decreasing sequence set s2.remove(maxx) # for each query for i in range(q): # checking if x is greater than # maximum element or not. if maxx <= x[i]: maxx = x[i] s1.add(x[i]) else: # checking if x lie in increasing sequence if x[i] not in s1: s1.add(x[i]) # else insert into decreasing sequence set else: s2.add(x[i]) # finding the length ans = len(s1) + len(s2) print(ans) # printing the sequence for i in s1: print(i, end = " ") for i in reversed(list(s2)): print(i, end = " ") # Driver Code if __name__ == "__main__": a = [1, 2, 5, 2] n = len(a) x = [5, 1, 3, 2] q = len(x) solveQuery(a, n, x, q) # This code is contributed by # sanjeev2552
C#
// C# implementation of above approach using System; using System.Collections.Generic; class GFG { // Function to find the bitonic sequence static void solveQuery(int []a, int n, int []x, int q) { int maxx = int.MinValue; // Finding the maximum element for (int i = 0; i < n; i++) maxx = Math.Max(maxx, a[i]); HashSet<int> s1 = new HashSet<int>(), s2 = new HashSet<int>(); s1.Add(a[0]); s2.Add(a[n - 1]); // set to include increasing sequence element for (int i = 1; i < n; i++) if (a[i] > a[i - 1]) s1.Add(a[i]); // set to include decreasing sequence element for (int i = n - 2; i >= 0; i--) if (a[i] > a[i + 1]) s2.Add(a[i]); // removing maximum element from // decreasing sequence set s2.Remove(maxx); // for each query for (int i = 0; i < q; i++) { // checking if x is greater than // maximum element or not. if (maxx <= x[i]) { maxx = x[i]; s1.Add(x[i]); } else { // checking if x lie in increasing sequence if (!s1.Contains(x[i])) s1.Add(x[i]); // else insert into decreasing sequence set else s2.Add(x[i]); } // finding the length int ans = s1.Count + s2.Count; Console.Write(ans + "\n"); } // printing the sequence foreach (int it in s1) Console.Write((it) + " "); foreach (int it in s2) Console.Write((it) + " "); } // Driver code public static void Main(String[] args) { int []a = { 1, 2, 5, 2 }; int n = a.Length; int []x = { 5, 1, 3, 2 }; int q = x.Length; solveQuery(a, n, x, q); } } // This code is contributed by Rajput-Ji
Javascript
<script> // Javascript implementation of above approach // Function to find the bitonic sequence function solveQuery(a, n, x, q) { let maxx = Number.MIN_VALUE; // Finding the maximum element for (let i = 0; i < n; i++) maxx = Math.max(maxx, a[i]); let s1 = new Set(); let s2 = new Set(); s1.add(a[0]); s2.add(a[n - 1]); // set to include increasing sequence element for (let i = 1; i < n; i++) if (a[i] > a[i - 1]) s1.add(a[i]); // set to include decreasing sequence element for (let i = n - 2; i >= 0; i--) if (a[i] > a[i + 1]) s2.add(a[i]); // removing maximum element from // decreasing sequence set s2.delete(maxx); // for each query for (let i = 0; i < q; i++) { // checking if x is greater than // maximum element or not. if (maxx <= x[i]) { maxx = x[i]; s1.add(x[i]); } else { // checking if x lie in increasing sequence if (!s1.has(x[i])) s1.add(x[i]); // else insert into decreasing sequence set else s2.add(x[i]); } // finding the length let ans = s1.size + s2.size; document.write(ans + "</br>"); } let S1 = Array.from(s1); S1.sort(function(a, b){return a - b}); // printing the sequence S1.forEach (function(it) { document.write(it + " "); }) s2.forEach (function(it) { document.write(it + " "); }) } let a = [ 1, 2, 5, 2 ]; let n = a.length; let x = [ 5, 1, 3, 2 ]; let q = x.length; solveQuery(a, n, x, q); // This code is contributed by decode2207. </script>
Producción:
4 5 6 6 1 2 3 5 2 1