Editorial of MindCoding 2017 Round 1 (Div. 1)

250 - SpeedV2

350 - Morse

For every word we will do the following:
Let's say we are at word W(i). We compute its morse encoding and using a mapping from morseEncoding to number of apparitions, we will keep track of how many times a morse encoding appeared in the dictionary.
So at step i we will increment the number of apparitions of the morse encoding we obtained from W(i) where i=1...n. In order the manage this mapping we can use a hash table that maps strings to integers. We can then compute the answer by iterating through the values of the hash.
If there are no collisions, we print -1.
#include <iostream>
#include <stdio.h>
#include <unordered_map>
#include <vector>

using namespace std;

int main() {
    int n, ans = 0;
    vector <string> d;
    unordered_map<char, string> repr;
    unordered_map<string, int> cnt;
    for(int i = 0; i < 26; ++ i) {
        char ch;
        string code;
        cin >> ch >> code;
        repr[ch] = code;
    }
    cin >> n;
    for(int i = 0; i < n; ++ i) {
        string word;
        cin >> word;
        string morse = "";
        for(auto ch : word)
            morse = morse + repr[ch];
        ans = max(ans, ++ cnt[morse]);
    }
    if(ans == 1)
        cout << -1 << '\n';
    else
        cout << ans << '\n';
    return 0;
}

600 - Zombie

The problem requires you to count the number of surjections defined on a domain of cardinal N and codomain of cardinal M and multiply it by the number of derangements of M.

In order to count this we use Inclusion-Exclusion Principle in the following way:
Sum(K <- 0, M) (M choose K) * (M - K) ^ N * (-1) ^ K. We basically choose out of the M elements of the codomain, which of them we don't map anything to and then map the N elements of the domain in all the possible ways to the remainig (M - K) elements of the codomain. To count the number of derangements we can use again the principle of inclusion and exclusion. N! - AtLeastOneElementMappedCorrectly is the number of derangements. To count the number of ways we can map at least 1 element correctly, we use IEP in the following way: Sum(K <- 1, M) (M choose K) * (M - K)!. We basically choose at any step K out of the M elements to be mapped correctly and permute the remaining (M - K) elements. Complexity: O(M + M log MOD) = O(M)

800 - Exploding Kittens

We first observe that the problem is independent for each dimension.
Therefore we should solve the problem in a 1 dimensional space and the same principle applies to all dimensions.
For the 1D problem, we sort the elements in ascending order of the (only) coordinate and then we can use partial sums to the left and to the right to compute the manhattan distance from one point to all the others in O(M) in total. We just need to take care that we add the manhattan distance to the correct initial point (as the order may differ when sorting on different axis).
Therefore the algorithm is O(N * M * logM) orO(N * M) using the integer property of coordinates and radix / bucket sort.

Questions?

Sponsors Gold