AVGFLEX - Editorial

PROBLEM LINK:

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

Author: Jeevan Jyot Singh
Tester: Danny Mittal
Editorialist: Nishank Suresh

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

You are given the marks of N students in a class, where the i-th student scores A_i. Student i will boast if and only if the number of students scoring less than or equal to A_i is strictly larger than the number of students scoring more than A_i.

Find the number of students who will boast.

EXPLANATION:

The constraints are fairly low, so several different solutions pass. A couple are detailed below.

Solution 1

N is small a simple brute-force passes: for every student i, iterate over all students j and check whether A_j \leq A_i or not. This gives us an \mathcal{O}(N^2) solution.

Solution 2

The A_i are small, so a modification of the first solution which runs in \mathcal{O}(N\max A) also works.

To do this, we maintain a frequency table f of marks, where f_i denotes the number of students who scored exactly i marks.
Then, for a given student i, iterate over all marks and find the sum of f_j where j\leq A_i - let this be S. Comparing S with n - S will tell us whether student i boasts or not.

This can be further improved to \mathcal{O}(N + maxA) by prefix sums - after building the frequency table f, build its prefix sums so that we have f_i being the count of students whose marks are \leq i. Then, for a student i all that needs to be done is to compare f_{A_i} and n - f_{A_i}.

TIME COMPLEXITY:

\mathcal{O}(N^2)/\mathcal{O}(N\max A)/\mathcal{O}(N + \max A) depending on implementation.

CODE:

Setter (C++)
#ifdef WTSH
    #include <wtsh.h>
#else
    #include <bits/stdc++.h>
    using namespace std;
    #define dbg(Z...)
#endif

#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define int long long
#define endl "\n"
#define sz(w) (int)(w.size())
using pii = pair<int, int>;

const double EPS = 1e-9;
const long long INF = 1e18;

const int N = 1e6+5; 

void solve()
{
    int n; cin >> n;
    vector<int> freq(101);
    for(int i = 0; i < n; i++)
    {
        int x; cin >> x;
        freq[x]++;
    }
    int ans = 0, cnt = 0;
    for(int i = 0; i <= 100; i++)
    {
        cnt += freq[i];
        if(cnt > n-cnt)
            ans += freq[i];
    }
    cout << ans << endl;
}

int32_t main()
{
    IOS;
    int T; cin >> T;
    for(int tc = 1; tc <= T; tc++)
    {
        // cout << "Case #" << tc << ": ";
        solve();
    }
    return 0;
}
Tester (Kotlin)
import java.io.BufferedInputStream

fun main(omkar: Array<String>) {
    val jin = FastScanner()
    repeat(jin.nextInt(1000)) {
        val n = jin.nextInt(1000)
        val freq = IntArray(101)
        for (j in 0 until n) {
            freq[jin.nextInt(0, 100, j == n - 1)]++
        }
        var answer = 0
        for (x in 0..100) {
            if ((0..x).sumBy { freq[it] } > (x + 1..100).sumBy { freq[it] }) {
                answer += freq[x]
            }
        }
        println(answer)
    }
    jin.assureInputDone()
}

class FastScanner {
    private val BS = 1 shl 16
    private val NC = 0.toChar()
    private val buf = ByteArray(BS)
    private var bId = 0
    private var size = 0
    private var c = NC
    private var `in`: BufferedInputStream? = null

    constructor() {
        `in` = BufferedInputStream(System.`in`, BS)
    }

    private val char: Char
        private get() {
            while (bId == size) {
                size = try {
                    `in`!!.read(buf)
                } catch (e: Exception) {
                    return NC
                }
                if (size == -1) return NC
                bId = 0
            }
            return buf[bId++].toChar()
        }

    fun assureInputDone() {
        if (char != NC) {
            throw IllegalArgumentException("excessive input")
        }
    }

    fun nextInt(endsLine: Boolean): Int {
        var neg = false
        c = char
        if (c !in '0'..'9' && c != '-' && c != ' ' && c != '\n') {
            throw IllegalArgumentException("found character other than digit, negative sign, space, and newline")
        }
        if (c == '-') {
            neg = true
            c = char
        }
        var res = 0
        while (c in '0'..'9') {
            res = (res shl 3) + (res shl 1) + (c - '0')
            c = char
        }
        if (endsLine) {
            if (c != '\n') {
                throw IllegalArgumentException("found character other than newline")
            }
        } else {
            if (c != ' ') {
                throw IllegalArgumentException("found character other than space")
            }
        }
        return if (neg) -res else res
    }

    fun nextInt(from: Int, to: Int, endsLine: Boolean = true): Int {
        val res = nextInt(endsLine)
        if (res !in from..to) {
            throw IllegalArgumentException("$res not in range $from..$to")
        }
        return res
    }

    fun nextInt(to: Int, endsLine: Boolean = true) = nextInt(1, to, endsLine)
}
Editorialist (C++)
#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,mmx,avx,avx2")
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);

    int t; cin >> t;
    while (t--) {
        int n ;cin >> n;
        vector<int> v(n);
        for (int &x : v)
            cin >> x;
        sort(begin(v), end(v));
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            int d = upper_bound(begin(v), end(v), v[i]) - begin(v);
            ans += d > n-d;
        }
        cout << ans << '\n';
    }
}
1 Like

Can you explain test case for 3 students scoring [2 1 3] .

4 Likes

Well, find the median of the list, see where it lies in the sorted list (required for finding the median) and (1) count the number of scores greater than or equal to, or (2) find its index and calculate the {length of the list} - {this index}.

This is the fastest solution.

from sys import stdin
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	a = sorted(map(int, stdin.readline().split()))
	q = max(a, key=lambda x:x>=a[n//2])
	print (n-a.index(q))

See my solution below. Just a simple median calculation.