TAP2013G

WAR

Link to the question: TAP2013G

HOW TO SOLVE:

I have solved the question just by modification of the brute force. That is I sorted both the arrays and then performed a binary search to find the largest number q[i] which is smaller than s[i]. 

Just think simple as it requires simple mathematics.

SOURCE CODE:

/* War - (TAP2013G) */
/* Sushant Gupta */

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int f=0;
int bin(long long int d, int s, long long int *array) {
      int  l, m, found;
       l = s - 1; found = 0;
      while (f <= l) {
            m = (f + l) / 2;
            if (d <= array[m]) {

                      l = m - 1;
            }

                    else if (d > array[m]) {
                           found = 1;

                           f++;
                            break;
                    };
      }
      if (found)
       return 1;
      else return 2;
}

int main()
{
    int n,i,c=0,k;
    scanf("%d",&n);
    long long int q[n],s[n];
    for(i=0;i<n;i++)
        scanf("%lld",&q[i]);
    for(i=0;i<n;i++)
        scanf("%lld",&s[i]);
    sort(q,q+n);
    sort(s,s+n);

    for(i=0;i<n;i++)
    {

        k= bin(s[i],n,q);
        if(k==1)
            c++;
    }
    printf("%d",c);
    return 0;
}