Jumps
2015 TCO Final · 2015-04-08 · by zxqfl
2015 TCO Final · 2015-04-08 · by zxqfl · Greedy
Problem Statement
Problem Statement
Foobar the Frog lives on a number line.
One day, he performed a series of one or more jumps.
At the beginning he was on an integer coordinate.
The first jump in the sequence was 1 unit long.
Each subsequent jump was twice as long as the previous one.
Foobar wrote down a sequence of all coordinates he visited during his jumps, including the coordinate where he started. (Hence, this sequence consisted of J+1 integers, where J is the number of jumps Foobar made.)
Foobar then produced a new sequence of integers. The new sequence was produced in two steps. In the first step, Foobar may have erased some elements of his original sequence. (It is possible that he did not erase any elements. After the first step the sequence contained at least one element.) In the second step, Foobar may have rearranged the remaining elements arbitrarily.
You are given along[] positions.
Return "Valid" if this sequence can be obtained as the result of the process described above.
In other words, return "Valid" if it is possible to rearrange the elements of positions and possibly add some new elements in such a way that the reconstructed sequence corresponds to Foobar's way of jumping.
Otherwise, return "Invalid".
Foobar wrote down a sequence of all coordinates he visited during his jumps, including the coordinate where he started. (Hence, this sequence consisted of J+1 integers, where J is the number of jumps Foobar made.)
Foobar then produced a new sequence of integers. The new sequence was produced in two steps. In the first step, Foobar may have erased some elements of his original sequence. (It is possible that he did not erase any elements. After the first step the sequence contained at least one element.) In the second step, Foobar may have rearranged the remaining elements arbitrarily.
You are given a
Notes
- The numbers Foobar erased from the list could have been arbitrary. In particular, the erased numbers did not necessarily satisfy the constraints given for positions.
Constraints
- positions will contain between 1 and 50 elements, inclusive.
- Each element of positions will be between 1 and 1,000,000,000,000,000,000 (10^18), inclusive.
Examples
0)
{1, 2, 8, 16, 4}
Returns: "Valid"
One possibility is that Foobar's original list was [1, 2, 4, 8, 16] and he only rearranged it.
1)
{1, 2, 3}
Returns: "Valid"
Foobar's original list might have been [2, 1, 3].
2)
{1, 2, 3, 4}
Returns: "Invalid"
3)
{6, 62, 30, 11, 10, 12}
Returns: "Valid"
4)
{1, 1000000000000000000, 2}
Returns: "Valid"
Submissions are judged against all 151 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class Jumps with a public method string isValidList(vector<long long> positions) · 151 test cases · 2 s / 256 MB per case