# UVA 10474 - “Where is the marble?” time limit

I have a problem from UVA online judge here. 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 a time error. I don't know any faster way of searching on an array other than binary search.

#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. – Martin York 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

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;
}


As @cat_baxter points out, you are re-sorting the marbles before every query. You should do it once per test case.

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()?