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';
}
}