×

# QUALPREL - EDITORIAL

Tester: Misha Chorniy
Editorialist: Taranpreet Singh

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:

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

This question is marked "community wiki".

3.9k2791
accept rate: 22%

19.8k350498541

# include <bits stdc++.h="">

using namespace std; vector<int> semi;

int main(){ int x,t,i,N,K,no,count; cin>>t; vector<int>::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;


}

2★vjjxx3
1
accept rate: 0%

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

Remove break statement. Print count.

(18 Oct '18, 13:16)
 0 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(c) can anyone tell whats wrong its always showing time exceed answered 28 Oct '18, 21:34 2★gvp777 1 accept rate: 0%
 0 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=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[key-1]) { count++; } else { break; } } return count; }  } answered 05 Jan, 14:55 1★anithya 1 accept rate: 0% plzz tell me.. where i m getting wrong (05 Jan, 14:56) anithya1★
 0 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 totalValues=new ArrayList<>(); while(noTestCases-->0) { totalPlayers=Integer.parseInt(mScanner.nextLine()); selectionNumber=Integer.parseInt(mScanner.nextLine()); for(int i=0;i totalValues,int selectionIndex){ boolean isContinue=true; while(isContinue){ if(!totalValues.get(++selectionIndex).equals(selectionValue)) { isContinue=false; } } return String.valueOf(selectionIndex); }  } answered 28 Jan, 00:02 0★drdang 1●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×1,643
×785
×649
×29
×3

question asked: 13 Oct '18, 04:28

question was seen: 1,568 times

last updated: 28 Jan, 00:04