Editorial STARTERS 14

Diagonal movement

Practice
After observing the problem, you will see that the point whose distance from the origin i.e {0,0} is even can be reached whereas whose distance is odd will be unreachable.

Hint for code
void solve() {
    ll x, y;
    cin >> x >> y;
    ll ans = abs(x) + abs(y);
    if (ans % 2 == 0)cout << "YES" << endl;
    else cout << "NO" << endl;
}

Odd GCD

Practice
As we have to make the gcd of the array an odd number. So why will be the gcd of array an even, it will be possible only when all the elements in the array are multiple of 2. The best approach will be to make any one number to an odd number. So, we will iterate through all the elements in the array and find for each index, the number of operations to make an odd number. So the minimum of them will be our answer.

Hint for code
void solve() {
    ll n;
    cin >> n;
    ll arr[n];
    vector<ll> dp(n, 0);
    ll ans = 1e18;
    for (ll i = 0; i < n; i++) {
        cin >> arr[i];
        while (arr[i] % 2 == 0) {
            dp[i]++;
            arr[i] /= 2;
        }
        ans = min(dp[i], ans);
    }
    cout << ans << endl;
}

Fixed number of Fixed Points

Practice
So first discuss the -1 case, which will be when we have to make exactly 1 index to be unmatched i.e A[i]!=i because it will cause at least 1 more index to be unmatched.
So for other cases, what we can do is that we can only change the position of 1 to k indices by 1 position to right in a circular manner i.e by moving the first three indices of the array {1, 2, 3, 4, 5} will result to {3, 1, 2, 4, 5}.

Hint for code
void solve() {
    ll n, k;
    cin >> n >> k;
    k = n - k;
    if (k == 1)cout << -1 << endl;
    else {
        for (ll i = 1; i < k; i++)cout << i + 1 << " ";
        if (k > 0)   cout << 1 << " ";
        for (ll i = 1 + k; i <= n; i++)cout << i << " ";
        cout << endl;
    }
}

Task Times

Practice
Now for each subtask, it is more sufficient to have an odd number of topics to be done for each subject as [5/2]=[6/2] according to the question, so what we will do is we will make a vector array of all subjects and push the working hours of all the topic in it. Once all topics are pushed, sort all the vector array of all subjects. Then make a new vector in which we will push the elements so that we get to prepare either 0 topics or an odd number of topics from each subject.
Like if there is a subject of size 4, we will push 1 ^{th} topic time, (sum of 2 ^{nd} and 3 ^{rd} topic time) but we will not study that 4 ^{th} topic because even if we study that topic, it will not result in the increase of marks.

  • Will be more clear by code

Hint for code
void solve() {
    ll n, m , k;
    cin >> n >> m >> k;
    ll arr[n][2];
    for (ll i = 0; i < n; i++)cin >> arr[i][0];
    for (ll i = 0; i < n; i++)cin >> arr[i][1];
    vector<ll> ad[m + 1], final;
    for (ll i = 0; i < n; i++)ad[arr[i][0]].push_back(arr[i][1]);
    for (ll i = 1; i <= m; i++)sort(all(ad[i]));
    for (ll i = 1; i <= m; i++) {
        if (ad[i].size() > 0) {
            final.push_back(ad[i][0]);
            for (ll j = 2; j < ad[i].size(); j += 2)final.push_back(ad[i][j] + ad[i][j - 1]);
        }
    }
    ll ans = 0;
    sort(all(final));
    ll sum = 0;
    for (ll i = 0; i < final.size(); i++) {
        sum += final[i];
        if (sum <= k)ans++;
    }
    cout << ans << endl;
}
1 Like