Kindly explain this problem ! (link in the description )

https://www.codechef.com/problems/ENTEXAM

let us suppose that total no of student , n=5
total marks of all exam of all contestant except Sergey arranged in ascending order is 20 20 20 20
now let us suppose Sergey total marks in E-1 subjects is 15 where E is total no of subject and M (max marks that can be scored ) is 10
and total no of students which may be selected , k=2

now here in order to be selected Sergey need to score more than at least n-k students i.e he has to score more than 3 students in this case .
this can be possible only when sergey total scores gets 21 (15+6)
In this way he will get his score more than at least 3 students .
so now if you see total marks of each contestant it will be
20 20 20 20 21 (arrange in ascending order)
Since only 2 students can be selected so Sergey can be first student but then who will be the second student because here no student marks is more than at least 3 students marks ???

If k=2 i.e. only 2 students will be selected. Then Sergey has to score atleast 15+6=21 to get selected as all have the same score. Here, you need don’t have to take care who will be selected second as no such criterion is mentioned in the problem. So, just find the minimum score by which Sergey can be selected.

1 Like

ok i have improved that
can you cheek why my solution is still wrong ?

Please provide your submission link

1 Like

just wait few sec sir

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

IF my total possible score score will be greater than at least n-k students total score than i will be selected .
else impossible
is it correct ?

I have a theory, and it’s an unusually subtle one.

Weirdly, when compiling as C, gcc doesn’t complain about this, but when compiling as C++ it does, very loudly:

[simon@simon-laptop][17:42:07]
[~/devel/hackerrank/otherpeoples]>./compile-latest-cpp.sh 
Compiling k_purushottam-ENTEXAM.cpp
k_purushottam-ENTEXAM.cpp: In function ‘int main()’:
k_purushottam-ENTEXAM.cpp:33:53: error: invalid conversion from ‘long long int (*)(const void*, const void*)’ to ‘__compar_fn_t {aka int (*)(const void*, const void*)}’ [-fpermissive]
         qsort(arr1,n-1,sizeof(long long int),compare);
                                                     ^
In file included from /usr/include/c++/7/cstdlib:75:0,
                 from /usr/include/c++/7/stdlib.h:36,
                 from k_purushottam-ENTEXAM.cpp:4:
/usr/include/stdlib.h:827:13: note:   initializing argument 4 of ‘void qsort(void*, size_t, size_t, __compar_fn_t)’
 extern void qsort (void *__base, size_t __nmemb, size_t __size,

As the error suggests, compare should return an int, not a long long int. Presumably, internally qsort treats the result of compare as an int, but your compare is subtracting long long ints and returning the result, and this might overflow an int, meaning that qsort gets the wrong ordering for pairs of elements, completely breaking its attempt at sorting them.

Changing your compare to something like this:

int compare(const void *p1,const void *p2)
{
    const long long int p1AsLong = *(long long int *)p1;
    const long long int p2AsLong = *(long long int *)p2;
    if (p1AsLong < p2AsLong)
        return -1;
    if (p1AsLong > p2AsLong)
        return +1;
    return 0;
}

might work.

Edit:

I tell a lie: compiling it as C does cause gcc to warn about it:

[simon@simon-laptop][17:49:20]
[~/devel/hackerrank/otherpeoples]>gcc k_purushottam-ENTEXAM.c -DONLINE_JUDGE -D_GLIBCXX_DEBUG    -fsanitize=undefined -ftrapv -Wall -Wextra
k_purushottam-ENTEXAM.c: In function ‘main’:
k_purushottam-ENTEXAM.c:46:46: warning: passing argument 4 of ‘qsort’ from incompatible pointer type [-Wincompatible-pointer-types]
         qsort(arr1,n-1,sizeof(long long int),compare);
                                              ^~~~~~~
In file included from k_purushottam-ENTEXAM.c:4:0:
/usr/include/stdlib.h:827:13: note: expected ‘__compar_fn_t {aka int (*)(const void *, const void *)}’ but argument is of type ‘long long int (*)(const void *, const void *)’
 extern void qsort (void *__base, size_t __nmemb, size_t __size,
             ^~~~~

Edit3:

Here’s a specific test input that your solution fails on.

3 Likes

Here’s the AC code. You code was correct, just you were not handling the cases properly. I have fixed the cases and now its working find. And I changed the qsort to standard sort(a,a+n) as it was shown as error, so you can just fix that and you are good to go.

1 Like

Sir, what I understand for you is that qsort only sort the array which are of int type not long long int type
it that you want to say ?

No: you can qsort an array of long long int elements, but the compare function you pass to qsort must return an int.

if compare function will return an int than if i am comparing 2 long long int element than at at end it will return an int
but we know elements are of long long int type so this will again be wrong ?

sir can you please tell me which cases i was not handling properly ?
it will be a great help

Read the documentation for qsort:

https://en.cppreference.com/w/c/algorithm/qsort

in particular, the “Parameters” “comp” part.

2 Likes

ok thanks a lot now i understand it . :grinning:

1 Like