PERMSPL - Editorial

PROBLEM LINK:

Division 1
Division 2
Practice

Author: Anton Trygub
Tester: Alexander Morozov
Editorialist: Colin Galen

(My) video
Official video

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Math, DP (knapsack)

PROBLEM:

You’re given a permutation of the integers 1 \dots n. Find out if it’s possible to split this permutation into two subsequences (maintaining the original order) so that the number of inversions - indices i, j where i < j and a_i > a_j - in both sequences are the same.

QUICK EXPLANATION:

Main solution

Consider the quantity \Delta - the difference between the inversion counts of each sequence (first - second). If all elements are in the first sequence, \Delta = the number of inversions in the initial permutation.

Let c_i be the number of pairs that include i and create an inversion. Moving element i from the first sequence to the second decreases \Delta by c_i, independent of other elements. So you can run 0-1 knapsack to see if it’s possible to use c_i to obtain \Delta.

EXPLANATION:

Main solution

Define \Delta to be the difference between the inversions of the two sequences (first - second). We’ll try to make \Delta = 0 instead of making the two inversion counts the same, which is equivalent. Let’s start off with all elements in the first sequence, and we’ll move some of those numbers to the second sequence. Initially, \Delta is the number of inversions in the initial sequence, which we can count naively using the definition of an inversion.

Consider some pair i, j that forms an inversion, that is, i < j and a_i > a_j. What happens when we move i from the first sequence to the second? There are two cases:

  • j is still in the first sequence: in this case, moving i removes the inversion pair i, j from the first sequence, so \Delta decreases by 1.
  • j is in the second sequence: in this case, moving i creates the inversion pair i, j in the second sequence, so \Delta still decreases by 1.

So, no matter what we do with j, if we move i to the other sequence, \Delta decreases by 1 for each pair it’s in. The casework ends up being the same for j, so this holds true for all elements.

For notation, let c_i be the number of inversion pairs that index i is “involved in” - it’s either the first or second index in the pair. You can think of this as its degree in a graph where every inversion creates an edge. Independent of other elements (as demonstrated above), if we move element i to the second sequence, \Delta decreases by c_i. Since we want \Delta to be 0, you can model it as choosing some subset of the values c_i that sums to \Delta. This is exactly knapsack, and the remainder of the problem can be solved with that.

TIME COMPLEXITY:

Main solution

O(n^3) for the knapsack (O(n^2) possible sums and O(n) elements).
Another note: O(n^2) for computing inversions naively. This can be sped up to O(n \log n) with an efficient structure for range sum/query, but it makes no difference as this isn’t the main contributor to the complexity.

O(n^3) in total.

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
 
using namespace std;
 
void solve()
{
    int n;
    cin>>n;
    vector<int> p(n);
    for (int i = 0; i<n; i++) cin>>p[i];
    vector<int> deg(n);
    for (int i = 0; i<n; i++)
    {
        for (int j = 0; j<i; j++) if (p[j]>p[i]) deg[i]++;
        for (int j = i+1; j<n; j++) if (p[j]<p[i]) deg[i]++;
    }
 
    int sum = 0;
    for (auto it: deg) sum+=it;
    vector<bool> can(sum+1);
    can[0] = true;
    for (auto it: deg)
    {
        for (int i = sum; i>=it; i--) if (can[i-it]) can[i] = true;
    }
 
    if (can[sum/2]) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
 
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
 
    int t;
    cin>>t;
    while (t--) solve();
}
Tester's Solution
#include <bits/stdc++.h>
 
using namespace std;
using nagai = long long;
 
int main() {
	 cin.tie(0);
	 ios::sync_with_stdio(false);
	 int t;
	 cin >> t;
	 while(t--) {
		 int n;
		 cin >> n;
		 vector<int>a(n);
		 for(auto&x:a)
			 cin >> x;
		 bitset<20000> bs = {};
		 bs[0] = true;
		 int sum=0;
		 for(int i=0;i<n;++i) {
			 int c=0;
			 for(int j=0;j<n;++j)
				 if(j < i && a[j] > a[i] || j > i && a[j] < a[i])++c;
			 sum += c;
			 bs |= bs << c;
		 }
		 cout << (bs[sum/2] ? "YES" : "NO") << '\n';
	 }
	 return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

#define send {ios_base::sync_with_stdio(false);}
#define help {cin.tie(NULL); cout.tie(NULL);}
typedef long long ll;
 
void solve(int tc = 0) {
	ll n; 
	cin >> n;
	ll a[n], b[n];
	
	for (ll i = 0; i < n; i++) cin >> a[i];
	
	ll tot = 0;
	
	for (ll i = 0; i < n; i++) {
		ll inv = 0;
		for (ll j = 0; j < i; j++) {
			if (a[j] > a[i]) ++inv;
		}
		
		for (ll j = i + 1; j < n; j++) {
			if (a[i] > a[j]) ++inv;
		}
		
		b[i] = inv;
		tot += inv;
	}
	
	tot /= 2;
	
	ll dp[tot + 1] = {0};
	dp[0] = 1;
	for (ll i = 0; i < n; i++) {
		for (ll j = tot; j >= 0; j--) {
			if (j + b[i] <= tot) {
				dp[j + b[i]] |= dp[j];
			}
		}
	}
	
	cout << (dp[tot] ? "YES\n" : "NO\n");
}
 
int main() {
	send help
	
	int tc = 1;
	cin >> tc;
	for (int t = 0; t < tc; t++) solve(t);
}  

Video Editorial(s)

My video: CodeChef September Lunchtime 2020 - All Solutions (Div. 1 + Div. 2) - YouTube
Official video: - YouTube

12 Likes

Really cool solution! I was thinking it was from graph theory.

Me too was trying a cutting plane which would create two graphs with equal directed edges (an inversion as an edge) , Do you have any intuition to solve it using graphs ??

Nope. I couldn’t think of any fast approach.

Here If we move both i & j , won’t Δ decrease by 2 as it removes the i,j inversion pair from first and add it to second?

Yes, but removing j will have decreased \Delta by 1 in a separate movement operation, so we’ll assume we took care of it beforehand. In this scenario, we’re only focusing on i.

2 Likes

@galencolin your videos are too op
orz

how can “1 2 3” turn out to be true?

Just
1 2
and
3
since both of them have 0 inversions.

2 Likes

Lol, for subtask I iterated over all possible masks and I coded the Fenwick tree to count inversions.

1 Like

<3.

The explanation was great!!
Thank You :slight_smile:

1 Like

Really nice question loved it :smile:

Overcounting Issue?
Let’ say the answer subset contains the indices ‘i’ and ‘j’, then the subset-sum will be Ci + Cj. But what if ‘i’ and ‘j’ also form an inversion pair with each other? In this case, Ci + Cj will contain one overcounted pair. How do we resolve this?

It won’t overcount, it’ll do exactly what we want. Moving both i and j removes an inversion pair from the first sequence and creates one in the second sequence, decreasing \Delta by 2. (Note that i and j are accounted for in c_j and c_i respectively)

Ok now I got it. I was thinking that we can decrease Δ by only 1. Thanks!

In last 1 year this is one of the most beautiful thing i have seen

2 Likes

In the tester solution
Why the answer is can[sum/2]
According to the editorial it should be can[sum].

sum is always possible as its the initial no. of inversions in array. we are checking for sum/2 because as inversions in both array are equal we have inv(a)=inv(b) where a and b are two seperate arrays. then inv(a)+inv(b)=inv(arr), which gives inv(tobeobtained)=inv(arr)/2. correct me if wrong.

please can anyone tell what the inner for loop is doing…that would be really appreciable…
ll dp[tot + 1] = {0};
dp[0] = 1;
for (ll i = 0; i < n; i++) {
for (ll j = tot; j >= 0; j–) {
if (j + b[i] <= tot) {
dp[j + b[i]] |= dp[j];
}
}
}