Secret repetition

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]

Sherlock and Squares

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

The Salesman in a Rush

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