Sharp Eyes
Time limit2sMemory limit128 MB
Given up to 20,000 arithmetic progressions forming a multiset, find the single integer with odd multiplicity using binary search on prefix parity.
- Level
Medium7 of 10
- Topics
- Binary search, Math, Prefix sum, Implementation
- Solved
- No attempts yet
Problem
A multiset of integers is described by several arithmetic progressions. A line A C B contributes every integer A, A+B, A+2B, ... that is not greater than C.
Across the whole multiset, at most one integer appears an odd number of times; every other integer appears an even number of times. Find the integer that appears an odd number of times.
Input
The first line contains the number of progressions N, where 1 <= N <= 20,000.
Each of the next N lines contains three integers A C B. Each value is between 1 and 2,147,483,647, inclusive. A line means that every integer A + kB with k >= 0 and A + kB <= C is included in the multiset.
Output
If an integer appears an odd number of times, print that integer and its multiplicity separated by a space.
If no such integer exists, print NOTHING.
Hint
For a value x, count how many generated elements are less than or equal to x. The prefix count is even before the odd-multiplicity value and odd from that value onward, so the parity of this prefix count can be used with binary search.