Qualprel - editorial

general
, , , ,
1

PROBLEM LINK:

Practice
Contest

Setter: Hasan Jaddouh
Tester: Misha Chorniy
Editorialist: Taranpreet Singh

DIFFICULTY:

Cakewalk

PREREQUISITES:

Sorting would be enough.

PROBLEM:

Given scores of N teams, and an integer K, the number of teams from the top to qualify, Find out number of teams qualify if in case of tie at Kth position, All teams tying with Kth team will also qualify.

SUPER QUICK EXPLANATION

  • Sort the scores, and count number of teams having score greater than or equal to Kth team. (Shortest explanation ever from my side :P)

EXPLANATION

As the problem statement itself mentions, Teams will be sorted in descending order by their score and Top K teams will be selected.

First of all, Assume that all scores are distinct. Now, we are sure that there won’t be any tie for Kth rank. Exactly K teams will qualify.

Now, when two or more teams can score same, either all of them will qualify, or none of them. So, we just need to find the score X such that all teams with score s[i] /geq X will qualify, while teams with s[i] < X will not.

We can see that X is actually the score of Kth team, if all teams are sorted by their score.

So, we can just sort the scores, find X and iterate over all elements, increasing answer by one whenever we see a team with s[i] \geq X.

Problems for Practice can be found here.

Time Complexity

Time complexity is O(N*logN) due to sorting. Iterating over the elements takes O(N) time.

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution
Tester’s solution
Editorialist’s solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile:

2

#include <bits/stdc++.h>

using namespace std;
vector semi;

int main(){
int x,t,i,N,K,no,count;
cin>>t;
vector::iterator m,k;

while(t){
    cin>>N>>K;
    for(int i=0;i<N;i++){
        cin>>x;
        semi.push_back(x);
    }

    sort(semi.rbegin(), semi.rend());
    int target = semi[K-1];
    count=0;
    for(int i=0;i<N;i++){
        
        if(semi[i]>=target){
            count++;
            break;
        }
    }
    
    cout<<no<<"\n";
    
    t--;
} 




return 0;

}

3

Why printing no, plus, why a break statement used?

Remove break statement. Print count.

4

for _ in range(int(input())):
a,b=map(int,input().split())
l=list(map(int,input().split()))
c=0
l.sort(reverse=True)
for i in range(b):
c+=l.count(l[i])
print©

can anyone tell whats wrong its always showing time exceed

5

import java.util.Scanner;
class CodeChef {
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc =new Scanner(System.in);
int t=sc.nextInt();
if( (t<1000) ||(t==1) ){
while(t–!=0) {
int n=sc.nextInt();
int k=sc.nextInt();
if( ( (k<=100000)|| (k>=1) )&&( (n>=1) || (n<=100000) ) ) {
int ar[]=new int[n];
for(int i=0;i<ar.length;i++) {
ar[i]=sc.nextInt();
}

    int[] result=reverse(ar);
    int jio=search(result,k);
    if(jio<1000000) {
    display1(jio);
    }
    }
    }
    }
	 sc.close();
}

	public static void display1(int c) {
		System.out.println(c);
		System.out.println(" ");
	}
public static int[] reverse(int[] ar) {
	int temp=0;
	int[] swap=new int[ar.length];
	for(int i=0;i<swap.length;i++) {
		swap[i]=ar[i];
	}
	for(int i=0;i<swap.length-1;i++) {
	for(int j=1;j<swap.length;j++) {
		if(swap[j]>=swap[j-1]) {
			temp=swap[j];
			swap[j]=swap[j-1];
			swap[j-1]=temp;
		}
	}
	}
	return swap;
}
public static int search(int[] ar,int k) {
	int[] sorry=new int[ar.length];
	int key=k,count=0;
	for(int i=0;i<sorry.length;i++) {
		sorry[i]=ar[i];
	}
	for(int i=0;i<sorry.length;i++) {
	if (sorry[i]>=sorry[key-1]) {
		count++;
	}
	else {
		break;
	}
	}
	return count;
}

}

6

plzz tell me… where i m getting wrong

7

Please help and find the error. I didnt find any.

/* package codechef; // don’t place package name! */

import java.util.;
import java.lang.;
import java.io.*;

/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static Scanner mScanner=new Scanner(System.in);
public static void main (String[] args) throws java.lang.Exception
{
try {

    int noTestCases=Integer.parseInt(mScanner.nextLine());
    int totalPlayers,selectionNumber;
    ArrayList<Integer> totalValues=new ArrayList<>();
    while(noTestCases-->0)
    {
        totalPlayers=Integer.parseInt(mScanner.nextLine());
        selectionNumber=Integer.parseInt(mScanner.nextLine());
        for(int i=0;i<totalPlayers;i++)
        {
            totalValues.add(Integer.parseInt(mScanner.nextLine()));
        }
        Collections.sort(totalValues,Collections.reverseOrder());
        int selectionValue=totalValues.get(selectionNumber-1);
        System.out.println(qualifiedPlayers(selectionValue,totalValues,selectionNumber-1));
    }   
    }catch(Exception e) {
    } 
	// your code goes here
}

public  static String qualifiedPlayers(int selectionValue,ArrayList<Integer> totalValues,int selectionIndex){
    boolean isContinue=true;
    while(isContinue){
        if(!totalValues.get(++selectionIndex).equals(selectionValue))
        {
            isContinue=false;
        }
    }
    return String.valueOf(selectionIndex);
}

}

8

int[] result=reverse(ar);
int jio=search(result,k);
if(jio<1000000) {
display1(jio);
}
}
}
}
sc.close();
}

public static void display1(int c) {
    System.out.println(c);
    System.out.println(" ");
}

public static int[] reverse(int[] ar) {
int temp=0;
int[] swap=new int[ar.length];
for(int i=0;i<swap.length;i++) {
swap[i]=ar[i];
}
for(int i=0;i<swap.length-1;i++) {
for(int j=1;j<swap.length;j++) {
if(swap[j]>=swap[j-1]) {
temp=swap[j];
swap[j]=swap[j-1];
swap[j-1]=temp;
}
}
}
return swap;
}
public static int search(int[] ar,int k) {
int[] sorry=new int[ar.length];
int key=k,count=0;
for(int i=0;i<sorry.length;i++) {
sorry[i]=ar[i];
}
for(int i=0;i<sorry.length;i++) {
if (sorry[i]>=sorry[key-1]) {
count++;
}
else {
break;
}
}
return count;
}
}