Yo intente resolverlo, segun creo mi programa lo resuelve, pero no el tiempo indicado.
C | Consistent Verdicts |
In a 2D plane N persons are standing and each of them has a gun in his hand. The plane is so big that the persons can be considered as points and their locations are given as Cartesian coordinates. Each of the N persons fire the gun in his hand exactly once and no two of them fire at the same or similar time (the sound of two gun shots are never heard at the same time by anyone so no sound is missed due to concurrency). The hearing ability of all these persons is exactly same. That means if one person can hear a sound at distance R1, so can every other person and if one person cannot hear a sound at distance R2 the other N-1 persons cannot hear a sound at distance R2 as well.
The N persons are numbered from 1 to N. After all the guns are fired, all of them are asked how many gun shots they have heard (not including their own shot) and they give their verdict. It is not possible for you to determine whether their verdicts are true but it is possible for you to judge if their verdicts are consistent. For example, look at the figure above. There are five persons and their coordinates are (1, 2), (3, 1), (5, 1), (6, 3) and (1, 5) and they are numbered as 1, 2, 3, 4 and 5 respectively. After all five of them have shot their guns, you ask them how many shots each of them have heard. Now if there response is 1, 1, 1, 2 and 1 respectively then you can represent it as (1, 1, 1, 2, 1). But this is an inconsistent verdict because if person 4 hears 2 shots then he must have heard the shot fired by person 2, then obviously person 2 must have heard the shot fired by person 1, 3 and 4 (person 1 and 3 are nearer to person 2 than person 4). But their opinions show that Person 2 says that he has heard only 1 shot. On the other hand (1, 2, 2, 1, 0) is a consistent verdict for this scenario so is (2, 2, 2, 1, 1). In this scenario (5, 5, 5, 4, 4) is not a consistent verdict because a person can hear at most 4 shots.
Given the locations of N persons, your job is to find the total number of different consistent verdicts for that scenario. Two verdicts are different if opinion of at least one person is different.
Input
The first line of input will contain T (≤ 550) denoting the number of cases.
Each case starts with a line containing a positive integer N. Each of the next N lines contains two integers xi yi (0 ≤ xi, yi ≤ 30000) denoting a co-ordinate of a person. Assume that all the co-ordinates are distinct.
1) For 10 cases, N = 1000.
2) For 15 cases, 100 ≤ N < 1000.
3) For others, N < 100.
Output
For each case, print the case number and the total number of different consistent verdicts for the given scenario.
Sample Input | Output for Sample Input |
231 12 24 421 15 5 | Case 1: 4Case 2: 2 |
Lo importante del problema es revisar la cantidad de distancias distintas entre 2 personas.
ResponderEliminarA alguien se le ocurre como hacerlo eficiente?
include
long t,n, x[1001],y[1001],r,i,j,k,z,m,s,e;
long long a[500000];
int main(){
scanf("%long",&t);
for(j=1;j<t+1;j++){
scanf("%ld",&n);
for(k=1;k<n+1;k++)
scanf("%ld %ld",&x[k],&y[k]);
for(i=1;i<n;i++){
for(m=i+1;m<n+1;m++){
z=x[i]*x[i]+y[i]*y[i]+x[m]*x[m]+y[m]*y[m]-2*x[i]*x[m]-2*y[i]*y[m];
for(e=0;e<500000;e++){
if(z==a[e])
s=1;
}
if(s==0){
a[r]=z;
r=r+1;
}
s=0;
}
}
r=r+1;
printf("Case %ld: %ld",j,r);
for(k=1;k<n+1;k++){
x[k]=0;
y[k]=0;
}
for(k=0;k<r;k++)
a[k]=0;
r=0;
}
}
Jejeje... Hay varias formas de hacerlo de forma que sea un poco más eficiente. Yo pensaría en guardar todas las distancias (distintas o no), ordenarlas con un algoritmo que corra en nlogn (como una ordenación por mezcla o usando montículos) e ir recorriendo la lista con un contador que se incremente en 1 con cada distancia diferente que encuentre. Hay otras formas de abordarlo pero creo que esa es de las más sencillas. ¿Todavía es posible enviar el código para que se evalúe? El problema era de un concurso de bastante nivel.
ResponderEliminarEl problema sí sigue evaluándose. Por lo que veo todos los problemas de concursos llevados a cabo en la página de la UVA Online Judge son después colocados en los problemas de la carpeta Contest Volumes. Este problema es el número 12435. Así que pues hay que resolverlo, publiquen sus avances, dudas, comentarios o lo que se les ocurra.
ResponderEliminarPor más que intenté resolverlo usando una ordenación por mezcla siguió marcándome tiempo límite excedido... Incluso implementé la optimización sugeridad por José Luis de ordenar por inserción los subgrupos de números con un número pequeño de elementos, pero ni así funcionó. Después probé usando la función sort de la librería algorithm, que básicamente es una versión extraordinariamente optimizada del algoritmo Quicksort (que normalmente es en promedio más lento que un merge sort), y pues el resultado me sorprendió, ya que así sí corrió en tiempo. Creo que no he explicado en el curso como usar esa función, espero hacerlo el próximo sábado. El código es el siguiente:
ResponderEliminar#include
#include
using namespace std;
long a[500002],j,k,m,n,h,t,c,p[2][1002],dx,dy,z;
int main(){
scanf("%ld",&t);
for(z=1;z<=t;z++){
scanf("%ld",&n);
for(j=1;j<=n;j++)
scanf("%ld %ld",&p[0][j],&p[1][j]);
for(j=1,k=0;j0){
h=a[j];
while(a[j]==h)
j=j+1;
dx=dx+1;
}
printf("Case %ld: %ld\n",z,dx);
}
}
Tras haberlo hecho así me percaté de que un conocido lo había resuelto con un mejor tiempo y sin usar la librería. Esto lo sé porque en las estadísticas del problema veo que lo hizo en ANSI C (es decir sin librerías de C++ como es la algorithm). Quizá el envíe un correo preguntándole cómo le hizo... Su nombre es Rodrígo Burgos, ¿recuerdan que una vez les mostré su blog?
Tras pensarle un buen rato y tras más de 30 envíos pude optimizar mi código para que fuera más rápido que el de Rodrigo, pero yo lo sigo haciendo con la ayuda de la librería algorithm. ¿Qué ideas tendrían para mejorar el tiempo?
Parece que el código no se pegó bien... Lo intentaré de nuevo:
ResponderEliminar#include<stdio.h>
#include<algorithm>
using namespace std;
long a[500002],j,k,m,n,h,t,c,p[2][1002],dx,dy,z;
int main(){
scanf("%ld",&t);
for(z=1;z<=t;z++){
scanf("%ld",&n);
for(j=1;j<=n;j++)
scanf("%ld %ld",&p[0][j],&p[1][j]);
for(j=1,k=0;j<n;j=j+1)
for(h=j+1;h<=n;h=h+1,k=k+1){
dx=p[0][j]-p[0][h];
dy=p[1][j]-p[1][h];
a[k]=dx*dx+dy*dy;
}
sort(a,a+k);
a[k]=0;
dx=1;
j=0;
h=1;
while(a[j]>0){
h=a[j];
while(a[j]==h)
j=j+1;
dx=dx+1;
}
printf("Case %ld: %ld\n",z,dx);
}
}