Asuntos Oficiales > Retos
La Carrera
Binary:
Sinceramente, creo que las ordenaciones no son la respuesta. Ademas, siendo dos for anidados, la velocidad no podria mejorar drasticamente.
Si te fijas bien, hay un for que no varia... es el de por todos los autos, luego debemos responder de la forma mas rapida posible ( lg(n)) o similar, "cuantos autos hasta los analizados tienen una velocidad mayor que el que estamos calculando ahora".
Esto es porque recorremos los autos por posicion inicial, y el que estamos analizando esta mas adelante que todos los analizados hasta ahora, por eso, solo nos interesa: de los analizados hasta ahora, cuantos superan la velocidad de este.
Hay una estructura que permite responder a esta pregunta en lg(N) y modificar los datos para cada proximo auto en lg(n) tambien... asi que para cada auto tendriamos 2*lg(V), (v = posibles velocidades), lo que nos da una complijidad de N*2*lg(V) o O(N*lgN)
Saludos...
Enko:
La escuela me ha lavado el cerebro. Trate de solucionar el reto jugando el V Rally :unsure: (se nota que ya no se que hacer).
Traté hacer algo el sabado pero no me salió. Se me vienen como 5 examenes en la semana que viene así que no tendré tiempo para programar(la solucioón debe ser corta, pero no tengo práctica en algoritmos maniosos y se me complica). Además estaba aprendiendo algo de programación gráfica mientras desarollaba una pobre librería de este tipo y todo tendrá que ser suspendido por los examenes.
Resumiendo: ME RINDO. :adios:
Binary:
Ya... posteo la solucion:
Antes que nada... tenemos 1M diferentes velocidades. Asi tambien tenemos 1M autos, cada uno, caracterizado por su velocidad y su posicion inicial del pto de partida.
Asi, para cada auto tenemos:
struct Car {
int pos, speed;
};
Ademas, los autos vienen en orden de pos... mas precisamente... los autos mas cerca, primeros.
Definiremos adelantamiento como la situacion en la que un auto "x" esta mas cerca de la partida que otro auto "y", y el auto x tiene mayor velocidad...
Asi... if(c[x].pos < c[y].pos && c[x].speed > c[y].speed) tenemos adelantamiento
Para facilitar las cosas, y hacerlas mas rapidas, haremos lo siguente...
Tendremos un array de velocidades, en el que guardaremos la cantidad de autos que tienen dicha velocidad, asi:
v[x] seria la cantidad de autos con velocidad x
Ahora:
vamos recorriendo los autos uno por uno (del mas cercano al mas lejano).
Para cada auto, haremos lo siguente.... veremos cuantos autos con velocidad mayor a la suya hay en v[]... (en v tenemos solo autos que ya han sido procesados, o sea, estan mas cerca de la partida que el dicho)
luego, la suma de estos autos, la sumamos a "ans", representanto la cantidad de adelantamientos realizados pos los autos en v, al auto que estamos procesando.
Asi...
for(i = 0; i < N; i++)
for(j = c.speed + 1; j < MAX_SPEED; j++)
ans += v[j];
hasta aqui seria la solucion de N^2, que tomaria horas al PC para resolver...
Altiro posteo la optimizada....
Binary:
Ahora... lo que vamos a optimizar es la rapidez con la que guardaremos los autos en v[]....
Tanto la entrada, como al sacar, lo realizaremos en tiempo lg(N), gracias a la estructura de datos, conocida como index_tree...
(por favor, buscar en google para los que no la sepan)...
esta permite almacenar datos en array en tiempo lg(n) y preguntar en tiempo lg(n)... cuantos datos hay en v[1..n]... asi... al preguntar para v[1...MAXSPEED] - v[1..c.speed]... tenemos la cantidad buscada....
Ahora escribire el codigo...
Binary:
--- Código: Text --- // Race#include <stdio.h>#define MAXV 1000001#define LOW_BIT(x) ((((x) - 1) ^ (x)) & (x)) int v[MAXV]; int query(int pos){ int i, r = 0; for(i = pos; i > 0; i -= LOW_BIT(i)) r += v[i]; return r;} void update(int pos, int val){ int i; for(i = pos; i < MAXV; i += LOW_BIT(i)) v[i] += val;} int main(){ int n, i, ans, pos, speed; FILE *fin, *fout; fin = fopen("race.in", "r"); fout = fopen("race.out", "w"); ans = 0; fscanf(fin, "%d", &n); for(i = 0; i < n; i++) { fscanf(fin, "%d %d", &pos, &speed); ans += query(MAXV-1) - query(speed); update(speed, 1); } fprintf(fout, "%d\n", ans); fclose(fin); fclose(fout); return 0;}
Navegación
[*] Página Anterior
Ir a la versión completa