DPOWER - Editorial

editorial
, , ,
1

PROBLEM LINK:

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

Author: gg98
Tester: mexomerf
Editorialist: iceknight1093

DIFFICULTY:

simple

PREREQUISITES:

Sorting

PROBLEM:

There are N soldiers, with distinct strengths. You would like to choose N-1 of them.
The rank of a chosen soldier is the number of chosen soldiers with strictly larger strength, plus one.
Find the number of distinct rank arrays possible.

EXPLANATION:

First, since the array elements are distinct, let’s compress to them to [1, N] - that is, map the smallest element to 1, second smallest to 2, and so on till the largest element is mapped to N.
This doesn’t change the answer.
Let P denote the strength array after compression.

Each rank array is determined by removing one soldier, so let’s analyze when the rank arrays formed by removing soldier x and soldier y are the same (say x \lt y).

Consider the solder with strength s (after compression).
Observe that:

  1. If s \lt \min(P_x, P_y), the rank of this solder will be N-s whether x is removed or y is removed.
  2. If s \gt \max(P_x, P_y), similarly the rank of this solder will be N+1-s no matter whether x or y is removed.
  3. If s lies between P_x and P_y, then we’ll see some change in the rank - the rank will change by exactly 1, in fact.
    For example, if P_x = 4 and P_y = 10, then the solder with strength s = 5 will have a rank of N+1-5 when x is removed, but N-5 when y is removed.

So, in a sense, only values between P_x and P_y are “important”.

Let’s see what this means for the overall rank array.

For convenience, let b_i denote the rank of soldier i when x is excluded, and c_i denote the rank of soldier i when y is excluded . Note that these are arrays of length N, with b_x and c_y being undefined - but we only compare the defined parts of both rank arrays to check for equality, and that’s of length N-1.

So, for the rank arrays to be equal, we must have:

  • b_i = c_i for all 1 \leq i \lt x
  • b_i = c_i for all y \lt i \leq N
  • b_{i+1} = c_i for all x \leq i \lt y

The third condition is particularly interesting.

We work with P_x \lt P_y without loss of generality.
Note that:

  • c_x = N-P_x, meaning b_{x+1} = N-P_x must hold.
    This forces P_{x+1} = P_x + 1 since this is the number with rank N-P_x when P_x is removed.
  • This tells us that c_{x+1} = N - P_x - 1, so by the exact same logic, P_{x+2} = P_{x+1} + 1 = P_{x} + 2.
  • The same logic repeats again to give us P_{x+3} = P_x + 3, and so on.

Essentially, the sequence of values in P from index x to index y must be [P_x, P_x+1, P_{x}+2, \ldots, P_y].
Note that if P_x \gt P_y instead, we’d have the same reasoning but end up with the decreasing sequence [P_x, P_x - 1, \ldots, P_y] instead.

Now, we’ve established that if the rank arrays formed by removing soldiers x and y being equals means the values from P_x to P_y must occur in order from positions x to y - either ascending or descending.
It’s not hard to see that this condition is not just necessary, it’s also sufficient - that is, if every element from P_x to P_y occurs in order, removing x and removing y will result in the same rank arrays.

This gives us a very easy way of counting the number of distinct final rank arrays.
Start with \text{ans} = 1, obtained by removing the leftmost soldier.
Then, for each i from 2 to N,

  • If |P_i - P_{i-1}| = 1, removing soldier i will result in the same rank array as removing i-1.
    So, don’t add anything to the answer.
  • If |P_i - P_{i-1}| \neq 1, removing soldier i will result in a different rank array from removing i-1.
    In fact, the rank array will be different from removing any soldier before i (because i and i-1 are already not in the correct configuration, going past them won’t be able to fix this either).
    So, add 1 to \text{ans}.

Print \text{ans} in the end.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Author's code (C++) 
#include <bits/stdc++.h>
using namespace std;
void main_() {
	int t;
	cin>>t;
	while(t>0)
	{
        int n;
        cin>>n;
        int a[n];
        for(int i=0;i<n;i++)
        cin>>a[i];
        vector<pair<int,int>>v;
        for(int i=0;i<n;i++)
        {
            v.push_back({a[i],i});
        }
        sort(v.rbegin(),v.rend());
        int b[n];
        int r=1;
        for(auto it:v)
        {
            b[it.second]=r;
            r++;
        }
        int ans=n;
        for(int i=1;i<n;i++)
        {
            if(abs(b[i]-b[i-1])==1)
            ans--;
        }
        cout<<ans<<"\n";
		
        
        
        
        
        
        t--;
	}
}
static void run_with_stack_size(void (*func)(void), size_t stsize) {
    char *stack, *send;
    stack = (char *)malloc(stsize);
    send = stack + stsize - 16;
    send = (char *)((uintptr_t)send / 16 * 16);
    asm volatile(
        "mov %%rsp, (%0)\n"
        "mov %0, %%rsp\n"
        :
        : "r"(send));
    func();
    asm volatile("mov (%0), %%rsp\n" : : "r"(send));
    free(stack);
}
int main() {
    run_with_stack_size(main_, 1024 * 1024 * 1024); // run with a 1 GiB stack
    return 0;
}
Tester's code (C++) 
#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int a[n];
        map<int, int> mpp;
        for(int i = 0; i < n; i++){
            cin>>a[i];
            mpp[a[i]] = 0;
        }
        int cnt = 0;
        for(auto &it: mpp){
            it.second = cnt++;
        }
        int ans = 1;
        for(int i = 1; i < n; i++){
            if(abs(mpp[a[i]] - mpp[a[i - 1]]) != 1){
                ans++;
            }
        }
        cout<<ans<<"\n";
    }
}
Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    
    sa = sorted(a)
    id = {}
    for i in range(n):
        id[sa[i]] = i
    for i in range(n):
        a[i] = id[a[i]]
    
    ans = 1
    for i in range(1, n):
        ans += abs(a[i] - a[i-1]) != 1
    print(ans)
2 Likes