Editorial for Wesley's Anger Contest 6 Problem 3 - Difference Sorting

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Riolku

It is important to note that this problem has many, many possible solutions. Most of them first sort the array, and then determine what $K$ ~K~ value is required to have each element be able to swap into the correct position.

Subtask 1

For this subtask, we can binary search over all possible values of $K$ ~K~, noting that $K$ ~K~ will be less than the max $a_i$ ~a_i~, so $K \le 2\,000$ ~K \le 2\,000~. For each value of $K$ ~K~, we can iterate over the array and swap any pair of elements that are out of order and have difference less than or equal to $K$ ~K~.

Time Complexity: $\mathcal{O}(N^2 \log K)$ ~\mathcal{O}(N^2 \log K)~

Subtask 2

For this subtask, we need a more efficient way to check if a given $K$ ~K~ value will work. To do so, we will use DSU. For each pair in the sorted list, add an edge if the difference is not more than $K$ ~K~. After, we need to ensure that there is a way for every element to go from its initial index to its final index.

Time Complexity: $\mathcal{O}(N \log K \log N)$ ~\mathcal{O}(N \log K \log N)~

Comments

0

dxke02 commented on Jan. 27, 2021, 12:59 a.m. ← edited →

when you say loop thru all the pairs in the sorted array do you really mean every single one because most of the time it will TLE because the size is $2 \times 10^5$ ~2 \times 10^5~ (sorry if I'm being dumb)

2

GeeTransit commented on Jan. 27, 2021, 1:08 a.m.

You can loop through each adjacent pair, so if the sorted array was [1, 2, 4, 7], you'd check (1, 2), (2, 4), and (4, 7). As an example, if the difference between 2 and 4 is more than k, the difference between 2 and any further nodes is gonna be more than k as well. Also, we're looping through them in order because each set in the DSU has a maximum difference of k, so when one pair is more than k, the set stops being added to.

0

dxke02 commented on Jan. 27, 2021, 1:24 a.m.

Despite taking your advice, I still TLE on the 2nd case of the 2nd batch.

0

GeeTransit commented on Jan. 27, 2021, 1:41 a.m.

Right now, your code is making a degenerate chain of parents from the smallest item to the largest, causing your find function to be linear. You can use either path compression or union by rank (or switch which one's being added to) to make it log $N$ ~N~.

1

dxke02 commented on Jan. 27, 2021, 1:50 a.m.

thanks, I got AC

2

GeeTransit commented on Jan. 26, 2021, 12:48 a.m. ← edit 2 →

The $log N$ ~log N~ for Subtask 2 can be reduced to constant time by setting the larger item's parent to the smaller item's parent when adding edges because the disjoint set "leaders" don't change and because the edges are added consecutively. EDIT: Wait I thought about this a lil bit. Where does the $N log N$ ~N log N~ for sorting the array go?

2

Riolku commented on Jan. 26, 2021, 2:42 a.m. ← edited →

The time required to sort the array, $\mathcal O(N \log N)$ ~\mathcal O(N \log N)~, is not relevant, since $\mathcal O(N \log K \log N)$ ~\mathcal O(N \log K \log N)~ is a direct superset of $\mathcal O(N \log N)$ ~\mathcal O(N \log N)~

That said, I believe what you are suggesting is the fast optimization to DSU that involves both union-by-rank and path compression, which would achieve the complexity $\mathcal O(N\log K\times\alpha(N) + N \log N)$ , where $\alpha(N)$ ~\alpha(N)~ is the inverse ackermann function. This is indeed faster, but is not "constant time".

At any rate, the posted complexity is quite sufficient to pass the problem, and can be achieved with union find or path compression alone.

1

GeeTransit commented on Jan. 26, 2021, 6:43 p.m.

I didn't use path compression nor union by rank (see line 9 of https://dmoj.ca/submission/3327789). It just sets the parent to the previous one's parent (this is looping thru the sorted numbers btw).

But yeah it's probably just my subpar implementation + Python's (lack of) speed that caused it to TLE before :/

1

aryanv commented on Jan. 25, 2021, 6:06 p.m.

even subtask2 was acceptable by binary search!! you dont need to check all the values!!

2

Riolku commented on Jan. 25, 2021, 6:25 p.m.

I strongly suggest you reread the editorial.

6

luismo commented on Jan. 25, 2021, 2:15 p.m.

I had a different approach using Coordinates Compression and a Min/Max Segment Tree

3

Riolku commented on Jan. 25, 2021, 6:27 p.m.

RMQ was very popular. However, that solution wasn't actually known by the contest organizers prior to the contest itself.

That said, this problem has many interesting solutions, and I encourage you to think about many ways to solve this, and perhaps to read some of the other submissions.

2

luismo commented on Jan. 25, 2021, 7:46 p.m. ← edited →

I really enjoyed solving this problem.