Retos C/C++

[Og.]

Buen problema. Así si son divertidos.

Código (cpp) [Seleccionar] Expandir

#include <iostream>

using std::cin;
using std::cout;
using std::endl;

struct pareja
{
    int h;
    int m;
};

pareja *relaciones;
int N, M;
short *pollos, *relacionesChk;
bool correcto;

bool Relaciona(int);
void entid(int num, int tp);

int main(void)
{
    cin >> N >> M;
    pollos = new short[N];
    relacionesChk = new short[M];
    relaciones = new pareja[M];
    for(int i=0; i<M; i++)
        relacionesChk[i] = 0;
    for(int i=0; i<M; i++)
    {
        cin >> relaciones[i].h >> relaciones[i].m;
    }
    correcto = true;
    Relaciona(0);
    if(correcto)
        cout << "SI";
    else
        cout << "NO";
    delete pollos;
    delete relacionesChk;
    delete relaciones;
}

bool Relaciona(int num)
{
    if(!correcto)
        return 0;
    if(num>=M)
        return true;
    for(int i=0; i<N; i++)
        pollos[i] = -1;
    relacionesChk[num] = 1;
    pollos[relaciones[num].h] = 0;
    pollos[relaciones[num].m] = 1;
    entid(relaciones[num].h, 1);
    entid(relaciones[num].m, 0);
    while(relacionesChk[++num] && num<=M);
    Relaciona(num);
}

void entid(int num, int tp)
{
    if(!correcto)
        return;
    for(int i=0; i<M; i++)
        if(!relacionesChk[i])
        {
            if(relaciones[i].h==num)
            {
                relacionesChk[i] = 1;
                if(pollos[relaciones[i].m] == -1)
                {
                    pollos[relaciones[i].m] = tp;
                    entid(relaciones[i].m, !tp);
                }
                else if(pollos[relaciones[i].m] == !tp)
                    correcto = false;
            } else if(relaciones[i].m==num) {
                relacionesChk[i] = 1;
                if(pollos[relaciones[i].h] == -1)
                {
                    pollos[relaciones[i].h] = tp;
                    entid(relaciones[i].h, !tp);
                }
                else if(pollos[relaciones[i].h] == !tp)
                    correcto = false;
            }
        }
    return;
}

[ghastlyX]

Parece correcto mirando el código por encima y probando algunos casos. La idea era ver que el problema se puede convertir en un grafo donde los animales son los nodos y las relaciones entre ellos las aristas. Una vez hecho esto, la cuestión era ver si este grafo era bipartido o no (si se pueden partir los nodos en dos grupos tal que cada grupo no tenga aristas entre ellos, que serán los machos y las hembras).

Es fácil de demostrar y ver que si G = (V,E) es un grafo no dirigido, los siguientes enunciados son equivalentes:

1) G es bipartido.
2) G es bicoloreable (2-coloreable).
3) G no contiene ningún ciclo simple de longitud impar.

Como las tres son equivalentes, se puede mirar cualquiera de ellas y la más eficiente de comprobar es la segunda, que mirando tú código supongo que es lo que haces.

Os dejo también la solución que había preparado:

Código (cpp) [Seleccionar] Expandir

#include <iostream>
#include <vector>
using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;

bool bicolor(int u, int c, VVI& G, VI& color) {
   bool res = true;
   for (int i = 0; i < G[u].size(); ++i) {
       int v = G[u][i];
       if (color[v] < 0) {
           color[v] = c;
           res &= bicolor(v, 1 - c, G, color);
       }
       else if (color[v] != c) res = false;
   }
   return res;
}

int main() {
   int n, m;
   cin >> n >> m;
   VVI G(n);
   for (int i = 0; i < m; ++i) {
       int a, b;
       cin >> a >> b;
       G[a].push_back(b);
       G[b].push_back(a);
   }
   VI color(n, -1);
   bool res = true;
   for (int i = 0; i < n; ++i) { //Por si hay mas de un componente
       if (color[i] < 0) {
           color[i] = 0;
           res &= bicolor(i, 1, G, color);
       }
   }
   if (res) cout << "Si" << endl;
   else cout << "No" << endl;    
}

PD: Cuidado con las salidas, tu código imprime SI y NO en vez de Si y No. A mí me da igual, pero si eres olímpico como supongo por tu firma, ves con cuidado con estas cosas en los concursos, puesto que el juez automático te daría un WA y estos errores tontos en pleno concurso pueden costar de encontrar, pensando que es problema en el código o el razonamiento.

Edito: Se me olvidaba, dos cosas:
- Para saber si un grafo es bicoloreable basta con ir asignando a cada nodo libre un color cualquiera y a sus vecinos el contrario. Si se encuentra algún vecino con el mismo color es que no es bicoloreable.

- Pon el siguiente reto xDD

[Og.]

jeje, a un amigo le paso que no le contaron los casos por un \n de mas al final del programa xD

Reto #9

Recibes don enteros (X, Y) los cuales representan una caja

y tu quieres partir esa caja en cuadrados exactos. hacer un programa que te diga el mínimo numero de cuadrados exactos dentro de una caja.

Ejemplo1

Entrada

Código [Seleccionar] Expandir

3 5

Salida

Código [Seleccionar] Expandir

4
Explicacion
1 caja de 3*3
1 caja de 2*2
2 cajas de 1*1

Ejemplo2

Entrada

Código [Seleccionar] Expandir

5 6

Salida

Código [Seleccionar] Expandir

5
Explicacion
2 cajas de 3*3
3 cajas de 2*2

[ghastlyX]

Supongo que sería así:

Código (cpp) [Seleccionar] Expandir

#include <iostream>
#include <vector>
using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;

const int INF = 1000000000;

int dp(int n, int m, VVI& M) {
    if (n < m) return dp(m, n, M);
    if (m == 0) return 0;
    if (M[n][m] == -1) {
        M[n][m] = INF;
        for (int x = 0; x <= m; ++x) {
            M[n][m] = min(M[n][m], 1 + dp(x, m - x, M) + dp(n - x, m, M));
            M[n][m] = min(M[n][m], 1 + dp(n, m - x, M) + dp(n - x, x, M));
        }
    }
    return M[n][m];
}

int main() {
    int n, m;
    cin >> n >> m;
    if (n < m) swap(n, m);
    VVI M(n + 1, VI(m + 1, -1));
    cout << dp(n, m, M) << endl;
}


A ver si la gente le pierde un poco el miedo a las dinámicas!

[[L]ord [R]NA]

GhastlyX deja el proximo reto... sin mucho chackra

[ghastlyX]

Reto #10
Una compañía de autobuses sospecha que en una de sus rutas el autobús va demasiado lleno y están estudiando poner otro más para mejorar el servicio. Para ello, han colocado un contador en las puertas que registra en cada parada cuánto varía la cantidad de personas en el bus (este número podrá ser obviamente negativo).

En un cierto momento de la ruta, el conductor activa el contador y se generan los registros y más tarde lo apaga (nótese que esto implica que la suma de las diferencias podrá ser negativa, puesto que podía haber gente dentro del bus). La compañía estudiará después las sumas de subsecuencias consecutivas de la secuencia de registros. Por ejemplo, si la secuencia es -20 -15 30 -15 30, subsecuencias consecutivas son entre otras -15 30, 30 o incluso la propia secuencia completa.

Entrada:
Un número N <= 1000 en una línea. En la siguiente línea, N números indicando registros. Se cumple que los números de los registros serán menores en valor absoluto que 100.

Salida:
Escribe la mayor suma que pueda obtenerse de una subsecuencia consecutiva.

Ejemplos:

Entrada 1:

Código [Seleccionar] Expandir

4
1 2 3 4

Salida 1:

Código [Seleccionar] Expandir

10

Entrada 2:

Código [Seleccionar] Expandir

5
-20 -15 30 -15 30

Salida 2:

Código [Seleccionar] Expandir

45

Notas:
- El hecho de que la N pueda ser hasta 1000 implica que una solución trivial de complejidad O(N³) no sirve (es decir, para cada posible inicio y posible final [dos fors anidados], hacer un for más anidado para calcular la suma y quedarse con la mayor). Si alguien no tiene claro si su solución es suficiente rápida (teniendo claro al menos que es correcta), se puede generar 1000 números enteros y ver cómo de rápido es su código. Debería tardar menos de un segundo, si tarda más que eso, el algoritmo no es suficiente bueno (no consiste en optimizar el código).

- Espero una solución de complejidad O(N²) intencionadamente para intentar que el problema sea más sencillo. Este problema se puede solucionar de forma más eficiente, usando una estrategia Divide&Conquer que deja una complejidad de O(NlogN) o incluso una forma ingeniosa para obtener un algoritmo O(N). Si alguien hace algún algoritmo mejor que cuadrático, como los que comento, obviamente el código será correcto.

[cgvwzq]

Solución trivial O(N³):

Código (c) [Seleccionar] Expandir

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {

  int n,*sec,i,j,k;

  if (argc != 2) return 1;

  n = atoi(argv[1]);
  sec = (int*)calloc(n,sizeof(int));
  for (i=0;i<n;i++) scanf("%d",&sec[i]);

  for (i=0;i<n;i++) {
     for (j=i;j<n;j++) {
        sum = 0; for (k=i;k<=j;k++) sum+=sec[k];
        if (sum > max) max = sum;
     }
  }

  printf("%d\n",max);

  free(sec);
  return 0;

}

Solución mejorada, en lugar de sumar cada vez todos los intervalos usamos los datos ya calculados para obtener el nuevo resultado. ¿Es O(N²)?

Código (c) [Seleccionar] Expandir

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {

  int n, i, j, **sec, max=0;

  if (argc != 2) return 1;

  n = atoi(argv[1]);
  if (!(sec = (int**)calloc(n,sizeof(int*)))) return 1;
  for (i=0;i<n;i++) if(!(sec[i] = (int*)calloc(n,sizeof(int)))) return 1;

  for (i=0;i<n;i++) scanf("%d",&sec[0][i]);

  for (i=1;i<n;i++)
     for (j=i;j<n;j++) {
        sec[i][j] = sec[i-1][j]+sec[0][j-i];
        if (sec[i][j] > max) max = sec[i][j];
     }
 
  printf("%d\n",max);

  for (i=0;i<n;i++) free(sec[i]); free(sec);

  return 0;

}

Una mejora clara sería reservar menos espacio, ya que estoy usando tan solo media matriz...

[ghastlyX]

No es la solución cuadrática estándar pero también es cuadrática y correcta, por lo tanto perfecta. En tu solución usas programación dinámica por lo que veo para calcular sec(i,j), que representa la suma de i + 1 elementos acabando en j si lo he entendido bien.

La solución cuadrática estándar usa un solo vector que guarda las sumas acumuladas, dejo el código:

Código (cpp) [Seleccionar] Expandir


#include <vector>
#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> suma(n);
    for (int i = 0; i < n; ++i) {
        cin >> suma[i];
        if (i > 0) suma[i] += suma[i - 1];
    }
    //suma[i] contiene la suma de los i + 1 primeros numeros
    int res = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            //Calculamos la suma de cada intervalo aprovechando el vector de sumas calculadas
            //La suma de [i,j] sera suma[j] - suma[i - 1]
            int temp = suma[j];
            if (i > 0) temp -= suma[i - 1];
            res = max(res, temp);
        }
    }
    cout << res << endl;
}


La solución lineal que comenté, es decir, O(N), además no requiere espacio en memoria extra. Aunque el código es muy simple, la idea puede costar un poco más de ver, pero si alguien se lo mira con invariantes puede ver que es correcto.

Código (cpp) [Seleccionar] Expandir

#include <vector>
#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    int a, res = 0, suma = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a;
        suma += a;
        if (suma < 0) suma = 0;
        res = max(res, suma);
    }
    cout << res << endl;
}

Pon el siguiente reto cuando quieras.

[cgvwzq]

@ghastlyX, la solución lineal es mu chulaa...XD

El programa generará una matriz "sopa de letras" de N x M, usando una función random. A la vez se le pasará una palabra que buscará en la sopa.

- Las letras de la palabra deberán aparecer en orden consecutivo. Podrán estar en horizontal, vertical, diagonal y en orden inverso.
- La sopa de letras contendrá solo minusculas.
- Una vez se encuentra la palabra la búsqueda termina aunque pueda estar repetida (simplifica el problema)

Al finalizar la búsqueda, se imprimirá la sopa de letras con la palabra en mayúsculas (si es que ha sido encontrada), y un mensaje ("Si" o "No") en función de si ha habido éxito.

Entrada:

Código [Seleccionar] Expandir

5 5 pi

Salida:

Código [Seleccionar] Expandir

r v x i l
q l g w f
q c w m n
w q I j j
l q t P q

Si

Entrada:

Código [Seleccionar] Expandir

5 5 zas

Salida:

Código [Seleccionar] Expandir

i v t x u
i l f n y
i e f t l
x j w a k
w e d j o

No

Es bastante sencillo, pero nunca me he planteado un problema de estos, y esto es lo primero que se me ha ocurrido...

[ghastlyX]

Código (cpp) [Seleccionar] Expandir

#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;

int arrf[8] = {-1,-1,-1,0,1,1,1,0};
int arrc[8] = {-1,0,1,1,1,0,-1,-1};

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<char> > S(n, vector<char>(m));
    srand(time(NULL));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            S[i][j] = 'a' + rand()%26;
    string s;
    cin >> s;
    bool busca = true;
    for (int i = 0; i < n and busca; ++i)
        for (int j = 0; j < m and busca; ++j)
            for (int d = 0; d < 8 and busca; ++d) {
                bool ok = true;
                for (int k = 0; k < s.size() and ok; ++k) {
                    int f = i + arrf[d]*k, c = j + arrc[d]*k;
                    if (f < 0 or f >= n or c < 0 or c >= m or S[f][c] != s[k]) ok = false;
                }
                if (ok) {
                    busca = false;
                    for (int k = 0; k < s.size(); ++k) {
                        int f = i + arrf[d]*k, c = j + arrc[d]*k;
                        S[f][c] ^= 32;
                    }
                }
            }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (j > 0) cout << " ";
            cout << S[i][j];
        }
        cout << endl;
    }
    cout << endl << (busca?"No":"Si") << endl;
}


Para el próximo, ¿queréis algo simple o para pensar un poco?