#sort

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]