You are not logged in. Please login at www.codechef.com to post your questions!

×

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[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);
        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

This question is marked "community wiki".

asked 12 Jun '16, 08:06

kevinsogo's gravatar image

7★kevinsogo
1.7k473136
accept rate: 11%

edited 15 Jun '16, 14:19

admin's gravatar image

0★admin ♦♦
16.9k347485513


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

include <iostream>

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;

}

link

answered 23 Jun '16, 23:00

greeshmanreddy's gravatar image

0★greeshmanreddy
11
accept rate: 0%

Can someone please help what is wrong in this code?

link

answered 03 Apr, 01:30

monsij's gravatar image

4★monsij
513
accept rate: 0%

edited 03 Apr, 01:33

vijju123's gravatar image

5★vijju123 ♦
11.2k314

Fixed the link. :)

(03 Apr, 01:33) vijju123 ♦5★

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[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

link

answered 17 Jun '16, 23:22

chinnanah's gravatar image

1★chinnanah
1
accept rate: 0%

edited 18 Jun '16, 15:58

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

(18 Jun '16, 15:57) chinnanah1★

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.

link

answered 18 Jun '16, 07:41

demo01's gravatar image

2★demo01
702
accept rate: 12%

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&lt;exams;j++)" {="" scanf("%lld",&temp);="" x[i]+="temp;" }="" }="" printf("fine");="" sorting------heapheap="" {="" long="" long="" elt,ivalue;="" long="" long="" s,f;="" for="" (i="1;i&lt;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[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\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"); } }

link

answered 18 Jun '16, 10:33

anushi's gravatar image

5★anushi
22717
accept rate: 20%

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

}

link

answered 18 Jun '16, 16:36

kashif93's gravatar image

2★kashif93
1
accept rate: 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

link

answered 20 Jun '16, 13:49

tarun_174's gravatar image

2★tarun_174
1
accept rate: 0%

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

Please upvote,I need karma to upvote or ask questions

(28 Jun '16, 19:11) cyberneo2★

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].

link

answered 20 Jun '16, 16:50

demo01's gravatar image

2★demo01
702
accept rate: 12%

edited 21 Jun '16, 21:58

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[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
link

answered 20 Jun '16, 20:58

abhi123_'s gravatar image

2★abhi123_
1
accept rate: 0%

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;
}
link

answered 21 Jun '16, 13:22

pragyan_123's gravatar image

2★pragyan_123
11
accept rate: 0%

edited 21 Jun '16, 13:23

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&lt;E;j++)" {="" scanf("%d",&amp;a[i][j]);="" c+="a[i][j];" }="" ca[i]="c;" }="" c="0;" for(j="0;j&lt;E-1;j++)" {="" scanf("%d",&amp;a[i][j]);="" c+="a[i][j];" }="" ca[i]="c;" sm="c;" for(i="0;i&lt;N;i++)" {="" for(j="0;j&lt;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--;="" }="" }="" <="" code="">
link

answered 21 Jun '16, 21:28

anjalichinni12's gravatar image

0★anjalichinni12
11
accept rate: 0%

edited 21 Jun '16, 21:32

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 ?

link

answered 25 Jun '16, 18:34

mehuls_45's gravatar image

3★mehuls_45
9
accept rate: 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")
        }
    }
}
link

answered 09 Jul '16, 19:11

balajiarun's gravatar image

0★balajiarun
1
accept rate: 0%

 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);
}
link

answered 09 Jul '16, 20:24

bazooka47's gravatar image

0★bazooka47
1
accept rate: 0%

an identical code gives the correct answer but mine doesnt why so ? its in java ' import java.util.*; class Eq { public static void main(String[] args) { Scanner sc =new Scanner(System.in); int t=sc.nextInt(); for(int i=0;i<t;i++) { int n =sc.nextInt(); int k =sc.nextInt(); int e =sc.nextInt(); int m =sc.nextInt(); long [] scores = new long[n-1]; long sergeyScore=0; for(int j=0;j<n-1;j++) { for(int l=0;l<e;l++) { int temp=sc.nextInt(); scores[j]+=temp ; } } Arrays.sort(scores); for(int j=0;j<(e-1);j++) { int temp1 = sc.nextInt(); sergeyScore+=temp1; }

        long lastSelected = 0;
        long marksNeeded =0;
         lastSelected = scores[n-k-1];
         marksNeeded = lastSelected-sergeyScore+1;
        if(marksNeeded<0)
        {
            System.out.println("0");
        }
        if(marksNeeded <=m)
        {
            System.out.println(marksNeeded);
        }
        else
        {
            System.out.println("Impossible");
        }
    }
}

}'

link

answered 17 Jul '16, 00:04

thakkarjinal99's gravatar image

2★thakkarjinal99
1
accept rate: 0%


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[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("\n Impossible");
     else
        printf("\n %u",(val-s2+1));

 }
 return 0;

}

Why ami I getting WA?

link

answered 20 Jul '16, 13:33

saikat777's gravatar image

1★saikat777
1
accept rate: 0%

//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;

}

link

answered 22 Jul '16, 02:17

v1ka5h's gravatar image

2★v1ka5h
1
accept rate: 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;

}

link

answered 31 Jul '16, 18:19

shikhar_deep05's gravatar image

2★shikhar_deep05
1
accept rate: 0%

include<iostream>

include<algorithm>

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?

link

answered 17 Aug '16, 17:31

nik96's gravatar image

2★nik96
1
accept rate: 0%

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.

link

answered 18 Aug '16, 04:34

shubhiks's gravatar image

5★shubhiks
10013
accept rate: 0%

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!

link

answered 31 Aug '16, 12:12

kanna19's gravatar image

0★kanna19
1
accept rate: 0%

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&lt;E;j++)" {="" scanf("%d",&amp;a[i][j]);="" c+="a[i][j];" }="" ca[i]="c;" }="" c="0;" for(j="0;j&lt;E-1;j++)" {="" scanf("%d",&amp;a[i][j]);="" c+="a[i][j];" }="" ca[i]="c;" sm="c;" for(i="0;i&lt;N;i++)" {="" for(j="0;j&lt;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--;="" }="" }="" <="" code="">

link

answered 12 Sep '16, 20:37

dileri_1996's gravatar image

0★dileri_1996
1
accept rate: 0%

Please tell me why my code is giving a wrong answer`import java.util.*;

class Entexam{

public static void main(String[] args){
    Scanner scanner = new Scanner(System.in);
    int T = scanner.nextInt();
    int N,K,E,M;
    for (int p=0;p<T;p++){
        N=scanner.nextInt(); //No. of students
        K=scanner.nextInt(); //These many students shall pass
        E=scanner.nextInt(); //no of tests
        M=scanner.nextInt(); // max marks in a test

        int[] marksOfOthers = new int[N-1]; 
        for(int j=0;j<N-1;j++){

            marksOfOthers[j]=0;
            for(int k=0;k<E;k++){

                marksOfOthers[j]+=scanner.nextInt();
            }

        }
        //Now marks have been taken of N-1 guys
        int mySum=0;
        for(int i=0;i<E-1;i++){
            mySum+=scanner.nextInt();
        }

        //I need to sort the marks array - I am using bubble sort for now
        Arrays.sort(marksOfOthers);
        //Now array sorted  , now I just need to get its score more than the kth person's score

        int targetScore = marksOfOthers[N-K-1] - mySum + 1;
        if(targetScore>M){
        //impossible
        System.out.println("Impossible");
        }else if (targetScore<0){

        //possible
        System.out.println(0);
        }else{
            System.out.println(targetScore);
        }




    }

    scanner.close();

}

} `

link

answered 17 Sep '16, 03:16

kartikg2jee's gravatar image

0★kartikg2jee
1
accept rate: 0%

This ruby code works fine for me elsewhere but gives NZEC while submission, any suggestions ?

t = gets.to_i
t.times do
  merit_list = []
  input = gets.split.map(&:to_i)
  n, k, e, m = input[0], input[1], input[2], input[3]
  (n-1).times do
    student_marks = gets.split.map(&:to_i)
    merit_list.push(student_marks.sum)
  end
  my_marks = gets.split.map(&:to_i)
  my_sum = my_marks.sum
  merit_list = merit_list.sort.reverse
  marks_to_get = merit_list[k-1] - my_sum + 1
  if (marks_to_get <= m)
    puts marks_to_get
  else
    puts "Impossible"
  end
end
link

answered 02 Dec '16, 17:47

akkee19's gravatar image

1★akkee19
1
accept rate: 0%

#include <bits/stdc++.h>


using namespace std;
int main()
{
    int t,k,n,e;
    long int o,ma;
    vector<long int> m(100011);
    cin>>t;
    while(t--)
    {
        long int total;
        cin >> n>>k>>e>>ma;
        for(int i=0;i<n-1;i++)
        {
            total=0;
            for(int j=0;j<e;j++)
           {
                cin>>o;
                total+=o;
            }
            m[i]=total;
        }
        total=0;
        sort(m.begin(),m.end());
        reverse(m.begin(),m.end());
        for(int i=0;i<e-1;i++)
        {
            cin>>o;
            total+=o;
            }
            long int x=total;
        long int y=m[n-k-1];
        long int mx=max(0L,y-x+1);
        //cout<<mx;
        if(mx>ma)
        cout<<"Impossible"<<endl;
        else
        cout<<mx<<endl;
        m.clear(); 
    }
    return 0;
}

what's wrong with my code?

link

answered 17 Feb, 00:28

gauthamnambi's gravatar image

1★gauthamnambi
1
accept rate: 0%

Can someone take a look at my code. I've been trying to refine it all day! If you want to be updated with my changes, kindly take a look over https://gist.github.com/salman-bhai/f51412bd45aa4c61c07071e089f9954e:

#include <bits/stdc++.h>
using namespace std;

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

    while(t--) {
        long long int n, k, e;
        long long int m;
        scanf("%lld %lld %lld %lld",&n,&k,&e,&m);

        long long int arr[n][e];
        long long int total[n-1]={0};

        for(long long int i = 0; i < n-1; i ++) {
            for(long long int j = 0; j < e; j ++) {
                scanf("%lld",&arr[i][j]);
                total[i] += arr[i][j];
            }
        }

        long long int sergey=0;
        for(long long int i = 0; i < e-1; i ++) {   
            long long int temp;
            scanf("%lld",&temp);
            sergey += temp;
        }

        sort(total, total+n-1);

        if(sergey > total[n-k-1])
            printf("1\n");
        else if(sergey <= total[n-k-1] && (total[n-k-1]-sergey+1 <= m))
            printf("%lld\n",(total[n-k-1]-sergey+1));
        else
            printf("Impossible\n");

    }

    return 0;
}

[1]: http:// https://gist.github.com/salman-bhai/f51412bd45aa4c61c07071e089f9954e

link

answered 06 Mar, 16:59

sbshah's gravatar image

2★sbshah
1
accept rate: 0%

@sbshah

The first error I noticed in your code is for cases where his total score is already large enough, that he can take get admission despite getting 0 in final exam.

Eg-

Compilation Successful
Input (stdin)
1
4 2 3 10
1 1 1
2 2 2
3 4 5
10 10
Your Output
1
Expected Output-
0

In case where his total score exceeds everyone else's score by such a large factor, that he need not score any mark in final exam, the output should be 0, as its possible to score 0 in exam. Your program is printing 1 for that case which is incorrect (if my interpretation of Q's line "In total there are E entrance exams, in each of them one can score between 0 and M points, inclusively" is correct)

link

answered 06 Mar, 18:23

vijju123's gravatar image

5★vijju123 ♦
11.2k314
accept rate: 18%

edited 06 Mar, 18:24

Anybody help me out with my code it gives wrong answers on submission

`#include<stdio.h>

int main() { long long int t,n,k,e,m,numb,i,j,z; long long int na[10000]; scanf("%d",&t); while(t--) { scanf("%lld%lld%lld%lld",&n,&k,&e,&m); for(i=0;i<n;i++) { na[i]=0; if(i==(n-1)) { for(j=0;j<e-1;j++) { scanf("%lld",&z); na[i]=na[i]+z; } } else { for(j=0;j<e;j++) { scanf("%lld",&z); na[i]=na[i]+z; } }

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

            }
        }
    }

    numb=na[k-1]+1;
    numb=numb-na[n-1];
    if(numb<=m)
    printf("%lld\n",numb);
    else
    printf("Impossible\n");

}
return 0;

}`

link

answered 22 Mar, 03:37

vruhela05's gravatar image

2★vruhela05
1
accept rate: 0%

enter code here
hhg
jvvv
#include<stdio.h>

int main() {

long long int t,n,k,e,m,numb,i,j,z;

long long int na[10000];

scanf("%d",&t);

while(t--) {

scanf("%lld%lld%lld%lld",&n,&k,&e,&m);

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

na[i]=0;

       if(i==(n-1))
       {  
        `for(j=0;j<e-1;j++)
         {

          scanf("%lld",&z);

          na[i]=na[i]+z;
          }
        }
        else
        {

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

            scanf("%lld",&z);

           na[i]=na[i]+z;
          }
        }

    }

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

               for(j=(i+1);j<(n-1);j++)
        {
               if(na[i]<na[j])

         { numb=na[i];

             na[i]=na[j];

             na[j]=numb;

            }
        }
    }


numb=na[k-1]+1;

numb=numb-na[n-1];

   if(numb<=m)

    printf("%lld\n",numb);

    else

    printf("Impossible\n");

}
return 0;

}

link

answered 22 Mar, 03:41

vruhela05's gravatar image

2★vruhela05
1
accept rate: 0%

#include<stdio.h>
#include<algorithm>
int main(){
long long int t,n,k,e,m,i,j,sum,x,y,z,ans;
scanf("%lld",&t);
while(t--){
scanf("%lld %lld %lld %lld",&n,&k,&e,&m);int a[n-1];
for(i=0;i<(n-1);i++)
{sum=0;
for(j=0;j<e;j++){ scanf("%lld",&x);sum+=x;}
a[i]=sum;
}std::sort(a,a+n-1);
y=a[n-k-1];ans=y;
for(j=0;j<e-1;j++){scanf("%lld",&z);ans=ans-z;}
if(ans=>0 && ans<=m)printf("%lld\n",ans);else if(ans>m)printf("Impossible\n"); else printf("0\n"); 
}
return 0;
} 

https://www.codechef.com/viewsolution/13147275/ @Sergey Kulik @Vasya Antoniuk @Kevin Atienza where is my solution going wrong ?

link

answered 23 Mar, 22:03

rj25's gravatar image

4★rj25
432
accept rate: 0%

Help me what wrong with this?????

#include<stdio.h>
#include<stdlib.h>
int main(){
long o,N,K,E,M,i,j,t,u,y=1;
scanf("%ld",&o);
while(o--){
int z=0;
y=1;
scanf(" %ld %ld %ld %ld",&N,&K,&E,&M);
long s[N];
for(i=0;i<(N-1);i++){
s[i]=0;
for(j=0;j<E;j++){
scanf(" %ld",&t); s[i]+=t;}}
s[N-1]=0;
for(i=0;i<(E-1);i++){scanf(" %ld",&t); s[N-1]+=t;}
for(i=0;i<(N-1);i++){
if(s[N-1]>s[i]) z++;}  if(z>=(N-K)) {printf("%d",0);} else{
u=s[N-1];
while(z<(N-K)){
for(j=0;j<(N-1);j++){if(s[j]>=s[N-1]){t=s[j]; break;}}
for(i=j;i<(N-1);i++){
if((s[i]>=s[N-1])&&(s[i]<t)) t=s[i];}
if((t-u)<M) s[N-1]=t+1; else{printf("Impossible"); y=0; break;}
z=0;
for(i=0;i<(N-1);i++){
if(s[N-1]>s[i]) z++;}
}if(y==1) printf("%d",(t-u+1));}}return 0;}
link

answered 26 Mar, 14:52

kchiranjewee63's gravatar image

0★kchiranjewee63
1
accept rate: 0%

edited 26 Mar, 15:38

@monsij

Your code fails at this test case

 Compilation Successful
Input (stdin)
1
4 2 3 11
10 10 10
10 10 10
10 10 10
10 10
Your Output
Impossible
Expected Output 
11

I feel the error is here-

for(i=0; i<=10;i++)
        {
            if((sum + i) > mark[n-k-1])
            {
                ans=i;
                flag=1;
                break;
            }
        }

I think i should be less than or equal to m, instead of 10 in loop condition. Try it and tell. :)

link

answered 03 Apr, 01:54

vijju123's gravatar image

5★vijju123 ♦
11.2k314
accept rate: 18%

edited 03 Apr, 01:56

Could someone please help me find the error?

include<iostream>

include<algorithm>

using namespace std;

int main(){
  long long t,n,m,e,k;
  long long sum[10000]={};
  long s;
  int pos=0;
  cin>>t;
  for(int i=0;i<t;i++){
    cin >> n >> k>>e>>m;
    long int j;
    for(j=0;j<n-1;j++){
      s=0;
      for(int l=0;l<e;l++){
        cin>>s;
        sum[j]+=s;
      }
    }
    s=0;pos=j;
    for(int l=0;l<e-1;l++){
      cin>>s;
      sum[j]+=s;
    }
    sort(sum,sum+pos);
    long long x = sum[n-k-1]-sum[pos]+1;
    if(x<0)         cout<<0<<endl;
    else if(x<m)   cout<<x<<endl;
    else            cout<<"Impossible"<<endl;
  }
  return 0;
}

Thanks!

link

answered 09 Apr, 15:12

utkarsh867's gravatar image

0★utkarsh867
1
accept rate: 0%

Before anything- what is the significance of smallest in "(N−K)'th smallest total is x"?

link

answered 01 May, 23:02

kodeerder's gravatar image

1★kodeerder
635
accept rate: 0%

edited 01 May, 23:02

what is wrong with this code of mine? Unable to find the condition where it gives Wrong Answer. Please help.

import java.util.*;

class Entrance { public static void main(String args[]) { Scanner sc = new Scanner(System.in); int tc,n,k,e,i,l,j,z,count; long m,mx,temp; tc = sc.nextInt(); n = sc.nextInt(); k = sc.nextInt(); e = sc.nextInt(); m = sc.nextLong(); long ma[] = new long[e]; long sum[] = new long[n]; long sum1[] = new long[n-1];

    for(count=0; count<tc; count++)
    {

        for (i=0; i<n-1; i++)
        {
            for(j=0; j<e; j++)
            {
                ma[j] = sc.nextLong();
                sum[i]+=ma[j];
            }
        }
        for(l=0; l<e-1; l++)
        {
            ma[l] = sc.nextLong();
            sum[i]+=ma[l];  
        }

        mx = sum[i];

        for(z=0; z<n-1; z++)
            sum1[z]=sum[z];

        for(i=0; i<(sum1.length-1); i++)
        {
            for(j=0; j<(sum1.length-1-i); j++)
            {
                if(sum1[j]>sum1[j+1])
                {
                    temp = sum1[j];
                    sum1[j] = sum1[j+1];
                    sum1[j+1] = temp;
                }
            }
        }

        if ((sum1[k-1]-mx) < m)
        {
            if((sum1[k-1]-mx)>=0)
            System.out.println(sum1[k-1]-mx+1);
            else
            System.out.println("0");
        }
            else
            System.out.println("Impossible");

    }
}

}

link

answered 31 May, 14:55

piyush_27_5's gravatar image

2★piyush_27_5
1
accept rate: 0%

can anyone tell me for which test cases this code is failing?

include<iostream>

include<algorithm>

using namespace std; int main(){ long int m,n,t,i,j,k,e,last,p,min; cin>>t; while(t--){

cin>>n>>k>>e>>m;
last=0;
long int ar[n-1][e],sum_ar[n],sum;
for(i=0;i<n-1;i++){
    sum=0;
    for(j=0;j<e;j++){
    cin>>ar[i][j];sum+=ar[i][j];
}sum_ar[i]=sum;
}
for(i=0;i<e-1;i++){
    cin>>p;last+=p;
}
sort(sum_ar,sum_ar+n-1);
min=sum_ar[n-k-1]-last+1;
if(min<0)cout<<0<<endl;
else if(min>m)cout<<"Impossible"<<endl;
else cout<<min<<endl;


//for(i=0;i<n-1;i++)cout<<sum_ar[i]<<" ";

} return 0; }

link

answered 18 Jun, 21:18

sayantan11995's gravatar image

1★sayantan11995
1
accept rate: 0%

I am getting runtime error(NZEC) , don't know why? , what is wrong with my code?

import sys import math import string

t=int(input()) while t>0: n,k,e,m=list(map(int,input().strip().split(" "))) i=1 tm=[] while i<=n-1: l=list(map(int,input().strip().split(" "))) tm.append(sum(l)) i=i+1 l=list(map(int,input().strip().split(" "))) tm.sort(reverse=True)

if sum(l)>tm[k-1]:
    print("0")
else:
    if tm[k-1]-sum(l)+1>m:
        print("Impossible")
    else:
        print(tm[k-1]-sum(l)+1)
t=t-1
link

answered 10 Jul, 16:44

tomy_495's gravatar image

2★tomy_495
1
accept rate: 0%

import java.util.ArrayList;

import java.util.Scanner;

public class code {

public static void main(String args[])
{
    Scanner scan = new Scanner(System.in);
    Integer testCase = scan.nextInt();
    ArrayList<Integer> result = new ArrayList<>();
    if(testCase>=1 && testCase<=5)
    {
        for (int i = 0; i < testCase; i++) 
        {
            scan.nextLine();
            String str = scan.nextLine();
            String[] string = str.split(" ");
            Integer N = Integer.parseInt(string[0]);
            Integer K = Integer.parseInt(string[1]);
            Integer E = Integer.parseInt(string[2]);
            Integer M = Integer.parseInt(string[3]);
            if(K>=1 && K<N)
            {
                if(N>1 && N<10000)
                {
                    if(M>1 && M<1000000000)
                    {
                        if(E>=1 && E<=4)
                        {
                            ArrayList<Integer> studentMarks = new ArrayList<>();
                            for (int j = 0; j < N; j++) 
                            {
                                Integer sum=0;
                                String str1 = scan.nextLine();
                                String[] string1 = str1.split(" ");
                                for (int l = 0; l < string1.length; l++) 
                                {
                                    sum = sum+Integer.parseInt(string1[l]);
                                }
                                studentMarks.add(sum);
                            }
                            Integer his_marks = studentMarks.get(studentMarks.size()-1);
                            studentMarks.remove(studentMarks.size()-1);
                            for (int j = 1; j < studentMarks.size(); j++) 
                            {
                                Integer key = studentMarks.get(j);
                                Integer k= j-1;
                                while(k>=0 && studentMarks.get(k)>key)
                                {
                                    studentMarks.set(k+1, studentMarks.get(k));
                                    k=k-1;
                                }
                                studentMarks.set(k+1,key);
                            }
                            Integer minimum_marks =studentMarks.get((studentMarks.size()-(N-K)));
                            Integer required = (minimum_marks-his_marks)+1;
                            result.add(required);
                        }
                    }
                }
            }
        }
    }
    for (Integer integer : result) {
        System.out.println(integer);
    }
}

}

What's wrng with this one? Getting NZEC error!

link

answered 30 Sep, 11:11

bajasahay's gravatar image

1★bajasahay
51
accept rate: 0%

import java.util.ArrayList;

import java.util.Scanner;

public class code {

public static void main(String args[])
{
    Scanner scan = new Scanner(System.in);
    Integer testCase = scan.nextInt();
    ArrayList<Integer> result = new ArrayList<>();
    if(testCase>=1 && testCase<=5)
    {
        for (int i = 0; i < testCase; i++) 
        {
            scan.nextLine();
            String str = scan.nextLine();
            String[] string = str.split(" ");
            Integer N = Integer.parseInt(string[0]);
            Integer K = Integer.parseInt(string[1]);
            Integer E = Integer.parseInt(string[2]);
            Integer M = Integer.parseInt(string[3]);
            if(K>=1 && K<N)
            {
                if(N>1 && N<10000)
                {
                    if(M>1 && M<1000000000)
                    {
                        if(E>=1 && E<=4)
                        {
                            ArrayList<Integer> studentMarks = new ArrayList<>();
                            for (int j = 0; j < N; j++) 
                            {
                                Integer sum=0;
                                String str1 = scan.nextLine();
                                String[] string1 = str1.split(" ");
                                for (int l = 0; l < string1.length; l++) 
                                {
                                    sum = sum+Integer.parseInt(string1[l]);
                                }
                                studentMarks.add(sum);
                            }
                            Integer his_marks = studentMarks.get(studentMarks.size()-1);
                            studentMarks.remove(studentMarks.size()-1);
                            for (int j = 1; j < studentMarks.size(); j++) 
                            {
                                Integer key = studentMarks.get(j);
                                Integer k= j-1;
                                while(k>=0 && studentMarks.get(k)>key)
                                {
                                    studentMarks.set(k+1, studentMarks.get(k));
                                    k=k-1;
                                }
                                studentMarks.set(k+1,key);
                            }
                            Integer minimum_marks =studentMarks.get((studentMarks.size()-(N-K)));
                            Integer required = (minimum_marks-his_marks)+1;
                            result.add(required);
                        }
                    }
                }
            }
        }
    }
    for (Integer integer : result) {
        System.out.println(integer);
    }
}

}

What's wrng with this one? Getting NZEC error!

link

answered 30 Sep, 11:11

bajasahay's gravatar image

1★bajasahay
51
accept rate: 0%

https://www.codechef.com/viewsolution/15958617

Have a look at my solution and the comment on 20th line. Had to debug a lot to find that code chef compiler puts the value of 0 instead of increment by 1(number of people with that specific marks all total) in spite of using '++'. But I get the right answer when using '+1' ironically. Is there something wrong with <map> in code chef compiler as ++ worked fine in visual c++ 2017

link

answered 26 Oct, 09:24

faded4k's gravatar image

2★faded4k
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×11,987
×795
×70
×43
×8

question asked: 12 Jun '16, 08:06

question was seen: 7,750 times

last updated: 26 Oct, 09:24