RANJANA QUIZ - APOC2_01 - EDITORIAL
PROBLEM LINK
Author: codechefsrm
Editorialist : codechefsrm
PREREQUISTIES
SORTING ,2D MATRIX MANIPULATION,QUICK SORT
EXPLANATION
Prof. Ranjana decided to conduct a quiz in her class. She divided all the students of her class into groups of three. Consider that no student was left out after the division. She gave different sets of questions to every group. A set is said to be unique if there is no other team that received the same number of maths, science and english questions. In every set, maximum questions for each group were related to maths, then science, and the least number of questions were related to English. Total number of questions given to each team can be different.
After the test, the CR of the class asked every team to report the number of questions they got on each subject. The CR wants to know the number of unique sets of questions that were given to the teams, the problem is that all the students have just submitted the number of questions of each subject but in no particular order. Help the CR to find the number of unique sets
SOLUTION
Setter's Solution
#include<stdio.h>
void swap(long long int *a, long long int *b)
{
long long int t; t=*a;
*a=*b;
*b=t;
}
void qsort(long long int items[][4], long long int left, long long int right)
{
register long long int i,j,k; long long int x, y;
i = left; j = right;
x = items[(left+right)/2][3]; do
{
while((items[i][3] < x) && (i < right)) i++;
while((x < items[j][3]) && (j > left)) j--;
if(i <= j)
{
y = items[i][0];items[i][0] = items[j][0];items[j][0] = y;
y = items[i][1];items[i][1] = items[j][1];items[j][1] = y;
y = items[i][2];items[i][2] = items[j][2];items[j][2] = y;
y = items[i][3];items[i][3] = items[j][3];items[j][3] = y; i++;
j--;
}
} while(i <= j);
if(left < j)
qsort(items, left, j); if(i < right)
qsort(items, i, right);
}
int main()
{
long long int i,k,j,n,z,g,count=0; long long int p,q,r;
long long int arr[100000][4]={0}; scanf("%lld",&n); for(i=0;i<n;i++)
{
scanf("%lld %lld %lld",&arr[i][0],&arr[i][1],&arr[i][2]);
arr[i][3]=arr[i][0]+arr[i][1]+arr[i][2];
if (arr[i][0] > arr[i][1]) swap(&arr[i][0],&arr[i][1]);
if (arr[i][1] > arr[i][2]) swap(&arr[i][1],&arr[i][2]);
if (arr[i][0] > arr[i][1]) swap(&arr[i][0],&arr[i][1]);
}
qsort(arr,0,n-1);
i=0;
while(1)
{
p=arr[i][0];
q=arr[i][1];
r=arr[i][2];
k=arr[i][3]; j=i;
z=0;
if(p==0)
{
++i;
if(i==n)
break;
else continue;
}
while(arr[++i][3]==k && i<n)
{
if(arr[i][0]!=0 && arr[i][0]==p && arr[i][1]==q && arr[i][2]==r)
{
arr[i][0]=0;
z++;
}
}
if(z!=i-1-j && z>=1)
{
i=j+1; continue;
}
else if(z==0)
{
count++; if(i!=j+1)
{
i=j+1; continue;
}
}
if(i==n) break;
}
printf("%lld",count); return 0;
}