#binary search

Given a decimal number N between 1 and 4999, find its corresponding Roman numeral. Roman numerals are formed by the combination of these letters: 1 2 3 4 5 6 7 I=1 V=5 X=10 L=50 C=100 D=500 M=1000 Rules to combine letters: A letter repeats its value that many times (XXX = 30, CC = 200, etc.). A letter can only be repeated three times (except M). If one or more letters are placed after another letter of greater value, add that amount (VI = 6 (5+1)). [Read More]

The school term starts soon, and the students need to be sorted into their respective sections. There are \( n \) students numbered \( 1 \) to \( n \), and \( m \) sections numbered \( 1 \) to \( m \). Section needs to have exactly \( a_i \) students. To simplify the process, the school has decided to assign students to sections in increasing student number, which means the first \( a_1 \) students will be assigned section \( 1 \), the next \( a_2 \) students will be assigned section \( 2 \), and so on. [Read More]

Solutions This problem seem complicated if you try not using additional data structures. This is a typical case where pre-processing is needed and, in particular, we use two special kind of prefix sums. To answer to the first type of queries, we need to cache the running maximums of the prices: 1 2 3 4 5 6 7 8 vector<int> prefixMax(n); auto runningMax = p.front(); prefixMax[0] = runningMax; for (auto i=1; i<n; ++i) { prefixMax[i] = max(runningMax, p[i]); runningMax = prefixMax[i]; } In C++, we have a very useful standard algorithm to perform the same routine: [Read More]

Solutions This is a problem on intervals, such as this and this. In this challenge, the main point is to find an efficient way to insert an interval into an array of already sorted and non-overlapping intervals. The naive solution is to just insert it at the end of the array, sort again and finally merge new overlapping pairs. The cost is in the order of \(O(N \cdot logN)\) (and includes also the possible hidden cost of relocating the array, in case the space is not enough). [Read More]

Solutions The simplest solution to this problem involves storing a copy of the entire array every time a new version is saved. This way, to retrieve the value of an element at a specific version, we can simply access the saved array for that version. However, while easy to understand, this approach is highly inefficient for large arrays or when versions are taken frequently. If there are \(N\) calls to each function, this method would store \(N\) full copies of the array, leading to significant memory usage and poor time performance. [Read More]

Solutions Consider this test case: Visually, for each element of B we should mark the elements in A and C that are less than or equal to that element: And, for 3: Performing the operation on the second 3 is redundant, because triplets must be unique. Along the way, we could multiply the count of A’s marked elements with the count of B’s marked elements. All the results will be then accumulated. [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]