PROBLEM LINK:
Practice
Contest: Division 3
Contest: Division 2
Contest: Division 1
Author: Smit Mandavia, Daanish Mahajan
Tester: Istvan Nagy
Editorialist: Vichitr Gandas
DIFFICULTY:
SIMPLE
PREREQUISITES:
HashMaps, Sorting
PROBLEM:
CodeChef challenges has 3 divisions. Given a list of N problem codes and the number of correct solutions in each division. Find the total number of correct solutions for each problem.
EXPLANATION
Just find the sum of number of submissions over all divisions for every unique problem. Maintain a map M where key is problem name and value stores number of submissions. So iterate over all problems in each division and for each problem P, add the number of submissions S to the map ie. M[P] = M[P] + S.
At the end, just put all map values in separate array or vector, sort and print it.
TIME COMPLEXITY:
O(N + KlogK) where K is number of unique problems over all divisions.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e4, minv = 1, maxv = 5e8, maxt = 10;
const string newln = "\n", space = " ";
int main()
{
int t; cin >> t;
map<string, int> m; vector<int> v;
while(t--){
m.clear();
int n; cin >> n;
string s; int x;
for(int i = 0; i < 3 * n; i++){
cin >> s >> x;
for(int j = 0; j < s.length(); j++){
assert(s[j] >= 'A' && s[j] <= 'Z');
}
m[s] += x;
}
v.clear();
for(auto val : m){
v.push_back(val.second);
}
sort(v.begin(), v.end());
for(int i = 0; i < v.size(); i++)cout << v[i] << (i == v.size() - 1 ? newln : space);
}
}
Tester's Solution
#include <iostream>
#include <cassert>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <random>
#ifdef HOME
#include <windows.h>
#endif
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }
using namespace std;
long long readInt(long long l, long long r, char endd) {
long long x = 0;
int cnt = 0;
int fi = -1;
bool is_neg = false;
while (true) {
char g = getchar();
if (g == '-') {
assert(fi == -1);
is_neg = true;
continue;
}
if ('0' <= g && g <= '9') {
x *= 10;
x += g - '0';
if (cnt == 0) {
fi = g - '0';
}
cnt++;
assert(fi != 0 || cnt == 1);
assert(fi != 0 || is_neg == false);
assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
}
else if (g == endd) {
assert(cnt > 0);
if (is_neg) {
x = -x;
}
assert(l <= x && x <= r);
return x;
}
else {
//assert(false);
}
}
}
string readString(int l, int r, char endd) {
string ret = "";
int cnt = 0;
while (true) {
char g = getchar();
assert(g != -1);
if (g == endd) {
break;
}
cnt++;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}
long long readIntSp(long long l, long long r) {
return readInt(l, r, ' ');
}
long long readIntLn(long long l, long long r) {
return readInt(l, r, '\n');
}
string readStringLn(int l, int r) {
return readString(l, r, '\n');
}
string readStringSp(int l, int r) {
return readString(l, r, ' ');
}
int main(int argc, char** argv)
{
#ifdef HOME
if(IsDebuggerPresent())
{
freopen("../in.txt", "rb", stdin);
freopen("../out.txt", "wb", stdout);
}
#endif
int T = readIntLn(1, 10);
forn(tc, T)
{
int N = readIntLn(1, 20'000);
map<string, int> mi;
forn(i, 3*N)
{
string a = readStringSp(1, 8);
int b = readIntLn(1, 500'000'000);
mi[a] += b;
}
vector<int> res;
for (auto mv : mi)
res.push_back(mv.second);
sort(res.begin(), res.end());
forn(i, res.size())
{
printf("%d ", res[i]);
}
printf("\n");
}
//assert(getchar() != -1);
return 0;
}
Editorialist's Solution
/*
* @author: vichitr
* @date: 26th June 2021
*/
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
map<string, int> M;
for (int i = 0; i < n * 3; i++) {
string s; int c;
cin >> s >> c;
M[s] += c;
}
vector<int> submissions;
for (auto i : M) {
submissions.push_back(i.second);
}
sort(submissions.begin(), submissions.end());
for (int s : submissions)
cout << s << ' ';
cout << '\n';
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}
VIDEO EDITORIAL:
If you have other approaches or solutions, let’s discuss in comments.