Does this problem have a solution?

#	User	Rating
1	Benq	3792
2	Kevin114514	3678
3	VivaciousAubergine	3647
4	jiangly	3582
5	strapple	3515
6	tourist	3473
7	Radewoosh	3418
8	Um_nik	3376
9	maroonrk	3361
10	turmax	3345

#	User	Contrib.
1	Qingyu	162
2	adamant	148
3	Um_nik	146
4	Dominater069	143
5	errorgorn	141
6	cry	138
7	Proof_by_QED	136
8	YuukiS	135
9	chromate00	134
10	soullless	133

The problem goes like this:

You are given an integer array nums.

A nice permutation is defined as a permutation of any non-empty subset of nums such that the absolute difference between any two consecutive elements is exactly 1. A permutation of size 1 is considered nice by definition. A subset is any non-empty selection of elements from nums (regardless of order). A permutation of a subset is any reordering of the elements of a subset.

Your task is to compute the sum of all elements across all such nice permutations.

Since the total may be very large, output the result modulo $$$10^9 + 7$$$.

Input

An array nums of integers.
$$$1 \leq \text{nums.length} \leq 10^5$$$ (maybe no solution exists though ... I can't guarantee anything lol)
$$$0 \leq \text{nums}[i] \leq 10^5$$$ (maybe no solution exists though ... I can't guarantee anything lol)

Output

A single integer: the sum of all elements in all nice permutations of all non-empty subsets of nums, taken modulo $$$10^9 + 7$$$.

Examples

nums = [1, 2, 3]

[1], [2], [3], [1,2], [2,1], [2,3], [3,2], [1,2,3], [3,2,1] are all valid.
The sum is 34.
[1, 3], [3, 1], [2,3,1], [2,1,3], [3,1,2], and [1,3,2] are not valid.

nums = [2, 3, 2]

[2], [2], [3], [2,3], [3,2], [2,3], [3,2], [2,3,2], [2,3,2] are all valid.
The sum is 41.
[2,2], [2,2], [2,2,3], [2,2,3], [3,2,2], and [3,2,2] are not valid.

Apart from brute-forcing all $$$\sum_{k=1}^{n} \binom{n}{k} \cdot k!$$$ possibilities, I can't find any way to do it. I feel like we should start by sorting and making clusters (for example [1, 2, 9, 10, 11, 12] would have two clusters, [1, 2] and [9, 10, 11, 12]), but that kind of got me nowhere.

<spoiler summary="My Code (Python)"> ```python def solve(array): array.sort() the_one_having_nice_subarrays = [] the_nice_subarrays = [] for i in range(len(array) — 1): the_nice_subarrays.append(array[i]) if array[i + 1] != array[i] + 1: the_one_having_nice_subarrays.append(the_nice_subarrays) the_nice_subarrays = [] the_nice_subarrays.append(array[-1]) the_one_having_nice_subarrays.append(the_nice_subarrays) MOD = 10 ** 9 + 7 total_sum = 0 for a_list in the_one_having_nice_subarrays: t = len(a_list) A = a_list[0] t2 = t * t t3 = t2 * t t4 = t3 * t term = ( 2 * t4 + 4 * A * t3 + 4 * t3 + 12 * A * t2 — 8 * t2 — 4 * A * t + 2 * t ) // 12 term %= MOD total_sum = (total_sum + term) % MOD return total_sum print(solve([1,2,3])) ``` </spoiler>

def solve(array): array.sort() the_one_having_nice_subarrays = [] the_nice_subarrays = [] for i in range(len(array) - 1): the_nice_subarrays.append(array[i]) if array[i + 1] != array[i] + 1: the_one_having_nice_subarrays.append(the_nice_subarrays) the_nice_subarrays = [] the_nice_subarrays.append(array[-1]) the_one_having_nice_subarrays.append(the_nice_subarrays) MOD = 10 ** 9 + 7 total_sum = 0 for a_list in the_one_having_nice_subarrays: t = len(a_list) if t == 0: continue A = a_list[0] t2 = t * t t3 = t2 * t t4 = t3 * t term = ( 2 * t4 + 4 * A * t3 + 4 * t3 + 12 * A * t2 - 8 * t2 - 4 * A * t + 2 * t ) // 12 term %= MOD total_sum = (total_sum + term) % MOD return total_sum

def solve(array): array.sort() the_one_having_nice_subarrays = [] the_nice_subarrays = [] for i in range(len(array) - 1): the_nice_subarrays.append(array[i]) if array[i + 1] != array[i] + 1: the_one_having_nice_subarrays.append(the_nice_subarrays) the_nice_subarrays = [] the_nice_subarrays.append(array[-1]) the_one_having_nice_subarrays.append(the_nice_subarrays) return the_one_having_nice_subarrays print(solve([1,2,3,4]))

Comments (21)

Write comment?

Professor_James_Moriarty

11 months ago, hide # |

Very stupid question, but are all the elements distinct? Then it could be easier. With duplicates, it won't. Even counting the possible nice permutatiosn would be difficult then.

→ Reply

JasonMendoza2008

11 months ago, hide # ^ |

No they’re not necessarily distinct

← Rev. 3 →

Well, if they were distinct, then any nice permuation subsets must be in increasing order or decreasing order. Then, sorting the original permutation would be a very good idea, because it could help you find those permutations easily
Stuck on duplicates

No you can do [1,2,1]

No you can't unless A has two 1's in it. We assume it has distinct. I am saying that non-distinct is harder

← Rev. 2 →

Ah yes yes, i was just saying there could be duplicates, sorry.

I think let's focus on making one for distinct element ones. It's very easy, if you think a bit. Like finding the sum.

← Rev. 4 →

-13

Here's the one for distinct. It's in Python. SOrry for the time, it took a lot of time for that big-ass formula. Here's it:

SOrry, for the formatting, asked GPT to do it

Uhhh what

ImpersonaTe

I could thought of a solution of n*2^n...

if you choose an element as starting point and then do recursion to choose the -1 or +1 (if exists) then keep a sum tracker go on with it.

Then it may be solvable for n<=12

Also starting point are distinct so , if there are multpile same numbers we only have to choose the distinct ones.

-8

Too long. No, we do not need to choose distinct ones. SUppose you have two A's and one A-1. You can start a subset with A, A-1, A, so you were saying sth wrong

Edit: Why so many downvotes?

horvat.kamca

My idea does not work, plz. disregard.

okay

Okay, Jason, here's the solution for only distinct elements array in block form:

Isn't this O(n log n)? And also, did the format myself this time. The formula is the large one which is spread over multiple lines for better vision.

_kayak_

In the worst case, there is a possibility of (n*(n+1))/2 subarrays (after sorting), and you have put all such subarrays into "the_one_having_nice_subarray" and then you iterate over "the_one_having_nice_subarray". So there is definitely an n^2 factor in the time complexity. For example with [1,2,3,4] as input, "the_one_having_nice_subarray" will have 10 (=(4*(4+1))/2) subarrays in it.

Bro, it's collecting only maximal consecutive segments, and each element belongs to exactly one such segment., not all possiblwe subarrays. For example, on [1, 2, 6, 7, 8}, the subarrays are [1,2] and [6,7,8]. Where is the n^2 thing here?

← Rev. 19 →

It;s not doing [1], then [1,2], then [2], and so on, otherwise I knew it would take a long time. Type this:

See what it says. It says: ~~~~~ 1,2,3,4 ~~~~~ tHERE'S SUPPOSED TO BE two brackets around each side of 1,2,3,4, but it's not showing

Indeed, I made a mistake while analysing your code, it does run in O(nlogn)!

Thanks for confiming it! The GPT I use is free (and very stupid), so I don't believe it usually, like, when it tells me this code runs in n log n

speedcode

The problem has a solution.

Menma_gestapo

neh.. **your problem

JasonMendoza2008's blog

Input

Output

Examples