#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 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]