# ENTEXAM - Editorial

Author: Sergey Kulik
Testers: Vasya Antoniuk and Kevin Atienza
Translators: Vasya Antoniuk (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza

Simple

Loops

### PROBLEM:

N students will take E exams. All the students with score strictly greater than at least (N-K) students’ total score pass. Each exam’s score is an integer between 0 and M, inclusive.

They have already taken E-1 exams. Sergey is the N th person. Given that he knows the results of the other N-1 students in the remaining exam, what is the minimum score he must have to pass? (or determine if it is impossible to pass.)

### QUICK EXPLANATION:

• Find all total scores of the first N-1 students, and sort them in increasing order. Let the (N-K)'th smallest total be x.
• Let y be the total score Sergey in the first E-1 exams.
• Then Sergey needs at least \max(0, x - y + 1) points. If this exceeds M, then the answer is `Impossible`.

### EXPLANATION:

Sergey passes if and only if his total score is strictly greater than the (N-K)'th smallest total score. So the answer consists of two parts:

• Computing the (N-K)'th smallest total score, and
• Finding the smallest number of points for Sergey to exceed this total score.

The first part can easily be done by first computing the N-1 total scores of the other students using a nested loop, and then sorting. The (N-K)'th element of the sorted array is what we want! This runs in O(N \log N + NE) time, but we also note that this can be reduced to just O(NE) by using a linear-time selection algorithm.

For the second part, suppose the (N-K)'th smallest total is x, and Sergey’s total score in the first E-1 exams is y. (y can be computed with a simple loop). Then we must find the minimum score which, when added to y, becomes strictly greater than x. If y > x already, then this is 0. Otherwise (i.e., if y\le x), then we need to find an integer T such that y + T > x. Clearly this is minimized if the sum is as small as possible, but the smallest integer > x is x + 1, so y + T must be equal to x + 1. Thus, T = x - y + 1. Finally, note that an exam score is at most M, so we must check if T \le M, because if T > M, then we conclude that Sergey will not pass.

Here’s an implementation of this algorithm in C++:

``````#include <iostream>
#include <algorithm>
using namespace std;

long long totals;

// select the I'th smallest element from totals...totals[N-1]
long long select(int N, int I) {
sort(totals, totals+N);
}

int main() {
int T;
cin >> T;
for (int cas = 1; cas <= T; cas++) {
int N, K, E, M;
cin >> N >> K >> E >> M;
for (int i = 0; i < N-1; i++) {
long long total = 0;
for (int j = 0; j < E; j++) {
long long score;
cin >> score;
total += score;
}
totals[i] = total;
}
long long x = select(N-1, N-K);
long long y = 0;
for (int j = 0; j < E-1; j++) {
long long score;
cin >> score;
y += score;
}
long long answer = max(0LL, x - y + 1);
cout << "Impossible" << endl;
} else {
}
}
}
``````

Note that we don’t store the individual exam scores. Rather we compute the total of each student on the fly, and just store the totals.

O(N \log N + NE)

### AUTHOR’S AND TESTER’S SOLUTIONS:

whats wrong in my code it works all fine here is my code

``````#include <iostream>
using namespace std;

int maxminmarks(int a[],bool b,int siz){
int returning=a;
if(b==true){
for(int z=0;z<siz;z++){
if(returning<a[z]){
returning=a[z];
}
}
}
if(b==false){
for(int z=0;z<siz;z++){
if(returning>a[z]){
returning=a[z];
}
}
}
return returning;
}

int minmarksindex(int a[],int siz){
int y=a,x=0;
for(int z=0;z<siz;z++){
if(y>a[z]){
y=a[z];
x=z;
}
}
return x;
}

int main(){
int T;
cin >>T;
if(T>=1 && T<=5){
for(int a=0;a<T;a++){
int N=0,K=0,E=0,M=0;
cin >> N;
cin >> K;
cin >> E;
cin >> M;
int marks[N-1];
if(N>=1 && N<=10000 && K>=1 && K<=10000 && M>=1 && M <=1000000000 && E>=1 && E <=4){
for(int b=0;b<(N-1);b++){
int totalmark=0;
for(int c=0;c<E;c++){
int y=0;
cin >>y;
totalmark+=y;
}
marks[b]=totalmark;
}

int topper=0;
topper=maxminmarks(marks,true,(N-1));

int failures=N-K;
for(int z=1;z<failures;z++){
int small=minmarksindex(marks,(N-1));
marks[small]=topper;
}
int firstfailure=maxminmarks(marks,false,(N-1));
int sergeymark=0;
for(int c=0;c<(E-1);c++){
int y;
cin >>y;
sergeymark+=y;
}

int requiredmarks=1+firstfailure-sergeymark;
if(requiredmarks>M){
cout << "Impossible" << endl;
}
else{
if(requiredmarks >=0){
cout << requiredmarks<< endl;
}
else {
cout << 0 << endl;
}
}

}
}
}
}
``````

Do tell me examples where it doesn’t work, But codechef ain’t accepting this one

Hey chinnanah ! try these test case
1
4 2 3 10
2 7 7
4 1 10
0 10 1
10 10
and your output will be negative and it is clearly stated in the question 0<=score<=M.

Please anyone find bug in my program

# define mstud 10000

main( )
{
long long test,students,select,exams,marks,x[mstud],i,j,temp;
scanf("%lld",&test);
while (test–)
{
scanf("%lld %lld %lld %lld",&students,&select,&exams,&marks);
students–;
for (i=0;i<students;i++)
{
x[i]=0;
for (j=0;j<exams;j++)
{
scanf("%lld",&temp);
x[i]+=temp;
}
}
// printf(“Fine”);
//SORTING------HEAPHEAP
{
long long elt,ivalue;
long long s,f;
for (i=1;i<students;i++)
{
elt=x[i],s=i,f=(s-1)/2;
while (s>0 && x[f]<elt)
x[s]=x[f],s=f,f=(s-1)/2;
x[s]=elt;
}
for (i=students-1;i>0;i–){
ivalue=x[i],x[i]=x,f=0;
if (i==1) s=-1;
else s=1;
if (i>2 && x>x) s=2;
while (s>=0 && ivalue<x[s])
{
x[f]=x[s],f=s,s=2*f+1;
if (s+1<=i-1 && x[s]<x[s+1]) s++;
if (s>i-1) s=-1;
}
x[f]=ivalue;
}
}
x[students]=0;
for (j=1;j<exams;j++)
{
scanf("%lld",&temp);
x[students]+=temp;
}
// printf(“x[%llu]=%llu\nx[%llu]=%llu\n”,students-select,x[students-select],students,x[students]);
if (x[students-select]-x[students]<marks)
printf("%lld\n",-x[students]+x[students-select]+1);
else
printf(“Impossible\n”);
}
}

if have now corrected that mistake, still it shows not working

hi!
it works fine on my computer but gives wrong answer when submitted…

``````       #include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
long int n,k,e,m,i,j;
cin>>n>>k>>e>>m;
long int a[n-1][e],diff=0;
long int sum={0};
long int serscr={0},sersum=0;
for(i=0;i<n-1;i++)
{
for(j=0;j<e;j++)
{
cin>>a[i][j];
sum[i]+=a[i][j];

}
}

sort(sum,sum+(n-1));
for(i=0;i<e-1;i++)
{
cin>>serscr[i];
sersum+=serscr[i];

}

diff=sum[n-k-1]-sersum;

if(sersum<0)
{
cout<<0<<endl;
}
else
{
if(diff+1<=m)
{
cout<<diff+1<<endl;
}
else
{

cout<<"Impossible"<<endl;

}

}

}

return 0;
``````

}

Range of M is 1 to 10^9 … how can the score be max(0,x−y+1) // sergey can score a minimum of 1 in the last exam right? … he cant score 0

hey @tarun_174 ! your assumption is totally unpragmatic.Actually ,he can definitely score 0 marks in the last examination as it is already mentioned in the problem statement Score [0,M].

whats wrong with my code plz any 1 tell?
import sys
while t!=0:
n,k,e,m=map(int,input().split())
s=0
b=[]
while n!=1:
a=list(map(int,input().split()))
s=sum(a)
b.append(s)
a=[]
s=0
n=n-1
a=list(map(int,input().split()))
b=sorted(b)

# print(b)

``````s1=sum(a)
minn=999999
f=0
i=n-2
while k!=0:
d=abs(b[i]-s1)
if b[i]>s1 and d<m:
if d<minn:
minn=d
f=1
k=k-1
elif b[i]<s1 and d<m:
f=0
minn=0
k=k-1
elif d>=m:
minn=999999
f=-1
k=k-1
elif d==0:
f=1
minn=d
k=k-1
i=i-1
if f==1:
print(minn+1)
elif f==0:
print(minn)
elif f==-1:
print("Impossible")
t=t-1

``````

Unable to find the bug

``````#include <stdio.h>
#include <stdlib.h>
#define max(X,Y) (X) > (Y) ? (X) : (Y)

long long cmpfunc (const void * a, const void * b)
{
return ( *(long long*)a - *(long long*)b );
}

long long scan(void)
{
long long a;
scanf("%lld", &a);
return a;
}

int main(void) {
int t;
scanf("%d", &t);
while(t--) {
long long n, k, e, m;
scanf("%lld %lld", &n, &k);
scanf("%lld %lld", &e, &m);
long long i, j;
long long sum[n - 1];
long long ser = 0;
for(i = 0; i < n - 1; i++) {
sum[i] = 0;
for(j = 0; j < e; j++)
sum[i] += scan();
}

for(j = 0; j < e - 1; j++) ser += scan();
qsort(sum, n - 1, sizeof(long long), cmpfunc);
long long ans = max(0LL, sum[n - k - 1] + 1 - ser);
if(ans <= m) printf("%d\n", ans);
else printf("Impossible\n");
}
return 0;
}

``````

# getting correct output for any input but it was not accepting my solution what is the wrong in this??

``````#include<stdio.h>
main()
{
int T,N,E,K,M,i,j,c,temp=0,sm,kl,kpl,smm=0;
scanf("%d",&T);
while(T!=0)
{
scanf("%d",&N);
scanf("%d",&K);
scanf("%d",&E);
scanf("%d",&M);
int a[N][E],ca[N];
for(i=0;i<N-1;i++)
{
c=0;
for(j=0;j<E;j++)
{
scanf("%d",&a[i][j]);
c+=a[i][j];
}
ca[i]=c;
}
c=0;
for(j=0;j<E-1;j++)
{
scanf("%d",&a[i][j]);
c+=a[i][j];
}
ca[i]=c;
sm=c;
for(i=0;i<N;i++)
{
for(j=0;j<N-i;j++)
{
if(ca[j]<ca[j+1])
{
temp=ca[j];
ca[j]=ca[j+1];
ca[j+1]=temp;
}
}
}
kl=ca[K-1];
kpl=ca[K-2];
for(i=M;i>=0;i--)
{   int x=sm+i;
if((x>kl) && (x<kpl))
{
smm=i;

}
}
printf("%d\n",smm);
T--;
}
}

``````

//Can someone please tell me what’s wrong with this code

using namespace std;

int main() {
int T;
scanf("%d",&T);

``````while(T--){
int N, K, E, surgeysMarks =0;
long int M;
scanf("%d%d%d%ld",&N,&K,&E,&M);

int totalMarksArray[N-1]={0};//Total marks array of N-1 students

for(int i = 0; i<N-1; i++){//Storing marks of each of N-1 students in the array
for(int j=0; j<E; j++){
int marks;//Temporary variable marks of each of E subjects
scanf("%d",&marks);
totalMarksArray[i]+=marks;//Calculating total marks obtained by the ith student
}
}

//Sorting the totalMarksArray

while(1){
int swapped = 0; //Variable used as a reference to check if the array is sorted
for(int i=0; i<(N-1)-1; i++){
if(totalMarksArray[i]>totalMarksArray[i+1]){
int temp = 0;//Temporary variable for swapping
temp = totalMarksArray[i];
totalMarksArray[i]=totalMarksArray[i+1];
totalMarksArray[i+1]=temp;

swapped = 1;
}
}

if(swapped==0)
break;
}

//Inputting Surgey's Marks in E-1 subjects

for(int i=0; i<E-1; i++){
int surgeysTempMarks;//Temporary variable
scanf("%d",&surgeysTempMarks);

surgeysMarks+=surgeysTempMarks;
}

//Checking if Surgey can pass

if((totalMarksArray[K-1]-surgeysMarks)>M)
printf("Impossible\n");
else if(((totalMarksArray[K-1])-surgeysMarks)<0)//Case when surgey need not score anything to pass
printf("%d",0);
else if((totalMarksArray[K-1]-surgeysMarks)<M)
printf("%d",totalMarksArray[K-1]-surgeysMarks+1);

}

return 0;
``````

}

1 Like

The totals[] array in my program contains the total score of the students. In total = total score of n exams of 1st student. In total = total score of n exams of 2nd student.

I initialized my array as total, but it showed the error SIG SEGV.
I saw the editorial and changed my array size as totals. The code ran in time. How ?

@tarun_174
He can.
The max marks, M is 1 to 10^9. But he can get 0.

This go code produces a timeout. An identical C code works fine! Is it the problem with the testing tool?

``````package main

import (
"fmt"
"sort"
)

type int64arr []int64
func (a int64arr) Len() int { return len(a) }
func (a int64arr) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
func (a int64arr) Less(i, j int) bool { return a[i] < a[j] }

func main() {
var testcases int
var n, k, e, m int
var value int64
var studScores int64arr
var sergeyScore int64

fmt.Scan(&testcases)
for tc := 0; tc < testcases; tc++ {
fmt.Scanln(&n, &k, &e, &m)
studScores = make(int64arr, n - 1)
for i := 0; i < n - 1; i++ {
studScores[i] = 0
for j := 0; j < e; j++ {
fmt.Scan(&value)
studScores[i] += value
}
}
sergeyScore = 0
for j := 0; j < e - 1; j++ {
fmt.Scan(&value)
sergeyScore += value
}
sort.Sort(studScores)
cutoff := studScores[n - k - 1] - sergeyScore + 1
if cutoff < 0 {
fmt.Println("0")
} else if cutoff <= int64(m) {
fmt.Println(cutoff)
} else {
fmt.Println("Impossible")
}
}
}``````

Hi,i wrote this program and it runs fine on my pc with the given example values but when i upload it, it shows wrong answer.can anybody please find the bug,please !!!
#include<stdio.h>
#include<stdlib.h>
void qs(int*,int,int);
int main()
{
int t;
scanf("%d",&t);
(t<=0||t>5)?exit(0):1;//constraint
while(t–)
{
int n,k,e,m;
scanf("%d%d%d%d",&n,&k,&e,&m);
(k<=0||k>1000)?exit(0):1;//constraint
(n<=0||n>1000)?exit(0):1;//constraint
(n<=k)?exit(0):1;//constraint
(e<=0||e>4)?exit(0):1;//constraint
(m<=0||m>1000000000)?exit(0):1;//constraint
int g[n][e];
int i,j;
for(i=0;i<n;i++)
for(j=0;j<e;j++)
{
if((i==(n-1))&&(j==(e-1))) break;
scanf("%d",&g[i][j]);
}
int h[n];
for(i=0;i<n;i++) //summation of each student grades
{
int sum=0;
for(j=0;j<e;j++)
{
if((i==(n-1))&&(j==(e-1))) break;
sum=sum+g[i][j];
}
h[i]=sum;
}
qs(h,0,(n-2));
int check;//keeps difference
if(h[n-1]>h[k-1]) printf(“0\n”);
else
{
check=(h[k-1]-h[n-1])+1;
if(check>m) printf(“Impossible\n”);
else printf("%d\n",check);

``````		}

}
return(0);
}
void qs(int a[],int start,int end) //quicksort
{
int i,swap,pivot=end,index=start;
if(start>=end) return;
for(i=start;i<end;i++)
{
if(a[pivot]<=a[i])
{
swap=a[index];
a[index]=a[i];
a[i]=swap;
++index;
}
}
swap=a[index];
a[index]=a[pivot];
a[pivot]=swap;
pivot=index;
qs(a,start,(pivot-1));
qs(a,(pivot+1),end);
}``````

#include<stdio.h>
void sort(unsigned long*,int);
void sort(unsigned long *a,int n)
{
int i,j;
unsigned long t;

``````for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(a[i]<a[j])
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
}
``````

}
int main()
{

`````` int T,N,K,E,i,j,k1;unsigned long M,s2,s,val;
unsigned long a,sum;
scanf("%d",&T);
for(i=0;i<T;i++)
{
scanf("%d",&N);
scanf("%d",&K);
scanf("%d",&E);
scanf("%u",&M);
for(j=0;j<N-1;j++)
{
for(k1=0;k1<E;k1++)
{
scanf("%u",&a[j][k1]);
}
}
s2=0.0d;
for(k1=0;k1<E-1;k1++)
{
scanf("%u",&a[N-1][k1]);s2=s2+a[N-1][k1];
}
for(j=0;j<N-1;j++)
{
s=0.0d;
for(k1=0;k1<E;k1++)
{
s=s+a[j][k1];
}
sum[j]=s;
}
sort(sum,N-1);
val=sum[K-1];
if((val-s2)>M)
printf("\n Impossible");
else
printf("\n %u",(val-s2+1));

}
return 0;
``````

}

Why ami I getting WA?

//Whats wrong in this code???

#include<stdio.h>

int main()
{
long long int a,n,m,e,k,i,j,temp;
scanf("%lld",&a);
while(a–)
{scanf("%lld%lld%lld%lld",&n,&k,&e,&m);

``````long long int z[e],s[n],v[e],show=0,s2=0,marks=n-k-1;;

for(i=0;i<n-1;i++)
{   s[i]=0;

{
for(j=0;j<e;j++)

{   scanf("%lld",&z[j]);
s[i]+=z[j];
}

}
}
for(j=0;j<e-1;j++)
{scanf("%lld",&v[j]);
s2+=v[j];
}

for (i = 0; i < n-1; ++i)
{
for (j = i + 1; j < n-1; ++j)
{
if (s[i] < s[j])
{
temp =  s[i];
s[i] = s[j];
s[j] = temp;
}

}

}
``````

if(s2+m>s[marks])
{
show=s[marks]+1-s2;
printf("%lld\n",show);
}
else if(s2+m<=s[marks])
printf(“Impossible\n”);

``````}
return 0;
``````

}

can anyone tell what is wrong?

#include <stdio.h>

int main(void) {
int T,N,K,E,M;
scanf("%d",&T);
int i,k,j,l,m;
for(i=0;i<T;i++)
{
scanf("%d %d %d %d",&N,&K,&E,&M);
int a,arr2[N];
int sum;
for(j=0;j<N-1;j++)
{
sum=0;
for(k=0;k<E;k++)
{
scanf("%d",&a);
sum=sum+a;
}
arr2[j]=sum;
// printf("%d\n",arr2[j]);
}
sum=0;
for(k=0;k<E-1;k++)
{
scanf("%d",&a);
sum=sum+a;
}
arr2[j]=sum;
// printf("%d\n",arr2[j]);

``````    for(l=0;l<N-1;l++)
{
for(m=l+1;m<N;m++)
{
if(arr2[l]<arr2[m])
{
int temp=arr2[l];
arr2[l]=arr2[m];
arr2[m]=temp;
}
}
//  printf("   %d   ",arr2[l]);
}
int result=arr2[K-1]-arr2[N-1]+1;
result=abs(result);
if(result<=M)
printf("%d\n",result);
else
printf("Impossible\n");

}
return 0;
``````

}

#include
#include
using namespace std;
int main()
{
int t;
cin>>t;
int t1=t;
long long int n,k,e,m,temp,sum;
while(t–)
{
cin>>n>>k>>e>>m;
long long int a[n];

``````    //Take input
for(long long int i=0;i<n-1;i++)
{
sum = 0;
for(long long int j=0;j<e;j++)
{
cin>>temp;
sum += temp;
}
a[i] = sum;
}
sum = 0;
for(long long int j=0;j<e-1;j++)
{
cin>>temp;
sum += temp;
}
a[n-1] = sum;

//Do processing
sort(a,a+n-1,greater<int>());
long long int value = a[k-1];
if(value<a[n-1])
{
cout<<"0"<<endl;
}
else if(value-a[n-1]+1<=m)
{
cout<<value-a[n-1]+1<<endl;
}
else
{
cout<<"Impossible"<<endl;
}
}
return 0;
``````

}
What is wrong in this code?