Other

The recent experience with acm icpc 2012. The questions were comparatively easier this time, but giving importance to the complexity. we attended 3 questions of which first one was right and rest two had time limit complexity issues. I am looking forward for the help from my reader's to correct my complexity issue.Here are the problem sets :-

Problem A: Pair socks

You have N socks in your cupboard. The color of each sock can either be red, green, blue, or white. Can you form complete pairs from these socks?

Input (STDIN):

The first line contains the number of test cases T. The next T lines contain a string c having N characters. The ith character of the string is either 'R', 'G', 'B' or 'W', denoting that the ith sock has color red, green, blue, or white respectively. There is no blank line between test cases.

Output (STDOUT):

For each test case, output "YES" if all socks can be grouped in pairs, or "NO" otherwise.

Constraints:

1 <= T <= 1000
The string c contains at most 50 characters.
Each character of c is either 'R', 'G', 'B' or 'W'.

Sample Input:

2
RGGGRG
RGBGRW

Sample Output:

YES
NO

Explanation:

For the first test case, RGGGRG implies that you have 2 red and 4 green socks, with which we can form 1 pair of red and 2 pairs of green socks.
For the second test case, RGBR implies that we have 2 red, 1 green and 1 blue socks. With this, we can form 1 pair of red socks, but we will then be left with 1 green and 1 blue socks which can't be used to form a pair.

Time limit : 1s

Memory limit : 32MB

 

Solution

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
using namespace std;
int main()
{
    int n,i=0,count[4],l,j=0,flag;
   
    char str[51];
    cin>>n;  
    i = 0;
    while(i<n)
    {
            memset(str,' ',51);
            j=0;
            while(j<4)
            {
                    count[j] = 0;
                    j++;
            }
                cin>>str;
                l = strlen(str);
                j=0;
                while(j<l)
                {
                        if(str[j] == 'R')
                        {
                                count[0]++; 
                               
                        }
                        if(str[j] == 'G')
                        {
                                count[1]++;      
                        }
                        if(str[j] == 'B')
                        {
                                count[2]++;      
                        }
                        if(str[j] == 'W')
                        {
                                count[3]++;      
                        }
                        j++;
                }
                j=0;
                flag = 0;
                while(j<4)
                {
                        if(count[j] % 2 != 0)
                        {
                                flag = 1;
                                cout<<"NO"<<endl;
                                break;
                        }
                        j++;
                }
                if(flag == 0)
                {
                        cout<<"YES"<<endl;
                }
        i++;
    }


    return 0;
}

Problem B: Sticks

You have N sticks - the length of the ith stick being L[i]. You also have M 3-dimensional boxes - the length, breadth and height of the jth box being A[j], B[j] and C[j]. What is the maximum number of sticks which can fit in the boxes? A stick can be fit in a box if it can be placed within it without bending or cutting it. A box can hold any number of fitting sicks (assume that the sticks do not intersect each other).

Input (STDIN):

The first line contains the number of test cases T. T test cases follow.
For each test case, the first line contains integers N and M on the first line. The next N lines contain the lengths of each stick, and the M lines after that contain the dimensions of each box denoted by 3 space-separated integers.
There is a blank line after each test case.

Output (STDOUT):

For each test case, output a single integer which is the number of sticks which can fit in the boxes.

Constraints:

1 <= T <= 10
1 <= N <= 50,000
1 <= M <= 50,000
1 <= L[i] <= 100,000
1 <= A[i],B[i],C[i] <= 30,000

Sample Input:

2
4 2
1
8
4
2
1 2 2
2 3 2

1 1
12
6 8 9

Sample Output:

3
1

Explanation:

For the first test case, the sticks of length 1 and 2 can fit in either of the 2 boxes, while the stick of length 4 can only fit in the second box.
For the second test case, the stick of length 12 can fix in the box of dimensions 6 X 8 X 9.

Time limit : 1s

Memory limit : 32MB

Solution

//Here the complexity is too high, its of order O(n^3)

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
using namespace std;
void merge(long long int [],int ,long long int ,long long int );
void part(long long int [],long long int ,long long int );
void part(long long int arr[],long long int min,long long int max)
{
 int mid;
 if(min<max)
 {
   mid=(min+max)/2;
   part(arr,min,mid);
   part(arr,mid+1,max);
   merge(arr,min,mid,max);
 }
}


void merge(long long int arr[],long long int min,long long int mid,long long int max)
{
  int tmp[30];
  int i,j,k,m;
  j=min;
  m=mid+1;
  for(i=min; j<=mid && m<=max ; i++)
  {
     if(arr[j] >= arr[m])
     {
         tmp[i]=arr[j];
         j++;
     }
     else
     {
         tmp[i]=arr[m];
         m++;
     }
  }
  if(j>mid)
  {
     for(k=m; k<=max; k++)
     {
         tmp[i]=arr[k];
         i++;
     }
  }
  else
  {
     for(k=j; k<=mid; k++)
     {
        tmp[i]=arr[k];
        i++;
     }
  }
  for(k=min; k<=max; k++)
     arr[k]=tmp[k];
}


int main()
{
        int flag = 0;
    long long int n,i=0,ns,nb,j=0,ln[50000],br[50000],ht[50000],k=0,count,sql,sqb,sqh,d[50000];
    long long int len[50000];
    char ch;
    cin>>n;
    i=0;  
    while(i < n)
    {
                cin>>ns>>nb;
                j=0;
                while(j < ns)
                {
                        cin>>len[j];
                        j++;
                }
              
                part(len,0,ns-1);
                j=0;
                while(j < nb)
                {
                       cin>>ln[j]>>br[j]>>ht[j];
                        sql = ln[j] * ln[j];
                        sqb = br[j] * br[j];
                        sqh = ht[j] * ht[j];
                        d[j] = (sql+sqb+sqh);       
                        j++;
                }
               
                j=0;
                count = 0;
                while(j < ns)
                {
                        k=0;
                        flag = 0;
                        while(k < nb)
                        {
                               if(len[j] <= sqrt(d[k]))
                               {
                                       count += ns - j;
                                       flag = 1;
                                       break;
                               }
                                k++;
                        }
                        if(flag == 1)
                        {
                                break;
                        }
                       
                        j++;
               
                } 
                cout<<count<<endl;   
                cin>>ch;             
        i++;
    }

    return 0;
}

Problem C: Sum Range

You are given N numbers a[1..N] and 2 other integers L and H. Count the number of tuples (i,j,k) satisfying i < j < k and L <= a[i] + a[j] + a[k] <= H.

Input (STDIN):

The first line contains the number of test cases T. T test cases follow.
The first line of each test case contains the numbers N, L and H. The next line contains N space-separated integers a[1]..a[N].
There is no blank line between test cases.

Output (STDOUT):

Output T lines, each containing the answer for the corresponding test case.

Constraints:

1 <= T <= 100
1 <= N <= 1000
1 <= L <= H <= 1000000
1 <= a[i] <= 1000000

Sample Input:

2
4 11 14
1 2 4 8
5 5 10
3 4 1 1 4

Sample Output:

3
9

Explanation:

For the first test case, the triplets of indices (1, 2, 4), (1, 3, 4) and (2, 3, 4) have their corresponding sums as 11, 13 and 14, which fall in the desired range.

Time limit : 5s

Memory limit : 32MB

Solution

//Here the complexity is too high, its of order O(n^3)

 #include<stdio.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<iostream>
using namespace std;
struct data
{
        long long int sum;
        long long int first;
        long long int second;

};

int main()
{
        long long int i=0,t,n,j,l1,l2,l3,sumt,count,ind;
        long long int L,R,arr[1000];
        vector<data> d(1000000);
        cin>>t;
        while(i<t)
        {
                cin>>n>>L>>R;
             
                j=0;
                while(j<n)
                {
                        cin>>arr[j];
                        j++;
                      
                }
                j=0;
                ind = 0;
                l1 =0;
                while(l1<n)
                {
                        l2=0;
                        while(l2<n)
                        {
                                if(l1 != l2)
                                {
                                        d[ind].sum = arr[l1]+arr[l2];
                                        d[ind].first = l1;
                                        d[ind].second = l2;
                                        ind++;                                
                                }
                                l2++;
                      
                        }
                        l1++;
                }
          
                l1=0;
                 count =0;
                while(l1 < ind)
                {
                        l2 = 0;
                        while(l2 < n)
                        {
                                if((d[l1].first != l2) && (d[l1].second != l2))
                                {
                                        sumt = d[l1].sum + arr[l2];
                                        if(sumt >= L && sumt <= R)
                                        {
                                            count++;
                                        
                                        }
                                }
                                l2++;
                        }
              
              
                        l1++;
                }
        count /= 6;
       cout<<count<<endl;    
              i++;
        }
    return 0;
}