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

int array[1000000];

int array2[1000000];

int binary_search(int a[], int low, int high, int target) {

while (low <= high) {

int middle = low + (high - low)/2;

if (target < a[middle])

high = middle - 1;

else if (target > a[middle])

low = middle + 1;

else

return middle;

}

return -1;

}

int main()

{

int a = 1, b = 1;

scanf("%d %d", &a, &b);

while(a != 0 && b != 0)

{

int count = 0;

int i = 0;

for(i = 0; i < a; ++i)

{

int temp;

scanf("%d", &temp);

array[i] = temp;

}

for(i = 0; i < b; ++i)

{

int temp;

scanf("%d", &temp);

int found = binary_search(array, 0, a - 1, temp);

if(array[found] == temp)

++count;

}

printf("%d\n", count);

count = 0;

scanf("%d %d", &a, &b);

}

return 0;

}

## Friday, October 28, 2011

### Too Slow - 11849 CD

So I was writing a program today to solve this problem. First I had some issues compiling because my arrays were too big. It seems that if you allocate them within the main function it takes up stack space where as initializing them as global variables takes up heap space. Good to know! The first five times I submitted I got a response of time limit exceeded. I did some minor things the first two times to break out of a loop if I had incremented my counter and if the CD number of Jack's was bigger than Jill's because all CDs were in order. This helped a little bit and then I remembered reading an article on competitive coding tips that suggested using scanf/printf functions instead of cin/cout. This dramatically improved my time, but was still getting rejected for exceeding the limit. I tried a couple other minor tweaks that improved my timing and finally decided a linear search was just too slow to work. Went to a binary search and submitted which gave me a response of ACCEPTED. :)

Subscribe to:
Post Comments (Atom)

## No comments:

## Post a Comment