CapriciousSorting
SRM 799 · 2021-02-04 · by IH19980412
Problem Statement
One day, Frederica found the
She thinks that only sorted arrays are beautiful, so she would like to transform num into a sequence that is sorted in strictly ascending order.
However, she thinks that simply sorting the elements is not fun. Instead, she is going to do the following operation:
- First, she picks some integer A that is between 0 and 2^30 - 1, inclusive.
- Second, she will xor all elements of num with the chosen A. That is, the new value of num[i] will be (num[i] xor A), for all valid i.
Of course, not every selection of A makes the final sequence sorted.
In order to help Frederica, please calculate and return the number of different choices for A that do change num into a sequence in strictly ascending order.
Constraints
- N will be between 2 and 50, inclusive.
- num will contain exactly N elements.
- Each element in num will be between 0 and 2^30 - 1, inclusive.
{0, 1, 2, 3, 4, 5, 6, 7}
Returns: 134217728
We can choose the highest 27 bits of A arbitrarily. The lowest three bits of A must be 0.
{7, 6, 5, 4, 3, 2, 1, 0}
Returns: 134217728
Again, we can choose the highest 27 bits of A arbitrarily. This time the lowest three bits of A must be 1.
{47, 47, 42}
Returns: 0
Regardless of which A you choose, the first two elements will always be the same and thus the sequence will never be strictly increasing.
{84, 94, 68, 72, 96, 31, 2, 57}
Returns: 67108864
{766439728,766439734,766439733,766439732,766439739,766439737,766439736,766439743,766439742,766439741,766439740,766439713,766439712,766439718,766439722,766439720,766439724,766439699,766439698,766439697,766439702,766439701,766439700,766439707,766439706,766439705,766439704,766439711,766439710,766439709,766439708,766439683,766439682,766439681,766439680,766439685,766439684,766439689,766439694,766439693,766439692}
Returns: 16777216
Submissions are judged against all 81 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CapriciousSorting with a public method int count(vector<int> num) · 81 test cases · 2 s / 256 MB per case