#math

Solutions This problem is very easy but, as we’ll see in a minute, it can be solved in a very clever way. The easiest approach uses extra space, a frequency table. The core of the algorithm in C++: 1 2 3 4 5 6 7 8 9 10 11 12 13 int N; cin >> N; vector<int> A(2*N); copy_n(istream_iterator<int>(cin), 2*N, begin(A)); vector<int> freq(1'000'000 + 1); for (auto i : A) { freq[i]++; if (freq[i] > 1) { cout << i; break; } } This solution is linear. [Read More]

Solutions There exist several approaches and solutions to this problem. Some are very intuitive, others require to rack one’s brain. This challenge is a variation of the “Equilibrium Index,” and since it’s available as Sherlock and Array on this website, we won’t revisit all the solutions discussed there. For instance, solutions based on the prefix sum pattern are not covered here but can also be applied to this problem. For completeness, we mention the brute force solution that consists in iterating through potential server values from 1 to \( n \). [Read More]

Solutions The naive solution runs in timeout. A better solution is \(O(\sqrt{B})\): 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 inline pair<bool, int> IsPerfectSquare(int n) { const auto root = sqrt(n); return make_pair(root == floor(root), root); } int main() { size_t T; cin >> T; int a, b; while (T--) { cin >> a >> b; pair<bool, int> pfs = {false, 0}; while (a<=b && ! [Read More]

You are a salesman and your goal is to visit all the houses along a certain street. You walk at a constant rate and can start and end at any location. You may visit the houses in any order you wish. Given the locations of the houses along the street, what is the minimum amount of time needed for you to visit all the houses? Formally, we represent the street as a number line and the positions of the houses as numbers along this line. [Read More]