Why

Kring

I believe text was much better for learning where you can take hints from each line and then work your way out to solve the problem.

you are handsome bro

why is not anyone solving d with dp i can not understood

#include <bits/stdc++.h>
 
#define endl "\n"
typedef long long ll;
using namespace std;
  
void solve() {
    ll n, k;
    cin >> n >> k;
    unordered_map<int, vector<ll>> mp;
    unordered_map<ll, ll> count;
    for (int i = 0; i < n; i++) {
        ll cur; cin >> cur;
        mp[cur % k].push_back(cur); 
        count[cur]++;
    }

    ll ans = 0, odd_count = 0;
    for (auto pair : mp) {
        vector<ll>& nums = pair.second;
        if (nums.size() % 2 != 0) {
            odd_count ++;
            if (odd_count == 2) {
                cout << "-1" << endl;
                return;
            }
        }

        vector<ll> v;
        for (auto num : nums) {
            if (count[num] % 2 != 0) v.push_back(num);
        }
        ll sz = v.size();
        sort(v.begin(), v.end());
        if (sz % 2 == 1) {
            ll mx_d = 0, index = 0;
            for (int i = 0; i < sz - 2; i+=2) {
                ll dif = abs((v[i + 1] - v[i]) - (v[i + 2] - v[i + 1]));
                if (dif > mx_d) {
                    mx_d = dif; index = i;
                }
            }
            if (v[index + 1] - v[index] < v[index + 2] - v[index + 1]) {
                index = index + 2;
            }
            v.erase(v.begin() + index); sz--;
        }

        for (int i = 0; i < sz - 1; i+=2) {
            ans += (v[i + 1] - v[i]) / k;
        }
    }

    cout << ans << endl;
} 
 
int main() {
ios::sync_with_stdio(0);
    cin.tie(0);
 
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
 
    return 0;
}

Problem E; wrong answer 5th numbers differ — expected: '118834745', found: '123022038' my code is failing this test case, can someone help me? i could come up with the entire solution on my own apart from the prefix and suffix sum stuff to find the element that needs to go in the middle, i'm struggling to understand how i would use prefix and suffix to find this element, can someone explain how it would work? I did it in a different way in my code but it's missing this test case-

My G's code is O(n^2) ,but it passed.

I am working on https://mirror.codeforces.com/contest/1986/problem/E and got some interesting timing result that I cannot explain.

In short, I have two submissions, one accepted and another TLE, but I can't understand why the TLE version is slower.

• Accepted submission: https://mirror.codeforces.com/contest/1986/submission/279826856
• TLE submission: https://mirror.codeforces.com/contest/1986/submission/279824555

The only difference between two submissions is that the accepted version sort the whole array once, and the TLE version sorts the bucket individually.

In principle, sorting the individual bucket has a time bound of O(sum (b log b)) <= O(n log (max b)), and it should be smaller than O(n log n) in all cases.

Local testing of sorting arrays by buckets or not does not show much difference, it could end up in many buckets, or it could end up with fewer but huge buckets, but the timing is more or less the same.

But in the submission, the timing difference is huge, the sorting by bucket version didn't complete in 2 seconds, but the sorting one version completed in 217ms.

This benchmark seems to show very similar timing:

import random
import time

l = list(range(1000000))
random.shuffle(l)

s = time.time()
l.sort()
buckets = {}
for v in l:
    mod = v % 1000
    if mod not in buckets:
        buckets[mod] = []
    buckets[mod].append(v // 1000)
t = time.time() - s
print(t)

l = list(range(1000000))
random.shuffle(l)


s = time.time()
buckets = {}
for v in l:
    mod = v % 1000
    if mod not in buckets:
        buckets[mod] = []
    buckets[mod].append(v // 1000)
for b in buckets:
    bucket = buckets[b]
    bucket.sort()
t = time.time() - s
print(t)

No way the difference in sorting caused a 10 fold timing difference. I also submitted multiple times to confirm it is not a glitch on the judge.