Retos C/C++

[N0body]

Hago concreto por fin el proyecto mío de establecer en la sección de C/C++ una serie de retos.

He aquí las reglas que he elaborado para tal fin, luego agregaré los primeros dos problemas:


Los retos son una forma de estimular a la comunidad a participar mediante la resolución de problemas que competen a las ciencias de la computación. En este caso particular, la implementación será en C/C++.

Los retos NO son una competencia, de serlo, la administración sería, obviamente, más rígida (en una competencia todos entregan sus códigos al mismo tiempo, por ejemplo).
Por lo cual, me parece redundante aclarar, que nadie viene aquí para demostrar nada o pelearse con el resto de los participantes.
Igualmente confío en el actuar responsable de la comunidad y espero que los retos se desarrollen con éxito y participación asidua, de modo que se transforme en un buen espacio para  compartir el hábito de la programación.



Los retos se desarrollarán de la siguiente manera:
-Se decidirán uno o dos problemas.
-Se crearán los hilos respectivos, los cuales serán puesto en chincheta por un mes, de modo que no haya ninguna ventaja (si alguno hubiese visto el mismo problema o problema similar con anterioridad). Y para que todos puedan hacerse un tiempo para participar, aún cuando estén muy atareados por el trabajo/estudio.
-Luego del mes el post se cerrará y quedarán las mediciones oficiales.
-Se creará otro post en chincheta que irá almacenando el historial de todos los retos que se cierren, de modo que no se pierdan aquellas resoluciones.



Los problemas serán todos de índole matemática. De ningún modo se exigirán conocimientos como APIs o demás que no estén en el estándar.
Con esto me refiero a que no serán retos al estilo de "programar un servidor", "hacer un rootkit", "hacer una interface gráfica", etc. Obviamente que puedo modificar el enunciado del problema para hacer una "historia" divertida, pero me aseguraré que con conocimientos muy básicos y un poco de lógica se puedan resolver. No necesito resolverlos, simplemente leyéndolos uno puede darse cuenta de como "pinta" el ejercicio, si es un problema matemático, o si se necesitan conocimientos avanzados que no son del estandar.

El hecho es que pongan sus esfuerzos en un programa que resuelva el problema de manera COMPLETA (que no haya casos sin cubrir), respetando los requerimientos de memoria explicitados en el enunciado y se deberá tratar de que sea los más óptimo posible en velocidad de resolución.

Además, cada código que se posteé tendrá que poseer una descripción de QUÉ es precisamente lo que hace (osea una explicación del algoritmo usado), de modo que se pruebe fehacientemente de que uno entiende lo que postea y además, contribuya a entender el método de resolución adoptado. Ya que, si bien es posible entender leyendo el código, ahorra mucho tiempo que se explique POR QUÉ se hace lo que se hace; especialmente en problemas que tienen una solución original, la cual es producto de todo un proceso matemático deductivo.
Si alguien usa una idea ya posteada, sólo con mencionarlo no necesita explicar otra cosa que la modificación añadida.

Yo, personalmente, me encargaré de las mediciones oficiales de los códigos, lo que no quiere decir que ustedes no puedan aportar sus propias mediciones. Del mismo modo, trataré de leer todos los algoritmos y códigos para asegurarme de que la solución sirve para todos los ingresos (para lo cual es importante que hagan la descripción de su algoritmo).

Además me ocuparé de buscar problemas. Mas cualquiera puede sugerir alguno, probablemente espere un poco para ponerlo como reto, de modo que nadie sugiera un problema que en realidad sea una tarea. Tengan en cuenta que probablemente, si participan en los retos frecuentemente haciendo buenos aportes se ganarán la confianza para que acepte los problemas que sugieran.
Es muy importante para que yo acepte poner un problema como reto, las fuentes. Ya que no sobra el listo que desea que se le haga la tarea (y de forma óptima! xD). Eso no es todo, ya que existen competiciones online y sería terrible que estuviesemos resolviendole los problemas a alguien. Yo también postearé las fuentes para que sea completamente transparente este tema tan delicado.



El incumplimiento de cualquier norma, tanto de la sección en general, como de las de normas particulares de los retos, podría acarrear a la eliminación del comentario sin aviso previo.



Problema #1:

Fuente: Es un problema que tenía en la computadora hace tiempo, y revisando (como siempre anoto las fuentes) descubrí que lo había sacado de éste foro.
El post de donde fue sacado es este: http://foro.elhacker.net/empty-t278773.0.html
Yo ya lo he resuelto, es un problema que tengo como ejemplo para explicarle a algunos chicos que a veces optimizar significa trabajar un poco el problema matemáticamente y abandonar la forma bruta de resolverlos. Además es original y fue uno de los primeros problemas de envergadura media con que me enfrenté.
En brevedad escanearé las hojas donde tengo la explicación (me gusta desarrollarlo a mano) y subiré el código que hice hace tiempo. No lo revisé, pero puede que sea factible hacerle optimizaciones.





Problema #2:
Trataremos el problema G del pdf que aquí adjunto (perdon por el hecho de que esté en inglés, si alguien no entiende avisa y lo traduzco).
http://cm.baylor.edu/ICPCWiki/attach/Problem%20Resources/1992WorldFinalProblemSet.pdf
Fuente: Exámen de la final del mundo de las competencias ACM de 1992 (organizadas por IBM) una olimpíada de programación universitaria internacionaldonde se valora el trabajo en grupo (se programa en grupos de a 3) para el diseño de soluciones óptimas a problemáticas de envergadura (siempre hablando de problemas de algoritmia) y donde también se valora la velocidad (se tiene 5 horas para realizar la prueba).





Este problema todavía no lo he tratado todavía pero probablemente lo haga, ya que estamos pensando en competir ahora q voy a la facu...


Suerte!

[Pirata LOL]

Aunque me parece buena idea lo de la competencia interna
veo esto mas como realizar la tarea   ((no dudo de ti)) PERO no participo sencillamente xq si lo que se quiere es practicar se hace solo con nuestros problemas(ejercicios) y de surgir dudas postearlas en el foro 

[N0body]

Yo te sugeriría ser un poco más observador y te invito a razonar un poco:
1)Las fuentes están en el post, ¿lo leíste?. Un problema ya lo resolvieron en el foro y por ende entra en la categoría de "nuestros problemas" ¿no?
2)El post está en chincheta y yo no soy administrador, eso implica que esto ha sido muy planeado con los admines, los cuales, seguramente tendrán criterio para ponerme en chincheta, de acuerdo a mi participación asidua (ahora no tanto) en esta sección.
3) Yo mismo dije que iba a poner mis resoluciones, ahora he estado un poquito ocupado, pero si quieres espera hasta que yo responda para confirmarlo. Espero poder escanear y subir las respuestas de al menos el primero para mañana...
4) Me tomé el trabajo de hacer las normas yo mismo, ¿haría tanto esfuerzo por una tarea?

Sé que aquí suelen haber personas que quieren la tarea hecha, yo mismo he prejuzgado a muchos. Pero antes me fijo:
a) La cantidad de mensajes.
b) La calidad de sus respuestas, usando el buscador.

Además, he creado este post porque los ejercicios que conmumente se proponen aquí no tienen el nievel y el estilo que tiene estos, admitiendo soluciones realmente originales, y no simplemente se limite la competencia a optimizar algo en un bucle, en una anidación, o convertir una recursividad en iteración.

[ghastlyX]

Como veo que la cosa está bastante parada, me tomo la libertad de poner mi análisis para el primer problema a ver si así se reactiva esto un poco, que lo considero una interesante idea. Pongo el texto en Latex a continuación:

Código [Seleccionar] Expandir

\documentclass[a4paper,article,10pt]{article}
\usepackage{geometry}
\ttfamily
\usepackage[dvips]{graphicx,psfrag,overpic,color}
\usepackage{latexsym}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{pstricks}
\usepackage[postscript]{ucs}
\usepackage[utf8]{inputenc}
\usepackage[spanish]{babel}
\usepackage{fancyhdr}
\usepackage{listings}
\geometry{margin=1.5cm}
\usepackage{fancyhdr}
\pagestyle{fancy}
\fancyhead{}
\fancyfoot{}
\rhead{\thepage}
\chead{Espirales - ghastlyX}
\rfoot{\thepage}

\newtheorem{teo}{{Teorema}}
\newtheorem{recu}{{Recurrencia}}
\newtheorem*{lema}{{Lema}}
\newtheorem*{coro}{{Corolario}}
\newenvironment{demo}[1][Demostración:]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{defi}[1][Definición]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{exemple}[1][Ejemplo]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{remark}[1][Remarca]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\renewcommand{\labelenumi}{(\alph{enumi})}

\begin{document}
\noindent Se va a proceder paso a paso en la resoluci\'on de este problema.
Dejando a un lado la soluci\'on por backtracking, puesto que es demasiado
ineficiente, se puede considerar una primera soluci\'on usando programaci\'on din\'amica.
Basta hacer un par de consideraciones para llegar a esta primera
soluci\'on. Sea $f(n, m)$ el n\'umero de espirales diferentes (sin tomar m\'odulo) en un tablero de $n\times m$.
\begin{lema}
Sean $n, m\in \mathbb{N}$ arbitrarios. Se cumple que $f(n, m) = f(m, n)$.
\end{lema}
\begin{demo}
Es evidente por simetr\'ia. $\blacksquare$
\end{demo}

\noindent Visto esto, dado un tablero de $n\times m$, las posibles espirales
son las que realizan una \textbf{L} y se acaban y las que despu\'es de realizarla
siguen avanzando. Esta \textbf{L} primero puede avanzar $n$ casillas y despu\'es
puede bajar hasta $m$ casillas, dando un total de $nm$ posibles \textbf{L}s.
Teniendo en cuenta que tras realizar la \textbf{L} vuelve a quedar un tablero de
$i\times j$, donde $i + 1 \leq n$ y $j + 1 \leq m$ son las dimensiones de
dicha \textbf{L}, se obtiene una primera recurrencia:

\begin{recu}
Sean $n, m\in \mathbb{N}$ arbitrarios. Se cumple que
$f(n, m) = nm + \sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{m}f(i, j)$.
\end{recu}
\noindent Con esta recurrencia se obtiene un primer c\'odigo, cuya complejidad es $O(n^2m^2)$:
\lstset{language=C++}
\begin{lstlisting}
#include <iostream>
#include <vector>
using namespace std;

const long long MOD = 1000000000;
long long M[1001][1001]; //Tabla para la dinamica

long long f(int n, int m) {
    if (M[n][m] == -1) { //Si no esta calculado
        //Si el simetrico esta calculado, se devuelve ese por el lema
        if (M[m][n] != -1) return M[n][m] = M[m][n];
        M[n][m] = n*m% MOD; //Espirales en forma de L sin continuar
        //Se suma el resto de espirales
        for (int i = 1; i <= n - 1; ++i)
            for (int j = 1; j <= m - 1; ++j)
                M[n][m] = (M[n][m] + f(i,j))%MOD;
    }
    return M[n][m];
}

int main() {
    int n, m;
    cin >> n >> m;
    //Inicializacion de la tabla a -1
    for (int i = 0; i <= 1000; ++i) for (int j = 0; j <= 1000; ++j) M[i][j] = -1;
    cout << f(n, m)%MOD << endl;
}
\end{lstlisting}
\noindent Esta recurrencia puede simplificarse, para as\'i eliminar uno de los
dos bucles de cada estado en la din\'amica. Si en lugar de considerar la
\textbf{L}, se avanza tan solo en la primera direcci\'on, se tienen $n$ posibles
espirales m\'as las que luego siguen creciendo en el tablero que queda, de
dimensiones $i\times (m - 1)$, donde $1 \leq i \leq n$ es lo que se avanza antes
de seguir. Con esto se obtiene la segunda recurrencia:
\begin{recu}
Sean $n, m\in \mathbb{N}$ arbitrarios. Se cumple que
$f(n, m) = n + \sum\limits_{i = 1}^{n}f(i, m - 1)$.
\end{recu}
\noindent Esta segunda recurrencia permite conseguir una complejidad de $O(n^2m)$.
El siguiente c\'odigo muestra como usarla adaptando el primer c\'odigo:
\lstset{language=C++}
\begin{lstlisting}
#include <iostream>
#include <vector>
using namespace std;

const long long MOD = 1000000000;
long long M[1001][1001];

long long f(int n, int m) {
    if (M[n][m] == -1) {
        if (m == 1) return M[n][m] = n;
        if (M[m][n] != -1) return M[n][m] = M[m][n];
        M[n][m] = n% MOD; //Posibles inicios de la L
        //Suma del resto de espirales
        for (int i = 1; i <= n; ++i)
            M[n][m] = (M[n][m] + f(i, m - 1))%MOD;
    }
    return M[n][m];
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i <= 1000; ++i) for (int j = 0; j <= 1000; ++j) M[i][j] = -1;
    cout << f(n, m)%MOD << endl;
}
\end{lstlisting}
\noindent Si bien este c\'odigo es bastante m\'as r\'apido que el primero,
se puede mejorar a\'un m\'as trabajando un poco m\'as la recurrencia. El siguiente
resultado muestra como poder hacerlo.
\begin{recu}
Sean $n, m\in \mathbb{N}$ arbitrarios. Se cumple que $f(n, m) = f(n - 1, m) + f(n, m - 1) + 1$.
\end{recu}
\begin{demo}
Queremos ver que $f(n, m) = f(n - 1, m) + f(n, m - 1) + 1$.
Aplicando la segunda recurrencia, se tiene que ser\'a cierto si y s\'olo si $n + \sum\limits_{i =
1}^{n}f(i, m - 1) = n - 1 + \sum\limits_{i = 1}^{n - 1}f(i, m - 1) + n + \sum\limits_{i = 1}^{n}f(i, m - 2 ) + 1$
es cierto. Simplificando esta segunda
expresi\'on queda $f(n, m - 1) = n + \sum\limits_{i = 1}^{n}f(i, m - 2)$,
que es cierta, puesto que es precisamente la segunda recurrencia vista
anteriormente. $\blacksquare$
\end{demo}
\noindent Por esta recurrencia y el lema se obtiene el \'ultimo resultado:
\begin{coro}
Sean $n, m\in \mathbb{N}$ arbitrarios. Se cumple que $f(n, m) = \binom{n+m}{m} - 1$.
\end{coro}
\noindent Por \'ultimo, el c\'odigo que utiliza este resultado:
\lstset{language=C++}
\begin{lstlisting}
#include <iostream>
using namespace std;

int M[2002][2002];
const int MOD = 1000000000;

int main() {
    int n, m;
    for (int i = 0; i < 2002; ++i) M[i][0] = M[i][i] = 1;
    for (int i = 2; i < 2002; ++i)
        for (int j = 1; j < i; ++j) 
            M[i][j] = (M[i - 1][j - 1] + M[i - 1][j])%MOD;
    cin >> n >> m;
    cout << (M[n + m][m] + MOD - 1)%MOD << endl;
}
\end{lstlisting}
A continuaci\'on se puede ver una comparativa de los diferentes c\'odigos con diferentes entradas:\\\\
\begin{tabular}{|c|c|c|c|c|}
\hline
& $n=m=100$ & $n=m=500$ & $n=m=750$& $n=m=1000$ \\
\hline
C\'odigo 1 & 0m0.288s & 2m31.501s & 12m44.252s & No realizado\\
\hline
C\'odigo 2 & 0m0.012s & 0m0.492s & 0m1.688s & 0m4.280s \\
\hline
C\'odigo 3 & 0m0.032s & 0m0.032s & 0m0.032s & 0m0.032s\\
\hline
\end{tabular}
\end{document}

[N0body]

Miles de millones de disculpas, últimamente estuve ocupadísimo y me olvidé de ésto!!

Tengo el escaner roto y la explicación a mano (soy de los viejos, vieron?). Así que momentanemente y viendo lo muerto que está esto, posteo mi código sin la explicación. No creo que se entienda sin la misma. No sé si está bien, no he comparado con el ya posteado. Desde ya que usa mucha menos memoria y menos tiempo (eso se ve a simple vista).

Código (C) [Seleccionar] Expandir


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

int main(int argc, char *argv[])
{
  int n, m, i;
  long long  a, b;
  long long c=1000000000;
  scanf ("%i", &n);
  scanf ("%i", &m);
  if (n>m)
     {
          i=m;
          m=n;
          n=i;
     }
  for (a=1,i=0;   
      i<n;
      i++)
      {
           a*=(m+i);
           a/=(i+1);
           while (a>c) a-=c;
      }
  a--;
  for (b=1,i=0;
       i<n-1;
       i++)
       {
           b*=(m+1+i);
           b/=(i+1);
           while (b>c) b-=c;
       }
  a=a+b;
      printf ("%d", a);
 
  system("PAUSE");
  return 0;
}




Existen foros que te interpretan LaTex (creo que consultan paginas externas). Esto está genial, porque si no puedo escanear la solución lo más idóneo sería pasarla a LaTex, porque está llena de simbología...

Vuelvo a disculparme por haberme olvidado de ésto
Saludos y preocuraré darme una vuelta de forma frecuente de aquí en adelante!

[ghastlyX]

Tu solución parece que es incorrecta. La he probado y comparado con las tres mías y para casos pequeños dan lo mismo, pero a poco que los números empiezan a ser grandes falla y las mías coinciden.

El problema creo que es que no aplicas correctamente el módulo. Si he entendido tu solución, cada vez que te pasas del módulo restas hasta compensarlo (o lo que sería equivalente, haces % c). Esto sería correcto si no hubiera divisiones de por medio, pero al haber divisiones falla. No puedes dividir y hacer módulo a la vez, puesto que no es lo mismo. Lo correcto sería en lugar de dividir, multiplicar por el inverso del divisor módulo 1000000000, pero no es primo, de forma que no todos los divisores serán coprimos con él, de forma que no puedes solucionar el problema así...

Si miras mi solución, al final acabo calculando (n +m sobre m) - 1 mod 1000000000, pero para realizarlo, en lugar de usar la típica fórmula con factoriales (que implica divisiones) uso la recurrencia lineal que solo tiene sumas, que no dan problemas con el módulo, haciendo pasar una solución que matemáticamente es lineal a ser cuadrática con memoria cuadrática también.