# JAVELIN - Editorial

Author: Daanish Mahajan
Tester : Radoslav Dimitrov
Editorialist: Aman Dwivedi

Cakewalk

None

# PROBLEM:

There are N players with IDs from 1 to N, who are participating in the Javelin throw competition which has two rounds. The first is the qualification round, followed by the final round. The qualification round has gotten over, and you are given the longest distance that each of the N players has thrown as A_1, A_2, \ldots, A_N. Now, the selection process for the final round happens in the following two steps:

1. If the longest throw of a player in the qualification round is greater than or equal to the qualification mark of M cm, they qualify for the final round.

2. If after step 1, less than X players have qualified for the finals, the remaining spots are filled by players who have thrown the maximum distance among the players who have not qualified yet.

You are given the best throws of the N players in the qualification round A_1, A_2, \ldots, A_N and the integers M and X. Print the list of the players who will qualify for the finals in increasing order of their IDs.

# EXPLANATION:

The problem is straightforward, we need to do as the problem statement says. Simply sort the array in decreasing order of the distance remembering the ID of the players with their distance.

Now after that, start traversing the array there are two conditions when a player can be qualified for the finals:

• If the playerâ€™s throw distance is more than the qualification mark M, he simply qualifies for the final.

• If the playerâ€™s throw distance is less than the qualification mark M but the number of players in the final is less than X, the player qualifies for the final.

We can simply push the IDs of the players that are qualified for the finals. Since we need IDs of the qualified players in increasing order, we can sort the array which contains the qualified players ID and print this list.

# TIME COMPLEXITY:

O(N*log(N)) per test case

# SOLUTIONS:

Author
``````#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define rb pop_back
#define ti tuple<int, int, int>
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define mp make_pair
#define mt make_tuple

using namespace std;

const int maxt = 1000;
const string newln = "\n", space = " ";
const int minm = 5000, maxm = 8000;

int main()
{
int t, n, m, x, y;
cin >> t;
while(t--){
cin >> n >> m >> x;
vector<pii> v;
for(int i = 0; i < n; i++){
cin >> y;
v.pb({y, i + 1});
}
sort(v.begin(), v.end(), greater<pii>());
int cnt = 0;
vector<int> ans;
for(pii p : v){
if(p.first >= m){
ans.pb(p.second); cnt++;
}else{
if(cnt < x){
ans.pb(p.second); cnt++;
}else{
break;
}
}
}
sort(ans.begin(), ans.end());
int sz = ans.size();
cout << sz << " ";
for(int i = 0; i < sz; i++){
cout << ans[i] << (i == sz - 1 ? newln : space);
}
}
}
``````
Tester
``````def solve_case():
n, m, k = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]

with_ids = [(x, i + 1) for i, x in enumerate(a)]

for v, i in sorted(with_ids, reverse=True):
if len(answer) < k or v >= m:

cases = int(input())
for _ in range(cases):
solve_case()

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

void solve()
{
int n,m,x;
cin>>n>>m>>x;

int a[n];

vector <int> ans;

for(int i=0;i<n;i++)
{
cin>>a[i];
if(a[i]>=m)
{
ans.push_back(i+1);
a[i]=-1;
}
}

while(ans.size()<x)
{
int idx = 0;
int fi_idx = 0;

while(idx<n)
{
if(a[idx]>a[fi_idx])
fi_idx = idx;

idx++;
}

ans.push_back(fi_idx+1);
a[fi_idx] = -1;
}

sort(ans.begin(),ans.end());

cout<<ans.size()<<" ";

for(auto itr: ans)
cout<<itr<<" ";

cout<<endl;
}

int main()
{
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);

int t;
cin>>t;

while(t--)
solve();
}

``````

Why This is not working. Can anyone help?

``````// Don't Just copy the code, Understand it first.
// -- theskyspace(Insta profile also) ;)

#include <bits/stdc++.h>
using namespace std;
#define deb(x) cout << #x << " = " << x << endl;
#define deb2(x,y) cout << #x << " = " << x << " , " << #y << " = " << y << endl;
typedef long long ll;

ll M = 10e8 + 7;

bool sortbysec(const pair<int,int> &a,
const pair<int,int> &b)
{
return (a.second < b.second);
}

void solve(){
// Let's start
int n, m , x;
cin >> n >> m >> x;
vector<pair<int,int>> a;
vector<pair<int,int>> q;

for (int i = 0; i < n; i++)
{
int j;
cin >> j;
if(j >= m){
q.push_back({j , i+1});
}
else
{
a.push_back({j , i+1});
}
}

// Runs only if X players are not selected.s
if(q.size() < x){
sort(a.begin() ,  a.end() , greater<pair<int, int>>());
for (int i = 0; i <= x-q.size(); i++)
{
q.push_back(a[i]);
}
}

sort(q.begin(), q.end(), sortbysec);
cout << q.size();
for(auto x:q){
cout << " " << x.second;
}
cout << endl;

}

//Driver's code
int main(){
// Stdin and stdout.
ios::sync_with_stdio(false);
cin.tie(0);

#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif

int t;
cin >> t;
while(t--){
solve();
}

return 0;
}
``````

Here is a test case for which your code fails

1
4 6002 3
5999 5998 6000 6001

Correct Answer:- 3 1 3 4
Your Output:- 2 3 4

Here is a code with slight logical change in yours one which got AC.

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

Happy Codingâ€¦

Thatâ€™s Not The correct output friend

2 Likes

What I think is that this section of your code is wrong. Suppose x - q.size() is 1 , then practically you need to add 1 more person. But your loop if running 2 time ( i = 0 , i = 1) . So the constraint in the loop should be for ( int i = 0 ; i < q.size() ; i++). This should work I guess.
The content structure of the provided text is an editorial for a competitive programming problem. It includes the problem statement, explanation, time complexity, and solutions in different programming languages.
no_question

the text does not contain a mathematical question or provide an answer to one. it is a detailed explanation and solution to a programming problem.
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# JAVELIN - Editorial

Author: Daanish Mahajan
Tester : Radoslav Dimitrov
Editorialist: Aman Dwivedi

Cakewalk

None

# PROBLEM:

There are N players with IDs from 1 to N, who are participating in the Javelin throw competition which has two rounds. The first is the qualification round, followed by the final round. The qualification round has gotten over, and you are given the longest distance that each of the N players has thrown as A_1, A_2, \ldots, A_N. Now, the selection process for the final round happens in the following two steps:

1. If the longest throw of a player in the qualification round is greater than or equal to the qualification mark of M cm, they qualify for the final round.

2. If after step 1, less than X players have qualified for the finals, the remaining spots are filled by players who have thrown the maximum distance among the players who have not qualified yet.

You are given the best throws of the N players in the qualification round A_1, A_2, \ldots, A_N and the integers M and X. Print the list of the players who will qualify for the finals in increasing order of their IDs.

# EXPLANATION:

The problem is straightforward, we need to do as the problem statement says. Simply sort the array in decreasing order of the distance remembering the ID of the players with their distance.

Now after that, start traversing the array there are two conditions when a player can be qualified for the finals:

• If the playerâ€™s throw distance is more than the qualification mark M, he simply qualifies for the final.

• If the playerâ€™s throw distance is less than the qualification mark M but the number of players in the final is less than X, the player qualifies for the final.

We can simply push the IDs of the players that are qualified for the finals. Since we need IDs of the qualified players in increasing order, we can sort the array which contains the qualified players ID and print this list.

# TIME COMPLEXITY:

O(N*log(N)) per test case

# SOLUTIONS:

Author
``````#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define rb pop_back
#define ti tuple<int, int, int>
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define mp make_pair
#define mt make_tuple

using namespace std;

const int maxt = 1000;
const string newln = "\n", space = " ";
const int minm = 5000, maxm = 8000;

int main()
{
int t, n, m, x, y;
cin >> t;
while(t--){
cin >> n >> m >> x;
vector<pii> v;
for(int i = 0; i < n; i++){
cin >> y;
v.pb({y, i + 1});
}
sort(v.begin(), v.end(), greater<pii>());
int cnt = 0;
vector<int> ans;
for(pii p : v){
if(p.first >= m){
ans.pb(p.second); cnt++;
}else{
if(cnt < x){
ans.pb(p.second); cnt++;
}else{
break;
}
}
}
sort(ans.begin(), ans.end());
int sz = ans.size();
cout << sz << " ";
for(int i = 0; i < sz; i++){
cout << ans[i] << (i == sz - 1 ? newln : space);
}
}
}
``````
Tester
``````def solve_case():
n, m, k = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]

with_ids = [(x, i + 1) for i, x in enumerate(a)]

for v, i in sorted(with_ids, reverse=True):
if len(answer) < k or v >= m:

cases = int(input())
for _ in range(cases):
solve_case()

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

void solve()
{
int n,m,x;
cin>>n>>m>>x;

int a[n];

vector <int> ans;

for(int i=0;i<n;i++)
{
cin>>a[i];
if(a[i]>=m)
{
ans.push_back(i+1);
a[i]=-1;
}
}

while(ans.size()<x)
{
int idx = 0;
int fi_idx = 0;

while(idx<n)
{
if(a[idx]>a[fi_idx])
fi_idx = idx;

idx++;
}

ans.push_back(fi_idx+1);
a[fi_idx] = -1;
}

sort(ans.begin(),ans.end());

cout<<ans.size()<<" ";

for(auto itr: ans)
cout<<itr<<" ";

cout<<endl;
}

int main()
{
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);

int t;
cin>>t;

while(t--)
solve();
}

``````

Why This is not working. Can anyone help?

``````// Don't Just copy the code, Understand it first.
// -- theskyspace(Insta profile also) ;)

#include <bits/stdc++.h>
using namespace std;
#define deb(x) cout << #x << " = " << x << endl;
#define deb2(x,y) cout << #x << " = " << x << " , " << #y << " = " << y << endl;
typedef long long ll;

ll M = 10e8 + 7;

bool sortbysec(const pair<int,int> &a,
const pair<int,int> &b)
{
return (a.second < b.second);
}

void solve(){
// Let's start
int n, m , x;
cin >> n >> m >> x;
vector<pair<int,int>> a;
vector<pair<int,int>> q;

for (int i = 0; i < n; i++)
{
int j;
cin >> j;
if(j >= m){
q.push_back({j , i+1});
}
else
{
a.push_back({j , i+1});
}
}

// Runs only if X players are not selected.s
if(q.size() < x){
sort(a.begin() ,  a.end() , greater<pair<int, int>>());
for (int i = 0; i <= x-q.size(); i++)
{
q.push_back(a[i]);
}
}

sort(q.begin(), q.end(), sortbysec);
cout << q.size();
for(auto x:q){
cout << " " << x.second;
}
cout << endl;

}

//Driver's code
int main(){
// Stdin and stdout.
ios::sync_with_stdio(false);
cin.tie(0);

#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif

int t;
cin >> t;
while(t--){
solve();
}

return 0;
}
``````

Here is a test case for which your code fails

1
4 6002 3
5999 5998 6000 6001

Correct Answer:- 3 1 3 4
Your Output:- 2 3 4

Here is a code with slight logical change in yours one which got AC.

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

Happy Codingâ€¦

Thatâ€™s Not The correct output friend

2 Likes

What I think is that this section of your code is wrong. Suppose x - q.size() is 1 , then practically you need to add 1 more person. But your loop if running 2 time ( i = 0 , i = 1) . So the constraint in the loop should be for ( int i = 0 ; i < q.size() ; i++). This should work I guess.
user
The content structure of the provided text is an editorial for a competitive programming problem. It includes the problem statement, explanation, time complexity, and solutions in different programming languages.

TYPE: NO_QUESTION

The text does not contain a mathematical question or provide an answer to one. It is a detailed explanation and solution to a programming problem.