Mensajes

[final]

Han pasado tres días y no hay soluciones, así que explico como se resuelve (aunque si se buscaba en Google el nombre del problema tal y como dije, explica en muchos sitios diferentes la solución).

La solución más eficiente es un algoritmo greedy que consiste en ordenar los intervalos por hora de final. Una vez hecho esto, se coge el primero y se va cogiendo el siguiente que no solape con el último cogido.

Código (cpp) [Seleccionar] Expandir

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

typedef pair<int, int> PII;

bool comp(PII a, PII b) {
    return (a.second < b.second) or (a.second == b.second and a.first < b.first);
}

int main() {
    int n;
    cin >> n;
    vector<PII> v(n);
    for (int i = 0; i < n; ++i) cin >> v[i].first >> v[i].second;
    sort(v.begin(), v.end(), comp);
    int cnt = 0, ant = -1;
    for (int i = 0; i < n ; ++i) {
        if (v[i].first >= ant) {
            ++cnt;
            ant = v[i].second;
        }
    }
    cout << cnt << endl;
}


El último for de este algoritmo es lineal, por lo que la complejidad se ve dominada por el coste de ordenar, que usando un algoritmo eficiente como por ejemplo Merge Sort deja una complejidad de O(NlogN).

Otra solución menos eficiente pero válida con las restricciones que puse es la dinámica cuadrática que se puede hacer en función de la N, que tiene complejidad O(N²).

Código (cpp) [Seleccionar] Expandir

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

typedef pair<int, int> PII;

int main() {
    int n;
    cin >> n;
    vector<PII> v(n);
    for (int i = 0; i < n; ++i) cin >> v[i].first >> v[i].second;
    sort(v.begin(), v.end());
    vector<int> M(n);
    int res = 0;
    for (int i = 0; i < n ; ++i) {
        M[i] = 1;
        for (int j = 0; j < i; ++j)
            if (v[j].second <= v[i].first) M[i] = max(M[i], M[j] + 1);
        res = max(res, M[i]);
    }
    cout << res << endl;
}


La idea de la dinámica es que M[ i] representa el máximo número de intervalos que puedo coger usando el i-ésimo en último lugar. Como están ordenados los intervalos por inicio (en el otro se ordenaba por final), el algoritmo planteado es correcto.

Como veo que no hay soluciones, os digo el nombre del problema que os he puesto, que como ya dije es bastante conocido como típico problema greedy, a ver si así aparece alguna solución. El problema se conoce como Activity selection problem.

Supongo que por matriz de nodos te referirás a la matriz que te permita reconstruir cada camino mínimo. Si esto es lo que te refieres, la forma típica de hacerlo es que una vez acabado el algoritmo, la posición M(i,j) de la matriz te diga el penúltimo nodo del menor camino de i a j, llamémosle k, para luego consultar M(i,k) y así hasta llegar al nodo i.

Para ello, normalmente se inicializa poniendo lo que quieras entre nodos que no tengan aristas (puesto que si hay un camino se sobreescribirá y si no lo hay lo verás en la matriz de distancias, por lo que ignorarás lo que tengas en esta).

En tu ejemplo, la matriz de distancias inicial sería así:
0 3 INF
3 0 5
INF 5 0

Y la matriz de antecesores sería:
A A X
B B B
X C C

Donde X quiere decir que puedes poner lo que quieras.

Si no me he equivocado al picarlo rápido, el código sería así en C++:

Código (cpp) [Seleccionar] Expandir

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

const int INF = 1000000000;

int main() {
    int n, m; //nodos, aristas
    cin >> n >> m;
    vector<vector<int> > G(n, vector<int> (n, INF)); //Matriz de distancias
    vector<vector<int> > A(n, vector<int> (n, -1)); //Matriz de antecesores
    for (int i = 0; i < n; ++i) G[i][i] = 0;
    for (int i = 0; i < n; ++i) A[i][i] = i;
    for (int i = 0; i < m; ++i) { //Lectura de aristas
        int a, b, c; //extremos y coste
        cin >> a >> b >> c;
        G[a][b] = G[b][a] = c;
        A[a][b] = a;
        A[b][a] = b;
    }
    cout << "Estado inicial de las matrices" << endl;
    cout << "Matriz de distancias:" << endl;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << G[i][j] << '\t';
        }
        cout << endl;
    }
    cout << "Matriz de antecesores:" << endl;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << A[i][j] << '\t';
        }
        cout << endl;
    }
    //Floyd-Warshall
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (G[i][j] > G[i][k] + G[k][j]) {
                    G[i][j] = G[i][k] + G[k][j];
                    A[i][j] = A[k][j];
                    A[j][i] = A[k][i];
                }
            }
        }
    }
    cout << endl;
    cout << "Estado final de las matrices" << endl;
    cout << "Matriz de distancias:" << endl;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << G[i][j] << '\t';
        }
        cout << endl;
    }
    cout << "Matriz de antecesores:" << endl;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << A[i][j] << '\t';
        }
        cout << endl;
    }
}


Y ejecutándolo con tu grafo (cambiando los nombres de los nodos, en vez de A B C, 0 1 2), es decir, poniendo como entrada:

Código [Seleccionar] Expandir

3 2
0 1 3
1 2 5
Da la siguiente salida:

Código [Seleccionar] Expandir

Estado inicial de las matrices
Matriz de distancias:
0       3       1000000000
3       0       5
1000000000      5       0
Matriz de antecesores:
0       0       -1
1       1       1
-1      2       2

Estado final de las matrices
Matriz de distancias:
0       3       8
3       0       5
8       5       0
Matriz de antecesores:
0       0       1
1       1       1
1       2       2

[Reto #12]

Pues pongo uno que es bastante conocido pero que es interesante si no se conoce.

Reto #12
Año 2546, un ladrón quiere cometer una serie de robos en tiendas. Concretamente, hay N tiendas y para cada una, tras una exitosa tarea de investigación, sabe en qué intervalo de tiempo no hay vigilancia (y podrá cometer el robo).

Nuestro ladrón puede teletransportarse de un sitio a otro de forma instantánea (los coches son cosa del pasado), pero sólo robará una tienda si puede dedicar el intervalo completo sin vigilancia a robarla. Por ejemplo, si tenemos dos tiendas con intervalos [100, 200] y [200, 300], podrá robar las dos (recordemos que se puede teletransportar), pero si fueran [100, 200] y [199, 300] sólo podría robar una de las dos.

Entrada:
Un número N <= 1000, seguido de N líneas. En cada una de estas líneas habrá dos números X Y, indicando que la tienda i-ésima no tiene vigilancia en ese intervalo de tiempo. Se cumplirá que 0 <= X,Y <= 10⁹.

Salida:
El máximo número de tiendas que podrá robar.

Ejemplo:

Entrada:

Código [Seleccionar] Expandir

5
1 3
2 4
3 5
1 2
5 6

Salida:

Código [Seleccionar] Expandir

3

Nota: Por las restricciones que he puesto, se acepta una solución O(N²), que se puede lograr haciendo una dinámica muy sencilla. Este problema de los intervalos es conocido como típico problema greedy, pues existe una solución greedy O(NlogN).

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?

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.

[Reto #10]

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.

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!

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

He mirado tu código y si lo he entendido bien, creas una matriz de adyacencia con máscaras de bits y cada vez que se añade una arista miras si hay un nodo intermedio que forme un camino alternativo entre ambos nodos, lo que conforma un ciclo de longitud 3 y por lo tanto una situación inconsistente.

Suponiendo que sea eso lo que estás haciendo (en caso contrario dímelo), la solución no es correcta puesto que aunque ese es un caso no consistente claramente, hay más casos "malos" que no detectas, por ejemplo, si tenemos cinco animales que formen con las relaciones un pentágono (un ciclo de longitud cinco).

El problema como bien has enfocado, se reduce a transformar la información en un grafo y decidir si el grafo es de un cierto tipo o no (sabiendo cómo, claro). Si veo que sigue sin salir, daré más pistas.