COMPETENCIA 11 de Febrero : Lista de problemas - CodeForces

Guty · 9 Febrero, 2019 20:56

Hola a todos,

Agarré algunos de los problemas de CodeForces que alguna vez me había marcado como “este problema está bueno”, y agregué algunos otros. Con eso armé una lista de 18 problemas, que van a formar parte de una mini competencia que comienza el Lunes 11 de Febrero y dura todo lo que queda del mes.

¿Cómo me inscribo?

Es sencillo, solo hace falta:

Tener un usuario en CodeForces
Tener un usuario en AhmedAly
En su usuario de Ahmed Aly, ingresar en la entrada “Codeforces Handle” tu nombre de usuario de CodeForces
Entrar a esta página para registrarse en la competencia (click en Register Individually).

¿Tengo que notificar cuando realizo un problema?

Si realizaste los pasos anteriores, con solamente enviar el problema en CodeForces la tabla de posiciones se actualiza sola, así que no hace falta.

¿Hay premio?

Quizá.

Mucho texto, ¿dónde están los problemas?

Acá: Lista de Problemas

Comentario

No están en ningún orden en particular (puede venir uno “fácil”, después uno “difícil” y después otra vez uno “fácil”).

¿Y si quiero más problemas?

Además, hay una lista de problemas súper recomendable que ya mencioné en otro post.

CSES Problem Set

Todos los problemas están en inglés

Igual Google Translate suele funcionar bien (a veces no, a veces te dice que un ángulo llano es un ángulo recto )

santo · 11 Febrero, 2019 00:01

¡Oooooh competencia!

Guty · 11 Febrero, 2019 03:33

¡Ya empezó!

Pueden registrarse y resolver problemas durante todo lo que queda del mes

Al-Garin · 17 Febrero, 2019 13:48

Ya me registré en la competencia, ¿hay joyas de premio o tengo que conseguirlas en otro lugar ?

Guty · 18 Febrero, 2019 21:22

Hola @Al-Garin

En este momento mandando un problema quedás primero en la competencia

Joyas reales no podemos dar de premio, pero hay un nuevo diseño de la Insignia Ryckeboer que algunos consideran ser una joya.

Algunos diseños anteriores podés verlos en:

Aprovecho para recordar que todavía hay Desafíos en los que nadie posteó una solución:

Guty · 26 Febrero, 2019 03:20

¡Quedan 3 días!

Guty · 28 Febrero, 2019 03:30

¡¡Último día!!

Guty · 1 Marzo, 2019 17:47

¡Se terminó el contest!

El top 3 terminó de la siguiente manera:

@ignaciocanta con 8 problemas resueltos
@mauroS con 7 problemas resueltos
@reedef con 6 problemas resueltos

¡Felicitaciones!

Un par de comentarios:

Sobre el problema “Mike and Feet” ya había un post en el foro que hablaba al respecto
El problema “Painting Fence” creo que es otro lindo problema de divide and conquer.
Ideas conducentes para resolver el problema “Monitor” están en la charla de búsqueda binaria del Nacional 2017.

¿Cuáles fueron sus problemas favoritos?

Pueden compartir sus soluciones, o incluso preguntar cualquier duda que haya quedado de algún problema.

mauroS · 1 Marzo, 2019 19:06

Muy buenos los problemas y felicitaciones al resto .
Me quedó duda con el problema Cloud of Hashtags. Siento que hice trampa porque pasé con el tiempo muy justito (1.8s de 2s) usando c++ cuando te dejan usar lenguajes más lentos para hacer el problema. Además de que en las tags aparece busqueda binaria la cual no usé.
Acá está mi código. Basicamente voy yendo por cada string del último al primero y me fijo que sea menor lexicograficamente que el siguiente y sino lo recorto para que sea menor.

Guty · 1 Marzo, 2019 19:22

La solución está muy bien. Yo no usé búsqueda binaria, yo hice lo mismo que vos. En este problema hay que escribir mucho output y leer mucho input.

Fijate qué pasa haciendo los siguientes cambios.

Agregá las siguientes líneas después de int main().

ios_base::sync_with_stdio(0);
cin.tie(NULL);

Cambiá \texttt{endl} por \texttt{"\n"} cada vez que escribas un fin de línea. En este caso algo que lo hace lento es que \texttt{endl} hace flush del buffer cada vez. Hay que tener cuidado con esto en algunos problemas interactivos de CodeForces por ejemplo (porque ahí sí queremos hacer flush del buffer). A la hora de hacer debugging es otro lugar natural donde queremos hacer flush del buffer cada vez.

Esto es solo porque CodeForces es un juez online donde hay que leer input y escribir output a la salida estándar. Por ejemplo, en los problemas de OIA donde hay que implementar una función y la entrada está en el encabezado de la función, estas líneas no ayudan en nada.

mauroS · 1 Marzo, 2019 20:01

Muchas gracias!
Pasó de 1.8s a 0.09s
Ahora voy a tratar de hacer los que me quedaron.

Guty · 1 Marzo, 2019 20:14

¡De nada!

Por las dudas remarco que la diferencia es grande en este caso porque hay que LEER MUCHO INPUT y ESCRIBIR MUCHO OUTPUT.

Si el problema era que estabas haciendo muchas operaciones esas líneas no iban a ayudar en nada.

ignaciocanta · 2 Marzo, 2019 19:11

Hola,
A mí el problema que más me gustó fue el siguiente: Game of Credit Cards.
Dejo mi solución.

código

#include <bits/stdc++.h>

using namespace std;

typedef long long tint;

#define forsn(i, s, n) for(tint i=s;i<tint(n);i++)
#define forn(i, n) forsn(i, 0, n)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

int  main() {
	tint n; cin >> n;
	string sherlock, moriarty;
	cin >> sherlock >> moriarty;
	tint contSherlock = 0, contMoriarty = 0;
	string copySherlock = sherlock, copyMoriarty = moriarty;
	sort(all(sherlock)); sort(all(moriarty));
	set<int> used0;
	for(tint i=0;i<n;i++){
		for(tint j=0;j<n;j++){
			if((tint)moriarty[j] > (tint)sherlock[i] && used0.find(j) == used0.end()){
				contSherlock++;
				used0.insert(j);
				break;
			}
		}
	}
	set<int> used;
	for(tint i=0;i<n;i++){
		for(tint j=0;j<n;j++){
			if((tint)moriarty[j] >= (tint)copySherlock[i] && used.find(j) == used.end()){
				contMoriarty++;
				used.insert(j);
				break;
			}
		}
	}
	cout << n-contMoriarty << endl;
	cout << contSherlock;
}

Tengo una duda con el problema NP-Hard Problem.
También adjunto el código.

código

#include <iostream>
#include <vector>
#include<algorithm>

using namespace std;

#define forn(i,n) for(int i=0;i<int(n);i++)

bool esBipartito(vector<vector<int>> grafo, int nodo, vector<bool>& visited, vector<int>& color) { 
    for (int vecino : grafo[nodo]) { 
        if (visited[vecino] == false) { 
            visited[vecino] = true; 
            color[vecino] = !color[nodo]; 
            if (!esBipartito(grafo, vecino, visited, color)) 
                return false; 
        } 
        else if (color[vecino] == color[nodo]) 
            return false; 
    } 
    return true; 
} 


int main(){
	int n,m; cin >> n >> m;
	vector<vector<int>> grafo (n);
	forn(i,m){
		int u,v; cin >> u >> v;
		u--; v--;
		grafo[u].push_back(v); grafo[v].push_back(u);
	}
	
	vector<bool> visited (n, false); vector<int> color (n);
	bool check = esBipartito(grafo, 0, visited, color);
	if(!check){
		cout << -1 << endl; return 0;
	}
    forn(i,n){
    	if(grafo[i].size() == 0)  color.erase(color.begin()+i);
    }
    cout << count(color.begin(), color.end(), 0) << endl;
     forn(i,color.size()){
    	if(color[i] == 0) cout << i+1 << " ";
    }
    cout << endl;
    cout << count(color.begin(), color.end(), 1) << endl;
    forn(i,color.size()){
    	if(color[i] == 1) cout << i+1 << " ";
    }
}

Esta solución me tira “Time Limit Exceeded” en el caso de prueba 14. Creo que el problema está en la implementación de la función “esBipartito”, pero no estoy seguro. Alguien podría decirme cómo hacer mi solución más eficiente?

Guty · 3 Marzo, 2019 01:30

Hola,

En cuanto al Time Limit. Creo que querés pasar grafo por referencia con &. Entiendo que estás haciendo una copia cada vez.

Además, si el grafo que te dan no es conexo creo que el código no estaría resolviendo el problema. Pensá qué pasa en el siguiente ejemplo:

Después hay otro tema, quizá más sutil, a la hora de tratar los nodos aislados. Fijate qué pasa en el siguiente ejemplo.

5 1
1 2

Guty · 2 Marzo, 2019 21:13

Sobre Game of Credit Cards creo que es un problema que primero requiere pensarlo en papel un poco antes de sentarse a codear (esto vale en general para cualquier problema la verdad).

Veo un poco de copy paste . Además yo implementé la misma idea un poquito distinto, así que dejo mi implementación.

Game of Credit Cards

#include <bits/stdc++.h>

#define forsn(i,s,n) for(tint i=(s);i<(tint)(n); i++)
#define forn(i,n) forsn(i,0,n)
#define debug(x) cout << #x << " = "  << x << endl

using namespace std;

typedef long long tint;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	tint n;
	while (cin >> n)
	{
		vector<vector<tint> > hist (2, vector<tint> (10,0));
		vector<string> s (2,"");
		cin >> s[0] >> s[1];
		forn(r,2)
		forn(i,n)
			hist[r][s[r][i]-'0']++; 
		
		vector<tint> ans (2,0);
		vector<vector<vector<tint> > > histP = {hist,hist};
		forn(r,2)
		{
			
			forn(i,10)
			{
				forsn(j,i+r,10)
					if (histP[r][0][i] > 0)
					{
						tint k = min(histP[r][0][i],histP[r][1][j]); 
						histP[r][0][i] -= k;
						histP[r][1][j] -= k;
						if (r == 1)
							ans[r] += k;
					}
				if (r == 0)
					ans[r] += histP[r][r][i]; 
			}
		}
		cout << ans[0] << "\n" << ans[1] << "\n";
		
	}
	return 0;
}

ignaciocanta · 2 Marzo, 2019 21:20

Gracias por la respuesta!
Pasar por referencia “grafo” hace que el caso de prueba 14 ande, pero en el 15 me tirá “runtime error” (tengo entendido que esto mismo sucede con el último ejemplo que me comentaste). Efectivamente, no interpreté de manera correcta lo que el programa debe hacer si el grafo no es conexo. Ahora voy a intentar resolverlo y cualquier cosa te consulto.

Guty · 2 Marzo, 2019 21:23

¡De nada!

Eso es lo que veo ahora que miré el código desde la PC. Creo que tratando bien esas situaciones debería estar, pero si no da AC consultá todo lo que haga falta, ¡para eso está el foro!

ignaciocanta · 2 Marzo, 2019 21:48

Hola, muchas gracias por la ayuda! Me dio AC .
Dejo el código:

código

#include <bits/stdc++.h>

using namespace std;

typedef long long tint;

#define forn(i,n) for(tint i=0;i<tint(n);i++)

bool esBipartito(vector<vector<tint>> &grafo, tint nodo, vector<bool>& visited, vector<tint>& color) { 
    for (tint vecino : grafo[nodo]) { 
        if (visited[vecino] == false) { 
            visited[vecino] = true; 
            color[vecino] = !color[nodo]; 
            if (!esBipartito(grafo, vecino, visited, color)) 
                return false; 
        } 
        else if (color[vecino] == color[nodo]) 
            return false; 
    } 
    return true; 
} 


int main(){
	ios_base::sync_with_stdio(0);
    cin.tie(NULL);
	tint n,m; cin >> n >> m;
	vector<vector<tint>> grafo (n);
	forn(i,m){
		tint u,v; cin >> u >> v;
		u--; v--;
		grafo[u].push_back(v); grafo[v].push_back(u);
	}
	
	vector<bool> visited (n, false); vector<tint> color (n);
	forn(i, n){
		if(!esBipartito(grafo, i, visited, color)){
			cout << -1; return 0;
		}
	}
    cout << count(color.begin(), color.end(), 0) << endl;
     forn(i,color.size()){
    	if(color[i] == 0) cout << i+1 << " ";
    }
    cout << endl;
    cout << count(color.begin(), color.end(), 1) << endl;
   
    forn(i,color.size()){
    	if(color[i] == 1) cout << i+1 << " ";
    }
}

Guty · 5 Marzo, 2019 02:44

Por las dudas aclaro que esas líneas solo deberían usarse con \texttt{cin} y \texttt{cout}.

Otra opción para hacer input y output rápidamente (y quizá más sencilla) es usar las funciones \texttt{printf} y \texttt{scanf} directamente.