COMPETENCIA 11 de Febrero : Lista de problemas - CodeForces


#1

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 :roll_eyes:

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


#2

¡Oooooh competencia!


#3

¡Ya empezó!

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


#4

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


#5

Hola @Al-Garin

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

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:


#6

:crazy_face: :crazy_face: ¡Quedan 3 días! :crazy_face: :crazy_face:


#7

:crazy_face::exploding_head:¡¡Último día!!:crazy_face::exploding_head:


#8

¡Se terminó el contest!

El top 3 terminó de la siguiente manera:

¡Felicitaciones!

Un par de comentarios:

  • Sobre el problema “Mike and Feet” ya había un post en el foro que hablaba al respecto :wink:
  • 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.


#9

Muy buenos los problemas y felicitaciones al resto :clap::clap::clap:.
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.


#10

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.


#11

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


#12

¡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.


#13

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?


#14

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:

5 4
1 2
3 4
4 5
3 5

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

#15

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 :unamused:. 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;
}

#16

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.


#17

¡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!


#18

Hola, muchas gracias por la ayuda! Me dio AC :smiley:.
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 << " ";
    }
}

#20

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.