JAVELIN - Editorial

PROBLEM LINK:

Practice
Contest: Division 3
Contest: Division 2
Contest: Division 1

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

DIFFICULTY:

Cakewalk

PREREQUISITES:

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)]
    
    answer = []
    for v, i in sorted(with_ids, reverse=True):
        if len(answer) < k or v >= m:
            answer.append(i)

    print(len(answer), *sorted(answer))

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.