¡CSAcademy volvió!


#1

Quizá algunos solo conozcan CSAcademy por su herramienta para generar grafos estéticamente agradables de manera sencilla, pero después de 6 meses sin ningún contest ahora ¡¡hay 3 competencias anunciadas!! :star_struck:

La primera de ellas es el miércoles 20 de Febrero a las 13:05. El contest sigue las siguiente reglas.

  • Hay para resolver 5 problemas en 2 horas.
  • Hay full feedback en los problemas (al isntante te dicen si tu envío es correcto o no).
  • Los problemas no tienen puntaje parcial, tu solución debe pasar todos los casos de prueba para ser considerada correcta.
  • Los problemas tienen puntaje dinámico. No es lo mismo hacer un problema súper sencillo que uno más elaborado. Cuantas más personas resuelvan un problema, menor será su puntaje.
  • En caso de empatar en puntos se desempata por penalidad (que es una suma ponderada del tiempo que se tarda en resolver cada problema y los envíos que no son correctos previos al primer envío correcto).

Los problemas están en inglés. Para resolver problemas en castellano pueden usar los que están cargados en el juez online OIAJ :wink:


#3

¡Terminó la primera competencia!

¡¡La próxima es el 6 de Marzo!!

Ya que estoy, aclaro cómo funciona en CSAcademy esta parte. Concretamente tu penalidad total es

\texttt{tiempo_ultimo_Accepted} + \sum\limits_{p \in \mathcal{P}} f(p)

Donde f(p) es la penalidad del problema p, que es: f(p) = 5 \log _2(e_p), donde e_p es la cantidad de envíos en el problema p hasta el primer Accepted. Por lo tanto los primeros envíos incorrectos de cada problema son mucho más costosos.

Dejo acá los problemas que me salieron (y cuando termino de codear el D lo agrego más tarde).

Sugarel and Modulo
#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 dforn(i,n) for(tint i = tint(n)-1; i >= 0; i--)
#define debug(x) cout << #x << " = "  << x << endl

using namespace std;

typedef long long tint;


tint mod (tint a, tint b)
{
	a %= b;
	if (a < 0)
		a += b;
	return a;
}

int main()
{
	#ifdef ACMTUYO
		assert(freopen("entrada.in", "r", stdin));
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	tint a,b,m;
	while (cin >> a >> b >> m)
	{
		assert(a <= b);
		if (b-a >= m or mod(a,m) > mod(b,m))
			cout << m-1 << "\n";
		else
			cout << mod(b,m) << "\n";
		
	}
	
	return 0;
}
Sugarel and Substrings
#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 dforn(i,n) for(tint i = tint(n)-1; i >= 0; i--)
#define debug(x) cout << #x << " = "  << x << endl

using namespace std;

typedef long long tint;


int main()
{
	#ifdef ACMTUYO
		assert(freopen("entrada.in", "r", stdin));
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	tint n;
	string s;
	while (cin >> n >> s)
	{
		tint total = 0;
		forn(i,n)
		{
			tint mask_letras = 0;
			forsn(j,i,n) // nunca avanza mas que alfabeto por palomar.
			{
				tint letra = tint(s[j]-'a');
				if ( (mask_letras & (1LL << letra)) == 0)
				{
					total++;
					mask_letras |= (1LL << letra);
				}
				else
					break;
			}
		}
		cout << total << "\n";
	}
	
	return 0;
}
Sugarel and Bars
#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 dforn(i,n) for(tint i = tint(n)-1; i >= 0; i--)
#define debug(x) cout << #x << " = "  << x << endl

using namespace std;

typedef int tint;

const tint MAXN = 131072;
bitset<MAXN> alcanzables[2];
vector<tint> ladj[MAXN]; 

void dfs(tint actual, tint k)
{
	alcanzables[k][actual] = 1;
	for (const auto &vecino : ladj[actual])
		if (!alcanzables[k][vecino])
			dfs(vecino,k);
}

int main()
{
	#ifdef ACMTUYO
		assert(freopen("entrada.in", "r", stdin));
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	tint n,m;
	while (cin >> n >> m)
	{
		tint x,y;
		cin >> x >> y;
		x--;
		y--;
		
		forn(i,m)
		{
			tint a,b;
			cin >> a >> b;
			if (a != b)
				ladj[b-1].emplace_back(a-1);
			
		}
		dfs(x,0);
		dfs(y,1);
		
		bool hay_interseccion = ((alcanzables[0] & alcanzables[1]).count() > 0);
		
		forn(i,n)
		{
			if (i)
				cout << " ";
			if (alcanzables[0][i] && alcanzables[1][i])
				cout << "0";
			else if (alcanzables[0][i] or alcanzables[1][i] or hay_interseccion)
				cout << "1";
			else
				cout << "2";
		}
		cout << "\n";
	}
	
	return 0;
}

#4

Agrego el problema D

Sugarel and Love
#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 dforn(i,n) for(tint i = tint(n)-1; i >= 0; i--)
#define debug(x) cout << #x << " = "  << x << endl

using namespace std;

typedef long long tint;

const tint MAXK = 4;
const tint MAXN = 131072;
tint best_dp[MAXN][MAXK]; // Lo mejor usando k hijos.
vector<pair<tint,tint> > ladj[MAXN];
tint aux[MAXK];

tint best(tint i, tint k, tint padre)
{
	if (best_dp[i][k] == -1)
	{
		pair<tint,tint> maxi = {0,0};
		tint suma = 0;
		for (const auto &arista : ladj[i])
		{
			tint hijo = arista.first;
			tint peso = arista.second;
			if (hijo != padre)
			{
				tint best_hijo = max(best(hijo,0,i),max(best(hijo,1,i),best(hijo,2,i)));
				
				suma += best_hijo;
				tint usar_arista = max(best(hijo,0,i),best(hijo,1,i)) + peso - best_hijo;
				maxi = max(maxi, max(make_pair(maxi.first,usar_arista),make_pair(usar_arista,maxi.first) ) );
			}
		}
		tie(aux[0],aux[1],aux[2]) = make_tuple(0,maxi.first,maxi.first+maxi.second);
		best_dp[i][k] = suma + aux[k];
	}
	return best_dp[i][k];
}

int main()
{
	#ifdef ACMTUYO
		assert(freopen("entrada.in", "r", stdin));
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	tint n;
	while (cin >> n)
	{
		forn(i,n)
		{
			ladj[i] = {};
			forn(j,MAXK)
				best_dp[i][j] = -1;
		}
		
		forn(i,n-1)
		{
			tint x,y,z;
			cin >> x >> y >> z;
			ladj[x-1].emplace_back(y-1,z);
			ladj[y-1].emplace_back(x-1,z);
		}
		
		cout << max(best(0,0,-1),max(best(0,1,-1),best(0,2,-1))) << "\n";
		
		
	}
	
	return 0;
}