ZEROONE - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3

Author: Prasant Kumar
Tester: Danny Mittal
Editorialist: Nishank Suresh

DIFFICULTY:

Simple

PREREQUISITES:

Sorting, rearrangement inequality (or at least intuition for it)

PROBLEM:

You are given an array C which represents a binary string B, where the first C_1 characters of B are 0, the next C_2 are 1, the next C_3 are 0, and so on.
You can swap two elements of C as long as they both correspond to blocks of the same character.
Maximize the number of times 01 occurs as a subsequence in B.

QUICK EXPLANATION

Sort the elements at odd indices (C_1, C_3, C_5, \dots) in descending order, and the elements at even indices (C_2, C_4, C_6, \dots) in ascending order.
Having done this, the answer is \displaystyle C_2\cdot C_1 + C_4\cdot (C_1 + C_3) + C_6\cdot (C_1 + C_3 + C_5) + \dots = \sum_{i = 1}^ {\lfloor\frac{n}{2}\rfloor} C_{2i} \sum_{j = 1}^i C_{2j-1}

EXPLANATION:

Let us first look at how to compute the number of times 01 occurs as a subsequence given that we know C.

Consider any block of 1s C_{2i}. Let us count the number of 01 subsequences which have the 1 chosen from this block.
There are C_{2i} ways to choose a 1 in this block. We then multiply this by the number of ways to choose a 0 which occurs before this block, which is C_{1} + C_{3} + C_{5} + \dots + C_{2i-1}.

Summing this over all blocks gives us

\sum_{i = 1}^ {\lfloor\frac{n}{2}\rfloor} C_{2i} \sum_{j = 1}^i C_{2j-1}

Now, how to maximize this?
Note that the given operation essentially tells us that we are free to choose an ordering of the C_{2i} and of the C_{2i-1}, and these orderings are independent of each other.
So, we try to optimize these two separately.

Ordering C_{2i}

Suppose we have fixed an order of the C_{2i-1}. What is the best way to order the elements C_{2i}?

Intuitively, we see that placing larger elements later makes more sense - the later something occurs, the higher its multiplier is and so the more it contributes to the answer.

It turns out that this is indeed optimal - sorting the C_{2i} in ascending order gives the best possible answer.

A formal proof of this seemingly intuitive idea is given by the Rearrangement inequality.

Ordering C_{2i-1}

The idea here is exactly the same behind the one for C_{2i}.
Sorting the C_{2i-1} in descending order ensures that the larger elements have larger multipliers, which again is optimal by the rearrangement inequality.

Putting it all together

Once the even and odd indices have been sorted in their respective orders, all that is left is to compute the total sum. This can be done in \mathcal{O}(N^2) given that the constraints are small, or even \mathcal{O}(N) by maintaining a prefix sum of odd indices.

TIME COMPLEXITY:

\mathcal{O}(N^2) or \mathcal{O}(N\log{N}) per test, depending on implementation.

CODE:

Setter (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"

signed main(){
	ios_base::sync_with_stdio(0) , cin.tie(0);
	
	int t;cin>>t;
	while(t--){
		int n;cin>>n;
		vector<int> v[2];
		for(int i=0;i<n;i++){
			int x;cin>>x;
			if(i&1){
				v[1].push_back(x);
			}else v[0].push_back(x);
		}
		
		sort(v[0].begin(),v[0].end());
		sort(v[1].begin(),v[1].end(),greater<int>());
		
		int cnt0=0,ans=0;
		
		for(int i=0;i<n;i++){
			if(i&1){
				ans+=cnt0*v[1].back();
				cout<<v[1].back()<<" ";
				v[1].pop_back();
			}else{
				cnt0+=v[0].back();
				cout<<v[0].back()<<" ";
				v[0].pop_back();
			}
		}cout<<endl;
		cout<<ans<<endl;
	}




	return 0;
}
Tester (Kotlin)
fun main(omkar: Array<String>) {
    repeat(readLine()!!.toInt()) {
        val n = readLine()!!.toInt()
        val xs = readLine()!!.split(" ").map { it.toInt() }
        val ys = (0 until n step 2).map { xs[it] }.sortedDescending()
        val zs = (1 until n step 2).map { xs[it] }.sorted()
        println((0 until n).map { (if (it % 2 == 0) ys else zs)[it / 2] }.joinToString(" "))
        var answer = 0
        for (j in ys.indices) {
            for (k in zs.indices) {
                if (j <= k) {
                    answer += ys[j] * zs[k]
                }
            }
        }
        println(answer)
    }
}
Editorialist (Python)
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    a[::2] = sorted(a[::2], reverse = True)
    a[1::2] = sorted(a[1::2])
    print(*a)
    ans, sm = 0, 0
    for i in range(1, n, 2):
        sm += a[i-1]
        ans += a[i]*sm
    print(ans)
1 Like

I would like to point out a fallacy in the language of question here. What is a 01 subsequence? It was nowhere defined. A 010101 is also a 01 subsequence.

14 Likes

I wonder why was the output format as such… isn’t it rather usual to print the array after the single valued integer whether it be size or anything else?

Indeed it is my fault in noticing the output format but I wanted to point it out.

I totally agree to this. I was not able to solve this problem during the contest due to this small detail!