# UVA 10474 - Where is the Marble Timelimit

I got a problem from UVA online judge Problem link. I have read it tons of times and as they said, I have to get the answer really fast.

I have used a binary search and STD::Sort, but I am still having time error. I don't know any faster way to search on an array than binary search.

PS:I am not an english speaker, sorry for my english.

``````#include <stdio.h>
#include <string>
#include <algorithm>

int n,q,vec[100000];
int inicio,final,medio,busca;
int cont;
int busquedabinaria()
{

//busqueda binaria
std::sort(vec,vec+n);
inicio=0;
final=n-1;
medio=(inicio+final)/2;

while(inicio<=final)
{
if(vec[inicio]==busca)
return inicio;
if(vec[medio]==busca)
return medio;
if(vec[final]==busca)
return final;
medio = (inicio + final) / 2;
if (vec[medio] > busca)
final = medio - 1;
else if (vec[medio] < busca)
inicio = medio + 1;
// found

}
return -1;

}

int main()
{

freopen("in.txt", "rt",stdin);
freopen("out.txt", "wt",stdout);

while (scanf("%d %d\n",&n,&q)!=EOF && (n!=0 || q!=0)    )
{
for (int i=0;i<n;i++)
{
scanf("%d\n",&vec[i]);

}
printf("CASE# %d:\n",cont+1);
cont++;
while(q--)
{

scanf("%d\n",&busca);

int res=busquedabinaria();
if(res!=-1)
{
while (vec[res-1]==busca && res>0)
{
res--;
}
printf("%d found at %d\n",busca,res+1);

}
else

}

}

return 0;
}
``````
-
I know that in UVa OJ, your program should read from standard input and write to standard output. You are reading from "in.txt" so no input is provided to your program and it hangs till getting TLE. –  saeedn Sep 30 '12 at 13:32
Yes, but thats just for debbuging, when you submit it you should erease it –  Giuseppe Sep 30 '12 at 17:02
The problem is you have applied a brute force technique to the problem. The quickest solution would be to work out a formula that allows you to calculate the count of each number. When Your input is `1 9999999` this technique will be infinitely quicker than a brute force approach. –  Loki Astari Oct 1 '12 at 15:58
Do you want this code analysed as C++? Also, English identifiers would help. –  Anton Golov Oct 2 '12 at 7:15
I'm confused-- is this meant to be a C program or a C++ program? –  Jamal Jul 24 at 12:05

Sorry for the delayed answer - your solution is slow because it performs the sorting before every binary search! Just move the sorting to the line above the

printf("CASE# %d:\n",cont+1);

and you'll see the difference :)

I also add my solution just to see what's possible to optimize (it uses custom int reader, without sort and the binary search):

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define SIZE 16*1024
#define N    10001
static unsigned int values[N];
static int  buffer_size = 0;
static int  buffer_pos  = -1;
static char buffer[SIZE];

{
unsigned int value  = 0;
unsigned int digits = 0;
char b;

if (buffer_pos == -1)
{
buffer_size = fread(buffer, 1, SIZE, stdin);
buffer_pos  = 0;
}

while(buffer_size > 0)
{

if (buffer_pos == buffer_size)
{
buffer_size = fread(buffer, 1, SIZE, stdin);
buffer_pos = 0;
}

while(buffer_pos < buffer_size)
{
b = buffer[buffer_pos++];
if (b == '\n' || b == ' ')
{
return value;
}
else
{
value = value*10 + (b - '0');
digits++;
}
}
}
return value;
}

int main(int argc, char **argv)
{
long time = clock();

char buffer[8192];
setvbuf(stdout, buffer, _IOFBF, sizeof(buffer));
unsigned int  n, q, num, max, min, c = 0;

while(1)
{
c++;

if(n==0 && q==0) break;

max = 0;
min = N;
memset(values, 0, N * sizeof(unsigned int));

for(unsigned int i=0; i<n; i++)
{
values[num]++;
if(num > max) max = num;
if(num < min) min = num;
}

unsigned int pos = 1, temp;
for(unsigned int i=min; i <= max; i++)
{
if(values[i] !=0){
temp = values[i];
values[i] = pos;
pos += temp;
}

}

printf("CASE# %d:\n", c);
unsigned qval;
for(unsigned int i=0; i<q; i++)
{
int ret = values[qval];
if(ret == 0)
else
printf("%d found at %d\n", qval, ret);
}
}
//printf("Time (ms): %ld\n", clock()-time);
return 0;
}
``````
-
Your `busquedabinaria()` uses global variables everywhere. Pass the parameters properly — there's no excuse for that kind of sloppiness.
If you're going to use `std::sort()`, why not also use `std::binary_search()`?