GREEDY MOVES DAY 02 – Q2

C. Permutation Partitions

Problem Statement – https://codeforces.com/problemset/problem/1326/C

Again, this problem was straight-forward implementation based. The greedy choice here is that we need to consider the last k integers to form up the maximum, as they will only give out the maximum sum.

Now, what remains, is to figure out how to count the number of such permutations. Now, this is easy, we can track the indices of each integer. So, sort the indices of last k integers. Now, you have got the selective indices in increasing order

Note, for any selective index, he has to take his left segment without any choice, because he has to be there in that segment. So, we need to take into account only the right segments. We can multiply the number of choices he has at each time.

Another note, if you are at last selective index, you do not have any choice, you need to consider the left and right sides completely.

void solve()
{
	ll n,k;
	cin >> n >> k;
	ll a[n+1];
    ll pos[n+1];
	rep(i,0,n) cin >> a[i],pos[a[i]] = i+1;
    ll ans = (n*(n+1))/2 - ((n-k)*(n-k+1))/2;
    ll ways = 1;
    V(ll) v;
    repp(i,n+1,n-k+1){
        v.PB(pos[i]);
    }
    sort(all(v));
    // for(ll i:v) cout << i << " ";cout << endl;
    rep(i,0,v.size()){
        if (i == v.size()-1){
            continue;
        }
        else{
            ways = (ways*(v[i+1] - v[i]))%M2;
        }
    }
    cout << ans << " " << ways << endl;
}

Leave a Reply