Editorial for DMOPC '19 Contest 5 P1 - Conspicuous Cryptic Checklist - Olympiads Online Judge

Editorial for DMOPC '19 Contest 5 P1 - Conspicuous Cryptic Checklist

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Tzak

For each of the $T_i$ $T_{i}$ items in the $M$ $M$ lists of items required for the upcoming assignments, check if each item exists in the original list by iterating over it. This process can be made easier and faster through the use of a built-in data structure such as std::set in C++.

Pseudocode:

Copy

read N, M
read original_list
answer is 0
do M times
    read T_i, required_list
    ok is true
    for item in required_list
        if item not in original_list ok is false
    if ok add 1 to answer
print answer

Time complexity: $\mathcal{O}(MT_i|s_i|N)$ $O (M T_{i} | s_{i} | N)$ or $\mathcal{O}(MT_i|s_i|\log N)$ $O (M T_{i} | s_{i} | \log N)$

Comments

There are no comments at the moment.