#Hashtable

Solutions Warning: the problem I/O might result slow. For some languages (e.g. C++), it’s better off reading the whole input first. This problem requires some additional storage to be solved efficiently. Using only one hash map is not enough because of operation of type 3. The idea is to use a hash map to store the frequencies of each element (query type 1 and 2) and also an additional hash map “histogram”, that is an inverse map from frequency to elements having such a frequency. [Read More]

Solutions For each possible character, we can check if it’s present in all rocks. A Python solution by Yuri Valentini. 1 2 3 4 5 6 7 8 9 10 11 import sys from functools import reduce n = int(input().strip()) rock = [] rock_i = 0 for rock_i in range(n): rock_t = str(input().strip()) rock.append(frozenset(rock_t)) inters = reduce((lambda a,b: a & b), rock) print(len(inters)) Another one: 1 print(len(set.intersection(*[set(input()) for _ in range(int(input()))]))) Another one in C#: [Read More]

Solutions Array The domain is limited to \( 10^5 \), so we can waste some memory to keep the last position of a value. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include <iostream> #include <map> int main() { std::array<int, 100001> pos; pos.fill(-1); std::array<int, 100001> dist; dist. [Read More]

You will be given an array of integers and a target value. Determine the number of pairs of array elements that have a difference equal to a target value.

[Read More]

Summer is over and people at Gugol are sad and unmotivated. They would prefer going back on vacation instead of working - how to blame them? Ted, head of employee happiness department, has got an idea to cheer people up: he will run a lottery among all the employees and will award the luckiest one with two extra weeks of vacation. The lottery will work this way: Ted will raffle off some ranges of employee ids like \( [120, 200] \) and \( [150, 180] \), a sophisticated algorithm will calculate which is the most frequent employee id in all such ranges, if more than one such an id exists, the sophisticated algorithm will select the smallest one - it corresponds to the employee who has been working at Gugol for more time You are a \( \cancel{slave} \) trainee at Gugol and you have to design and write such a sophisticated algorithm. [Read More]

You are given an array of N integers separated by spaces, all in one line. Display the element which occurs most frequently. If multiple elements satisfy this criteria, display the numerically smallest one. Input Format The first line contains the number of integers \(N\). The second line contains space separated integers \(xi\) for which you need to find the most frequent one. Constraints \(10 \leq N \leq 1'000'000 \) \(0 \leq xi \leq 100'000 \) Output Format One line containing the result. [Read More]