ENTEXAM - Editorial

PROBLEM LINK:

Contest
Practice

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

DIFFICULTY:

Simple

PREREQUISITES:

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[10011];

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

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* = 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);
        if (answer > M) {
            cout << "Impossible" << endl;
        } else {
            cout << answer << endl;
        }
    }
}

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.

Time Complexity:

O(N \log N + NE)

AUTHOR’S AND TESTER’S SOLUTIONS:

setter
tester
editorialist

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[0];
    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[0],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**=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*=0;
for (j=0;j<exams;j++)
{
scanf("%lld",&temp);
x*+=temp;
}
}
// printf(“Fine”);
//SORTING------HEAPHEAP
{
long long elt,ivalue;
long long s,f;
for (i=1;i<students;i++)
{
elt=x*,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*,x*=x[0],f=0;
if (i==1) s=-1;
else s=1;
if (i>2 && x[2]>x[1]) 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
x[%llu]=%llu
“,students-select,x[students-select],students,x[students]);
if (x[students-select]-x[students]<marks)
printf(”%lld
",-x[students]+x[students-select]+1);
else
printf("Impossible
");
}
}

hi!
please help me with my code,
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[1001]={0};
         long int serscr[4]={0},sersum=0;
         for(i=0;i<n-1;i++)
         {
            for(j=0;j<e;j++)
            {
               cin>>a*[j];
               sum*+=a*[j];
  
            }   
         }

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

         }

         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 t=int(sys.stdin.readline()) 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*-s1)
    if b*>s1 and d<m:
        if d<minn:
            minn=d
            f=1
        k=k-1
    elif b*<s1 and 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 
#include 
#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* = 0;
            for(j = 0; j < e; j++)
                sum* += 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
", ans);
        else printf("Impossible
");
    }
    return 0;
}

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

#include
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*[j]);
                c+=a*[j];
            }
            ca*=c;
        }
        c=0;
        for(j=0;j<E-1;j++)
        {
            scanf("%d",&a*[j]);
            c+=a*[j];
        }
        ca*=c;
        sm=c;
        for(i=0;i<N;i++)
        {
            for(j=0;j<N-i;j++)
            {
                if(ca[j]=0;i--)
        {   int x=sm+i;
            if((x>kl) && (x<kpl))
            {
                smm=i;

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

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

#include

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*+=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*>totalMarksArray[i+1]){
                int temp = 0;//Temporary variable for swapping
                temp = totalMarksArray*;
                totalMarksArray*=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

“);
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[0] = total score of n exams of 1st student. In total[1] = total score of n exams of 2nd student.

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

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*, a[j] = a[j], a* }
func (a int64arr) Less(i, j int) bool { return a* < 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* = 0
			for j := 0; j < e; j++ {
				fmt.Scan(&value)
				studScores* += 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*[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*[j];
}
h*=sum;
}
qs(h,0,(n-2));
int check;//keeps difference
if(h[n-1]>h[k-1]) printf("0
");
else
{
check=(h[k-1]-h[n-1])+1;
if(check>m) printf("Impossible
“);
else printf(”%d
",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*)
		{
			swap=a[index];
			a[index]=a*;
			a*=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*<a[j])
        {
            t=a*;
            a*=a[j];
            a[j]=t;
        }
    }
}

}
int main()
{

 int T,N,K,E,i,j,k1;unsigned long M,s2,s,val;
unsigned long a[10000][4],sum[10000];
 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("

Impossible");
else
printf("
%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*=0;

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

        {   scanf("%lld",&z[j]);
        s*+=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* < s[j])
        {
            temp =  s*;
            s* = s[j];
            s[j] = temp;
        }

    }

}

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

}
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
“,arr2[j]);
}
sum=0;
for(k=0;k<E-1;k++)
{
scanf(”%d",&a);
sum=sum+a;
}
arr2[j]=sum;
// printf("%d
",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

",result);
else
printf("Impossible
");

}
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* = 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?

All those who are getting wrong answers, its highly suggested to do a dry run of some test case which is giving a wrong answer, checking the corner cases. Because this is a simple ad-hoc problem and most of your simple logic implemented is correct. Though, you can also check someone else’s code if you are not able to figure out the mistake in your code.

1 Like

Hi,
Can you please help me find the bug in my code sumbmitted in the following link.
https://www.codechef.com/viewsolution/11285222
It works fine, but not accepted when submittd.
Thanks in advance!