#sort

Given two unsorted arrays arr1 and arr2 - possibly containing duplicates - for each element in arr1 print the number of elements less than or equal to it in array arr2. Input Format The first line contains an integer N. Two lines follow: the first array: N space-separated elements the second array: N space-separated elements Constraints N and M are at most 100'000 Each array element is at least 0 and at most 100'000. [Read More]

Solutions We can find the answer by sorting one of the arrays in ascending order and the other in descending order. Then we check if the sum of all elements in pairs is greater than or equal to \(K\). It’s a greedy algorithm and its proof is left to the reader (see here). In C++: 1 2 3 4 5 6 7 8 sort(begin(v1), end(v1)); sort(begin(v2), end(v2), greater<int>()); bool ok = true; for (auto i=0; i<N && ok; ++i) { ok = (v1[i]+v2[i])>=K; } cout << (ok ? [Read More]

Solutions Sorting A C++ solution based on sorting and a sliding window made of two increasing pointers: 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 35 36 #include <numeric> #include <array> #include <vector> #include <iostream> #include <algorithm> #include <iterator> using namespace std; int main() { int n; cin >> n; vector<int> v(n); copy_n(istream_iterator<int>(cin), n, begin(v)); sort(begin(v), end(v)); auto selected = 0; auto tail = begin(v); auto head = next(tail); while (head ! [Read More]

Solutions This problem looks like a classical puzzle: merging overlapping intervals. A naive approach is \(O(N^2)\) and consists in checking each route with the others. In case they overlap, remove the other route from the array and merge both into the first one. The crucial condition to check if two routes overlap is (assuming route1 precedes route2): 1 route1.end >= route2.begin For example: 1 2 3 1 5 3 6 10 32 1 5 overlaps with 3 6, indeed 5 >= 3. [Read More]

Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order, in linear time. Input Format The first line contains N, the length of the array. The second line contains N space-separated integers, the elements of the array. Constraints \(1 \leq N \leq 10^6\) \(-10^3 \leq A[i] \leq 10^3\) Output Format Print the array of the squares of each number, also in sorted non-decreasing order. [Read More]

Solutions Intuition: we only pay the number of distinct letters in s. The rest can be copied. Thus, the solution consists in simply counting the number of distinct characters in s. Haskell Just use Set to count unique characters. 1 2 3 4 5 6 7 8 9 import qualified Data.Set as Set import Data.List (intercalate) calculateCost = length . Set.fromList main = do _ <- getLine contents <- getContents putStrLn . [Read More]

Solutions First of all, we sort both the series in non-decreasing order, then we simply check if alternating boys and girls is feasible according to the rules: 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 int T, N; cin >> T; while (T--) { cin >> N; array<vector<int>, 2> v = {vector<int>(N), vector<int>(N)}; copy_n(istream_iterator<int>(cin), N, begin(v[0])); copy_n(istream_iterator<int>(cin), N, begin(v[1])); sort(begin(v[0]), end(v[0])); sort(begin(v[1]), end(v[1])); auto m = mismatch(begin(v[0]), end(v[0]), begin(v[1]), end(v[1])); if (m. [Read More]

A professor calls out student IDs of students one by one while marking attendance. He notices that the number of students recorded in the attendance sheet is far more than the number of students who are actually present in the classes. Hence, he decides to use a robot which can record the students’ voices and keep track of which students have responded to attendance calls. At the end of each session, the robot outputs the student IDs of the students who have responded to attendance calls. [Read More]

Solutions A C++ solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 string s; cin >> s; int q, i; cin >> q; vector<int> w; char last = 0; for (auto c : s) { if (c == last) w.push_back(w.back()+c-'a'+1); else w.push_back(c-'a'+1); last = c; } sort(begin(w), end(w)); while (q--) { cin >> i; cout << (binary_search(begin(w), end(w), i) ? "Yes" : "No") << endl; } A C++ solution using std::set. [Read More]