FRNDCLAS-Editorial

editorial
, , , ,
1

PROBLEM LINK:

Contest

Author: Prathamesh Fulkari
Tester: Sarthak Chafle
Editorialist: Prathamesh Fulkari

DIFFICULTY:

SIMPLE-EASY

PREREQUISITES:

set or map (dictionary for python)

PROBLEM:

Given names of N students and Q lines, each having names of two students indicating both are friends, determine whether the classroom is “Friendly Classroom”. If not, output all the names of students who have no friends.
“Friendly Classroom” is a classroom with every student having at least one friend in the classroom.

QUICK EXPLANATION:

Set can be used to store the names of students who are friend with any students. Those students who are not in the set but in the list of names, print them. If there are no such students print “Friendly Classroom”.

EXPLANATION:

(Given explanation is considering solution in C++)
There are N students and Q lines, each having names of two students indicating both are friends. We can store N names in a vector of strings (say names). If we closely observe, the names which are not in Q lines form our answer since they are not friends with any other student. The names can have duplicates in the Q lines. To remove the duplicates we can use set (a data structure having only unique elements). We will store each name from Q lines in the set (say friends). Now, this set forms a container having names that are friends with at least one student. Our final answer is the names that are in names but not in the friends ( if both the names and friends containers have the same size means that there are no such names and hence we will simply output “Friendly Classroom” ). To find those names we will traverse the names container and find if each name is in the friends container or not (find() method can be used here for C++). If not, we will push that name in the answer container. The answer container forms our final answer but we need to print the names in lexicographically sorted order. Hence, we will sort the answer container and output it.

SOLUTIONS:

Setter's Solution 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while (t--) {
        ll n, q;
        cin >> n >> q;

        vector < string > names(n), answer;
        set < string > friends;

        for (int i = 0; i < n; i++) cin >> names[i];

        string friend1, friend2;
        while (q--) {
            cin >> friend1 >> friend2;
            friends.insert(friend1);
            friends.insert(friend2);
        }

        if (names.size() == friends.size())
            cout << "Friendly Classroom\n";
        else {
            for (int i = 0; i < n; i++) {
                if (friends.find(names[i]) == friends.end())
                    answer.push_back(names[i]);
            }
            sort(answer.begin(), answer.end());
            for (auto name: answer)
                cout << name << " ";
            cout << "\n";
        }
    }
    return 0;
}
Tester's Solution 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n, q;
        int flag = 0;
        string a, b, name;
        cin >> n >> q;
        map < string, int > mp;
        for (int i = 0; i < n; i++) {
            cin >> name;
            mp.insert({name,1});
        }
        while (q--) {
            cin >> a >> b;
            mp[a]++;
            mp[b]++;
        }
        for (auto i: mp) {
            if (i.second == 1) {
                flag = 1;
                cout << i.first << " ";
            }
        }
        if (!flag) {
            cout << "Friendly Classroom";
        }
        cout << "\n";
    }
    return 0;
}

TIME-COMPLEXITY:

( n logn * maximum length of name )

2 Likes