PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter:
Tester: Istvan Nagy
Editorialist: Taranpreet Singh
DIFFICULTY
Simple
PREREQUISITES
None
PROBLEM
Given scores associated with K problems, and the information about the solved problems by each participant, compute the score of each participant.
QUICK EXPLANATION
The problem score is added to participant score only if the participant has solved that problem.
EXPLANATION
This is an implementation problem. We can store the problem scores in an array, and for each participant, consider all problems one by one.
If at position i, 1 appears, participant has solved this problem, hence the score of that problem is added to participant score.
Hence, we can deal with each participant separately, initialize participant score as zero, and iterate over problems, updating participant score for every solved problem.
To ease with implementation, you can store problem scores in an array.
Following is the code in brief
score = 0
problemScore = #array storing score of each problem, zero based indexing
solved = #binary string given in input
for problem in range(0, N):
if solved[problem] == '1':
solved += problemScore[problem]
Exercize
- Can you solve above problem without using any if condition?
- Can you solve above problem without using any if condition as well as ternary operator?
TIME COMPLEXITY
The time complexity is O(N*K) per test case.
The memory complexity is O(K) per test case.
SOLUTIONS
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
const int maxsz = 1e6, maxsc = 1e5, maxt = 5;
int main()
{
int t; cin >> t;
int tot = 0;
while(t--){
int n, k; cin >> n >> k; tot += n * k;
int score[k + 1];
for(int i = 1; i <= k; i++)cin >> score[i];
long long ans[n + 1]; memset(ans, 0, sizeof(ans));
for(int i = 1; i <= n; i++){
string rs; cin >> rs;
for(int j = 1; j <= k; j++){
if(rs[j - 1] - '0')ans[i] += score[j];
}
}
for(int i = 1; i <= n; i++){
cout << ans[i] << endl;
}
}
assert(tot <= maxsz);
}
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;
}
// if(g == '\r')
// continue;
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("../TOTSCR_0.in", "rb", stdin);
freopen("../out.txt", "wb", stdout);
}
#endif
int T = readIntLn(1, 5);
int sumN = 0, sumK = 0, sumNK=0;
forn(tc, T)
{
int N = readIntSp(1, 1'000'000);
int K = readIntLn(1, 1'000'000);
sumN += N;
sumK += K;
sumNK += K * N;
vector<int> A;
forn(i, K)
{
if (i + 1 < K)
{
int tmp = readIntSp(1, 100'000);
A.push_back(tmp);
}
else
{
int tmp = readIntLn(1, 100'000);
A.push_back(tmp);
}
}
assert(N * K <= 1'000'000);
forn(i, N)
{
string tmp = readStringLn(K, K);
uint64_t res = 0;
forn(j, K)
{
if (tmp[j] == '1')
{
res += A[j];
}
else
{
assert(tmp[j] == '0');
}
}
printf("%llu\n", res);
}
}
assert(sumNK <= 1'000'000);
assert(getchar() == -1);
return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class TOTSCR{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int N = ni(), K = ni();
int[] problemScore = new int[K];
for(int i = 0; i< K; i++)problemScore[i] = ni();
for(int participant = 1; participant <= N; participant++){
long score = 0;
String solved = n();
for(int problem = 0; problem < K; problem++)if(solved.charAt(problem) == '1')score += problemScore[problem];
pn(score);
}
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new TOTSCR().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always. 