Sort by Subsequence Sum
You are given a sequence of N integers. For each number in the sequence, calculate the sum of all its non-empty subsequences. Sort the original sequence based on these subsequence sums in non-decreasing order. If two numbers have the same subsequence sum, preserve their original relative order.
Input
The first line contains an integer N. The second line contains N space-separated integers a_1, a_2, ..., a_N.
Output
Print N space-separated integers, the elements of the original sequence sorted according to the specified criteria.
Constraints
1 <= N <= 200000, 0 <= a_i <= 10^9
Example 1
5 3 1 4 1 5
1 1 3 4 5
The numbers are 3, 1, 4, 1, 5. Their subsequence sums are also 3, 1, 4, 1, 5. Sorting stably by these sums gives 1, 1, 3, 4, 5. The first '1' came before the second '1' originally, so it remains first.
Example 2
4 10 20 10 30
10 10 20 30
The numbers are 10, 20, 10, 30. Subsequence sums are 10, 20, 10, 30. Stable sort yields 10, 10, 20, 30. The first 10 stays before the second 10.
Hints
Similar problems
- Group by PropertyMedium
- Count Unique Element PairsMedium
- Subarray XOR with TargetMedium
- Longest Prefix with Equal CountsMedium
- Minimum XOR Sum of SubarraysMedium
- Longest Subarray with Equal Number of Zeroes and OnesHard
More topics: Hash Map and Hashing problems, Prefix Sums problems, Sorting problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 3 1 4 1 5
4 10 20 10 30