UVA 10474 - "Where is the marble?" time limit

Question

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.

Any feedback please?

#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 
                printf("%d not found\n",busca);

        }

    }

    return 0;
}

Answer 1

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 readInt()
{
    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++;
        n = readInt();
        q = readInt();

        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++)
        {
            num = readInt();
            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++)
        {
            qval = readInt();
            int ret = values[qval];
            if(ret == 0) 
                printf("%d not found\n", qval);
            else 
                printf("%d found at %d\n", qval, ret);
        }
    }
    //printf("Time (ms): %ld\n", clock()-time);
    return 0;
}

Answer 2

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