Problema E TAP 2022

[Mariano Crosetti]

Si alguien tiene el código del problema "Eliminando Globos", tanto de la solución sería genial.

Lo ideal sería tener de varias soluciones en clase vimos:

- Una que usa un multiset y va de derecha a izquierda

- Una que usa una lista de sets + va de izquierda a derecha + lower_bound / upper_bound

- Una que va de izquierda a derecha y lleva (de alguna manera) la cuenta de cuántas flechas vienen en cada altura (esta supongo que es parecida a la primera pero en orden inverso).

Si pueden poner códigos (que hayan dado Acepted!!) se agreadece

Saludos,

Mariano

[Sebastian Giulianelli]

Está resuelto en Python, probablemente se pueda optimizar mas:

cantidad = int(input())
globos = input()
globos = globos.split(sep = " ")
    
flechas = 0
listaFlechas = {}
eliminados = 0
for i in range(cantidad):
    globo = int(globos[i])
    if not listaFlechas.get(globo):
            flechas += 1
    else:
        listaFlechas[globo] -= 1
    
    eliminados += 1
    if listaFlechas.get(globo - 1) == None:
        listaFlechas[globo - 1] = 1
    else:
        listaFlechas[globo - 1] += 1
   
print(flechas)

[Ariel Leonardo Fideleff]

Dejo mi solución AC para la tercera opción: https://codeforces.com/gym/103960/submission/175712813

Cualquier cosa también adjunto un link al código en GitHub por si no deja ver la submission: https://github.com/ariloc/CompetitiveProgrammingCodes/blob/master/TAP/2022/E%20(my%20version).cpp

[Alvaro Carrera]

Acá dejo una solución prácticamente igual a la anterior pero sin usar maps

#include <bits/stdc++.h>
using namespace std;

const int N=1E6+1;
int n,H[N];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin>>n;
    int ret=0;
    for(int i=0;i<n;++i){
        int x;cin>>x;
        if (H[x]) --H[x];
        else ++ret;
        ++H[x-1];
    }
    cout << ret;
}