Preparation for the Christmas Holidays#12289
Sign in

Preparation for the Christmas Holidays (Editorial)

Author of the problem:

Andrii Kholod (Connect), Anna Yarosh (Anna_Yarosh)

Prepared by:

Andrii Kholod (Connect)

Analysis:

Andrii Kholod (Connect)

Solution

Let us introduce the following auxiliary construction. We transform the cells where we must place spruce branches into boxes with the following capacities. The first box will contain the branch that must be on top, i.e., , then also on the left, on the right. In other words, the capacity array will look as follows: [1, 1, 1, 2, 2, 3, 3, ..., k, k.]

Now let us fill the boxes in the following manner:

We look from the end and find the first box that does not yet contain a branch of weight (w_i).

If some box becomes overfilled, we can move any subset of its contents to the beginning.

Now we can see that if under this distribution there is **no prefix** for which the sum of capacities of the boxes is **smaller** than the number of branches placed in that prefix, then the answer is **Yes**, otherwise **No**.

The time complexity of the solution is (O(n n)).

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define endl '\n'
#define pb push_back

const ll clasik = 2e5+17;

ll w[clasik] , pref[clasik] , poslid[clasik];

void solve() {

    ll n;

    cin>>n;

    for (int i = 1 ; i<=n ; i++) cin>>w[i];

    
    ll nn = n;

    nn--;

    ll k = -1;

    for (int j = 0 ; j*(j+1) <= nn ; j++) {
        if (j*(j+1) == nn) {
            k = j;
            break;
        }
    }

    if (k == -1) {cout<<"No"<<endl; return;}

    sort(w+1 , w+1+n);
    

    vector<ll> v;

    ll len = 1;

    for (int i = 2 ; i<=n ; i++) {
        if (w[i] != w[i-1]) {
            v.pb(len);
            len = 0;
        }
        len++;
    }
    v.pb(len);

    sort(v.begin() , v.end());

    ll p = 0;

    ll cnt = v.size();

    for (int i = 1 ; i<=2*k+1 ; i++) {
        pref[i] = cnt;
        while(p < v.size() && v[p] <= i) {
            p++;
            cnt--;
        }
    }

    reverse(pref+1 , pref+2+2*k);

    poslid[1] = 1;

    ll q = 1;

    for (int i = 1 ; i<=2*k+1 ; i++) {
        poslid[i] = q;
        if (i == 1) continue;
        q+=(i%2);
    }


    ll sum1 = 0, sum2 = 0;

    for (int i = 1 ; i<=n ; i++) {
        sum1+=pref[i];
        sum2+=poslid[i];
        if (sum1 > sum2) {
            cout<<"No"<<endl;
            return;
        }
    }

    if (sum1 == sum2) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return;

}  

signed main() {
    speed;
    int test;
    cin>>test;
    while (test--) solve();
    return 0;
}
C++