TOTCRT - Editorial

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.

1 Like

Is it possible to solve this problem using 3D vectors where A[i][j][0] is problem code and A[i][j][1] is total solutions?