Codeforces Round #760 (Div. 3) Editorial

#	User	Rating
1	Benq	3783
2	jiangly	3666
3	tourist	3611
4	Um_nik	3536
5	inaFSTream	3477
6	fantasy	3468
7	maroonrk	3464
8	QAQAutoMaton	3428
9	ecnerwala	3427
10	Ormlis	3396

#	User	Contrib.
1	Um_nik	185
2	adamant	177
2	awoo	177
4	nor	169
5	maroonrk	165
6	-is-this-fft-	164
7	antontrygubO_o	155
8	ko_osaga	151
8	dario2994	151
10	SecondThread	149

1618A - Polycarp and Sums of Subsequences

Idea: Brovko, preparation: Brovko

Tutorial

Solution (Brovko)

#include <bits/stdc++.h>

using namespace std;



int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
    {
        vector <int> b(7);

        for(int i = 0; i < 7; i++)
            cin >> b[i];

        cout << b[0] << ' ' << b[1] << ' ' << b[6] - b[0] - b[1] << endl;
    }
}

1618B - Missing Bigram

Idea: BledDest, preparation: awoo

Tutorial

Solution (awoo)

for _ in range(int(input())):
	n = int(input())
	s = input().split()
	for i in range(n - 3):
		if s[i][1] != s[i + 1][0]:
			s.insert(i + 1, s[i][1] + s[i + 1][0])
			break
	else:
		s.append(s[-1][1] + 'a')
	print(s[0][0], end="")
	for i in range(n - 1):
		print(s[i][1], end="")
	print()

1618C - Paint the Array

Idea: BledDest, preparation: BledDest

Tutorial

Solution (BledDest)

#include <bits/stdc++.h>     

using namespace std;

void solve()
{
    int n;
    cin >> n;
    vector<long long> a(n);
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    vector<long long> g(a.begin(), a.begin() + 2);
    for(int i = 0; i < n; i++)
    {
        g[i % 2] = __gcd(g[i % 2], a[i]);
    }  
    vector<bool> good(2, true);
    for(int i = 0; i < n; i++)
    {
        good[i % 2] = good[i % 2] && (a[i] % g[(i % 2) ^ 1] > 0);
    }   
    long long ans = 0;
    for(int i = 0; i < 2; i++)
        if(good[i])
            ans = max(ans, g[i ^ 1]);
    cout << ans << endl;
}

int main()
{
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
    {
        solve();
    }
}

1618D - Array and Operations

Idea: BledDest, preparation: BledDest

Tutorial

Solution (BledDest)

def solve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    a = sorted(a)
    cost = sum(a[0:n-2*k]) + sum(map(lambda x: a[x+n-2*k] // a[x+n-k], range(0, k)))
    print(cost)
    
t = int(input())
for i in range(t):
    solve()

1618E - Singers' Tour

Idea: shnirelman, preparation: shnirelman

Tutorial

Solution (shnirelman)

#include <bits/stdc++.h>

using namespace std;
using li = long long;

const int N = 50013;

int b[N];
int a[N];

void solve() {
    
    int n;
    cin >> n;

    li sumb = 0;
    for(int i = 0; i < n; i++) {
        cin >> b[i];
        sumb += b[i];
    }

    li d = n * 1ll * (n + 1) / 2;

    if(sumb % d != 0) {
        cout << "NO" << endl;
        return;
    }

    li suma = sumb / d;

    for(int i = n - 1; i >= 0; i--) {
        li res = (b[i] - b[(i + 1) % n] + suma);
        if(res % n != 0 || res <= 0) {
            cout << "NO" << endl;
            return;
        }

        a[(i + 1) % n] = res / n;
    }

    cout << "YES" << endl;
    for(int i = 0; i < n; i++)
        cout << a[i] << ' ';
    cout << endl;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
        solve();
}

1618F - Reverse

Idea: Lankin, preparation: Lankin

Tutorial

Solution (awoo)

a, b = map(int, input().split())
s = bin(b)[2:]
t = bin(a)[2:]
if s == t:
    print("YES")
    exit(0)
for q in [t + '1', t.strip('0')]:
    for l in range(len(s) - len(q) + 1):
        r = len(s) - len(q) - l
        if '1' * l + q + '1' * r == s or '1' * l + q[::-1] + '1' * r == s:
            print("YES")
            exit(0)
print("NO")

Solution (BledDest)

#include<bits/stdc++.h>

using namespace std;

string go(string t)
{
    while(t.back() == '0') t.pop_back();
    reverse(t.begin(), t.end());
    return t;
}

string to_bin(long long x)
{
    if(x == 0)
        return "";
    else
    {
        string s = to_bin(x / 2);
        s.push_back(char('0' + x % 2));
        return s;
    }
}

int main()
{
    long long x, y;
    cin >> x >> y;
    set<string> used;
    queue<string> q;
    q.push(to_bin(x));
    used.insert(to_bin(x));
    while(!q.empty())
    {
        string k = q.front();
        q.pop();
        if(k.size() > 100) continue;
        for(int i = 0; i < 2; i++)
        {
            string k2 = go(k + string(1, char('0' + i)));
            if(!used.count(k2))
            {
                used.insert(k2);
                q.push(k2);
            }
        }
    }
    if(used.count(to_bin(y)))
        cout << "YES\n";
    else
        cout << "NO\n";
}

1618G - Trader Problem

Idea: BledDest, preparation: BledDest

Tutorial

Solution (awoo)

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for(int i = 0; i < int(n); i++) 

const int N = 400 * 1000 + 13;

int n, m, k;
int a[N], b[N];
int q[N];

int p[N];
multiset<int> wst[N], bst[N];
long long sum;

int getp(int a){
	return a == p[a] ? a : p[a] = getp(p[a]);
}

void unite(int a, int b){
	a = getp(a), b = getp(b);
	if (wst[a].size() + bst[a].size() < wst[b].size() + bst[b].size()) swap(a, b);
	for (auto it : wst[b])
		wst[a].insert(it);
	for (auto it : bst[b])
		bst[a].insert(it);
	wst[b].clear();
	bst[b].clear();
	while (!bst[a].empty() && !wst[a].empty() && *bst[a].begin() < *wst[a].rbegin()){
		sum -= *bst[a].begin();
		sum += *wst[a].rbegin();
		bst[a].insert(*wst[a].rbegin());
		wst[a].insert(*bst[a].begin());
		bst[a].erase(bst[a].begin());
		wst[a].erase(--wst[a].end());
	}
	p[b] = a;
}

long long ans[N];

struct event{
	int x, t, i;
};

int main() {
	scanf("%d%d%d", &n, &m, &k);
	forn(i, n)
		scanf("%d", &a[i]);
	forn(i, m)
		scanf("%d", &b[i]);
	forn(i, k)
		scanf("%d", &q[i]);
	vector<pair<int, int>> tot;
	forn(i, n) tot.push_back({a[i], 1});
	forn(i, m) tot.push_back({b[i], 0});
	sort(tot.begin(), tot.end());
	sum = accumulate(a, a + n, 0ll);
	forn(i, n + m){
		p[i] = i;
		wst[i].clear();
		bst[i].clear();
		if (tot[i].second) bst[i].insert(tot[i].first);
		else wst[i].insert(tot[i].first);
	}
	vector<event> ev;
	forn(i, n + m - 1) ev.push_back({tot[i + 1].first - tot[i].first, 0, i});
	forn(i, k) ev.push_back({q[i], 1, i});
	sort(ev.begin(), ev.end(), [](const event &a, const event &b){
		if (a.x != b.x) return a.x < b.x;
		return a.t < b.t;
	});
	for (auto it : ev){
		if (it.t == 0)
			unite(it.i, it.i + 1);
		else
			ans[it.i] = sum;
	}
	forn(i, k) printf("%lld\n", ans[i]);
}

Solution (BledDest)

#include<bits/stdc++.h>

using namespace std;

long long get(const vector<int>& pcnt, const vector<long long>& psum, pair<int, int> seg)
{
    int L = seg.first;
    int R = seg.second;
    int cnt = pcnt[R] - pcnt[L];
    return psum[R] - psum[R - cnt];
}

int main()
{
    int n, m, q;
    scanf("%d %d %d", &n, &m, &q);
    vector<int> a(n), b(m);
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    for(int i = 0; i < m; i++)
    {
        scanf("%d", &b[i]);
    }
    vector<int> pcnt = {0};
    vector<long long> psum = {0ll};
    vector<pair<int, int>> order;
    for(int i = 0; i < n; i++) order.push_back(make_pair(a[i], 1));
    for(int i = 0; i < m; i++) order.push_back(make_pair(b[i], 0));
    sort(order.begin(), order.end());
    int z = n + m;
    for(int i = 0; i < z; i++)
    {
        pcnt.push_back(pcnt.back() + order[i].second);
        psum.push_back(psum.back() + order[i].first);
    }
    long long cur = 0;
    for(int i = 0; i < n; i++)
        cur += a[i];
    set<pair<int, int>> segs;
    for(int i = 0; i < z; i++)
        segs.insert(make_pair(i, i + 1));
    map<int, vector<int>> events;
    for(int i = 0; i < z - 1; i++)
        events[order[i + 1].first - order[i].first].push_back(i);
    vector<pair<int, long long>> ans = {{0, cur}};
    for(auto x : events)
    {
        int cost = x.first;
        vector<int> changes = x.second;
        for(auto i : changes)
        {
            auto itr = segs.upper_bound(make_pair(i, int(1e9)));
            auto itl = prev(itr);
            pair<int, int> pl = *itl;
            pair<int, int> pr = *itr;
            cur -= get(pcnt, psum, pl);
            cur -= get(pcnt, psum, pr);
            pair<int, int> p = make_pair(pl.first, pr.second);
            cur += get(pcnt, psum, p);
            segs.erase(pl);
            segs.erase(pr);
            segs.insert(p);
        }
        ans.push_back(make_pair(cost, cur));
    }              
    for(int i = 0; i < q; i++)
    {
        int k;
        scanf("%d", &k);
        int pos = upper_bound(ans.begin(), ans.end(), make_pair(k + 1, -1ll)) - ans.begin() - 1;
        printf("%lld\n", ans[pos].second);
    }
}

#include <algorithm> #include <cassert> #include <bitset> #include <chrono> #include <cmath> #include <cstring> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <random> #include <set> #include <vector> #include <climits> #include <stack> using namespace std; using ll = long long; using ld = long double; using ull = unsigned long long; const int MOD = 1e9 + 7; const ll INF = 1e18; #define ff first #define ss second #define mp make_pair #define lb lower_bound #define ub upper_bound #define setbits(x) __builtin_popcountll(x) #define sz(x) (int)(x).size() #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define sum(x) (accumulate ((x).begin(), (x).end(), 0ll)) #define mine(x) (*min_element((x).begin(), (x).end())) #define maxe(x) (*max_element((x).begin(), (x).end())) inline void fastio() {ios_base::sync_with_stdio(false);cin.tie(NULL);} template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; } template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; } void dbg_out() { cerr << endl; } template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); } #ifndef ONLINE_JUDGE #define dbg(...) cerr << "[" << #__VA_ARGS__ << "]:", dbg_out(__VA_ARGS__) #else #define dbg(...) #endif mt19937 rng((unsigned int)chrono::steady_clock::now().time_since_epoch().count()); int rand(int l, int r){ uniform_int_distribution<int> uid(l, r); return uid(rng); } // memset (name, value, sizeof(name)) // replace (list.begin(), list.end(), value1, value2) // unique (list.begin(), list.end()) // remove (list.begin(), list.end(), value) // lower_bound(list.begin(), list.end(), value) -> first element >= value // upper_bound(list.begin(), list.end(), value) -> first element > value ll binrev(ll x) { vector<int> bits; for(int i = 0; i < 63; i++) { if ((1LL << i) & x) { bits.push_back(1); } else { bits.push_back(0); } } while(!bits.empty() && bits.back() == 0) { bits.pop_back(); } reverse(all(bits)); ll xp {}; for(int i = 0; i < sz(bits); i++) { if (bits[i]) { xp += (1LL << i); } } return xp; } map<pair<ll, ll>, bool> m; bool f(ll x, ll y) { if (x == y) return true; if (m.find(mp(x, y)) != m.end()) { return false; } m[mp(x, y)] = true; // either perform operation 1 or operation 2 ll x1 = binrev(2 * x); ll x2 = binrev(2 * x + 1); bool res = f(x1, y) || f(x2, y); return res; } void solve() { ll x, y; cin >> x >> y; cout << (f(x, y) ? "YES" : "NO") << '\n'; } int main() { fastio(); #ifdef devansh_local auto begin = std::chrono::high_resolution_clock::now(); #endif cout << setprecision(15) << fixed; int tc = 1; while(tc--) { solve(); } #ifdef devansh_local auto end = std::chrono::high_resolution_clock::now(); cerr << "Execution time: " << std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count() << " ms" << endl; #endif return 0; }

Comments (51)

Show archived | Write comment?

naeem4265

17 months ago, # |

+32

At the beginning of the year i became expert, hopefully at the end of the year(tomorrow) i will become expert again. Nice problemset. Thanks for fast editorial.

→ Reply

WalrusRamen21

Not sure if anyone else has made this connection yet, but Problem $$$A$$$ looks very similar to Bronze Problem 1 from the 2020 December USACO competition: http://www.usaco.org/index.php?page=viewproblem2&cpid=1059

bluemuffin02

17 months ago, # ^ |

Haha, I think they are the same problem in essence :p

__Tanzeel__

+22

Even if the problem matches I think it will take less time to solve than to search for the actual problem itself :)

kinnikuma

Yes, I have already made this connection : IMO, it's a pretty classic problem.

dhruv7888

← Rev. 3 →

I solved D using Knapsack DP , I found out that last 2*k elements would be paired . So while pairing them I should try to keep elements with same value in a set , as splitting them will contribute 1 to answer , and not splitting will contribute 0 . I implementated it using Bitset Link
Edit : It got hacked :((

JacksonMHoke

Would anyone be kind enough to explain to me why these 2 submissions don't have the same result for problem e(https://codeforces.com/contest/1618/submission/139338958 https://codeforces.com/contest/1618/submission/139339631)? In the first submission I did a calculation using long long's in a cout statement, and in the second submission I swapped that with a calculation using a temp variable first then printing that variable. Is this something that I should be careful about and why does this happen? Thanks!

Inside if statement you r doing sum%n*(n+1)/2 which is equivalent to (sum%n)*(n+1)/2 . Hence WA.

clams

Why is the pairing in 1618D - Array and Operations optimal? It seems obvious but I can't find a proof for it.

We can look this as an inequality. Let's suppose a >= b >= c >= d >= e >= f >= g >= h. And k=3. (it's a simplified version, but it can be generalized to any kind of array).

First, we can see that the optimal solution gives \floor {d/a} + \floor {e/b} + \floor {f/c} + g + h.

What will the answer become if we swap elements e and g ?

It gives : \floor {d/a} + \floor {g/b} + \floor {f/c} + e + h.

To prove that the latter is less than the former, we could prove that the difference between the former and the latter (former-latter) is <= 0.

That brings us to prove that \floor {d/a} + \floor {e/b} + \floor {f/c} + g + h. - \floor {d/a} + \floor {g/b} + \floor {f/c} + e + h. <= 0. In other words \floor{e/b} + g — \floor{g/b} — e <= 0. Which is equivalent to (\floor{e/b} — \floor{g/b}) + (g-e) <= 0. The case e=g is trivial, suppose e > g. Than (\floor{e/b} — \floor{g/b}) <= 1 and (g-e) <= -1. Summing up these two inequalities, we obtain (\floor{e/b} — \floor{g/b}) + (g-e) <= 0, as desired.

Taha

I liked how you did it bro. How can I learn to write a proof like that?

← Rev. 2 →

Read other people's proofs, this is how I learned how to write.

triggered_

I solved D using Greedy here is the link https://codeforces.com/contest/1618/submission/139346218

amirhossein00

Yay, I also did the same :)

It counts the occurrence of each unique element and then puts it in a priority queue (we are trying to minimize the cnt of the element with the maximum cnt) so each time we will delete two elements with maximum cnt until there is only one unique element left(we do this on the last 2*k elements in sorted array).

RaadSharar

Same here.

amul02

Can someone helps me? In 2nd problem why my code fails the test cases https://codeforces.com/contest/1618/submission/139289954

Livu_sz

Try out this test case

1 7 bb ab bb ba ab

Your code will result bbabaab

But when you form Bigram from this : bb ba ab ba aa ab

According to your output 'ba' and 'aa' two are missing bigrams that's not possible

Correct answer should be bbabbab

As bigrams formed from this are bb ba ab bb ba ab

Correct me if I am wrong

+10

Can you help me, how you reach this test case?

phongan105

Hi, I think I might confuse something. But in the F problem ( Reverse) how can you turn 23 (10111) to 59 (111011) ?

khangai11

add 0 and reverse (10111 -> 11101)
add 1 and reverse (110111)
add 0 and reverse (111011)

Mysticode

I had solved problem C by taking the LCM of both GCDs and then checking if the array is divisible by the LCM for both the cases and printing the respective GCD, but the code didn't pass the test. Below is the link https://codeforces.com/contest/1618/submission/139321336 I did the same thing but this time I used GCD which passed all the tests. Below is the link — https://codeforces.com/contest/1618/submission/139323889 Can someone explain what is the difference between both the codes and why the LCM one didn't pass the test?

ravi_krst

LCM could cross long long limit. For example LCM of 10^18-1 and 10^18 cannot fit in long long. (ai's were upto 10^18 in problem)

onlyerror

can anyone please explain the intuition behind problem C?

The_mysterio

With practice, you will see that for these kinds it's better to evaluate all the possibilities to arrive at a conclusion. Adjacent elements needs to be colored differently...So the only two possibilities here are (even index elements colored blue and odd index elements colored red) and vice versa. Evaluate whether any of these can happen. To do so, see how can you find out a number that will divide all the numbers present at alternate indexes--->so you need to find the gcd of those numbers and then check whether the numbers at other indexes are divisible by that ...Could I make it clear ?

Algorithms

Can anyone explain what is "string(1, char('0' + i))" this line doing ??? Thanks!! This is in editorial of F.

Aging1986

convert int 1 to char '1' then to string "1"

devanshmishra111

can anyone help me figure out why this program for Problem F terminates ? It passes all the test cases:

Spoiler

isaacbell

Stupid question about Problem C:

I'm trying to understand this line of code:

--> good[i % 2] = good[i % 2] && (a[i] % g[(i % 2) ^ 1] > 0);

Specifically this part:

--> && (a[i] % g[(i % 2) ^ 1] > 0);

What's the purpose of the XOR here?

Same question about this line:

--> ans = max(ans, g[i ^ 1]);

lazy_and_slow

XOR flips the values from 0 to 1 and vice versa.

-3en_7oras-

good contest but it need to strong pretest cases in problem d and f finally i realy sorry for every one get wrong answer in d test 25 i put it in hacks , i tried to cover corner case not to hack some one

harshvardhan

If possible, add graphs tag to problem F.

saransh_singh

In problem G can someone clarify how to use DSU to reach the solution. I understand the creation of graph but am unclear on how to use DSU.

I didn't use graph or DSU. It's just interval merging.

vol-de-mort

Can you please explain basic idea of your solution, I mean just a walkover. Thanks in advance.

P.S: I could see your code but I don't want to as I want to code it on my own after knowing the basic idea you have implemented in your solution.

First combine array A and B as a new array v, then sort it. what you need to calculate is the sum of maximal x values of each interval [i, j] where v[l] + k <= v[l + 1] (i <= l < j). So, initially you have n intervals, [1,1], [2,2], ... , [n, n] where n = v.size(). For each given k in increasing order, find out all i satisfying v[i] + k <= v[i + 1] (from a pre-sorted array). Merge the interval end at i and the interval start at i + 1. I used two arrays left and right to store intervals. use prefix sum array to calculate the number of elements coming from array A between [i, j] in O(1), then use another prefix sum array to calculate the sum of maximal x values of [i, j] in O(1). You can check my last AC code.

omsgunjal2003

https://codeforces.com/contest/1618/submission/139274778 this my code of E question and I just got msg that my code is significantly match with this code https://codeforces.com/contest/1618/submission/139261121. please can anyone look into this because both codes are not same and I haven't done any unfair mean, you can also look into my profile.

Shubham__mishra

Yes, both codes are very different... Surprised how they are significantly matching.

PHENOMENALAB

Hey Everyone
Can anybody tell me how 'testcase: 1 576460752303423487' for problem F gives YES
According to me if x = 1.
You can change it to only 111...(any no of times)
but in this testcase, you can change it to 10000..(58 times). But How?

Brovko

576460752303423487 is 11...11 (59 times)

adarsh_sinhg

Binary for 576460752303423487 is "11111111111111111111111111111111111111111111111111111111111". So we can change 1 to 576460752303423487.So it gives "Yes".

De-Bug

1) In problem G, what is the proof that the rebalancing step in the unite function (i.e. while (*bst[a].begin() < *wst[a].rbegin())) won't take too long in total?

2) In problem D, how to prove that the answer is:

$$$(\sum_{i = 2k}^{n}a_i) - max(0, f - k)$$$

after sorting the array in non-increasing order? (I got AC with it and it seemed very intuitive)

$$$f$$$ is the frequency of the most repeated element in $$$a[1..2k]$$$.

the first one only runs n — 1 times, as there is only n — 1 segment and each one will be accessed only once.

Oh, I see. If I understood correctly, we are only increasing stuff, and we can do so at most $$$O(n)$$$ times.

yes.

Flyed

Regarding your second question, I had the same observation. This is my informal logic. We know that we are going to remove the first 2k elements when the array is sorted in non-increasing order. For each pair we remove, as long as the two elements are different, we can guarantee that they won't add anything to the score. Therefore, we are only concerned with pairs with two identical elements. We want to minimize those pairs in order to minimize the score. After some analysis, we can see that only the most repeated element in a[1...2k] matters. Consider the expression 2k — max_dupes, where max_dupes is the frequency of the most repeated element x in a[1...2k]. 2k — max_dupes represents the number of elements that are different from x, therefore, 2k — max_dupes operations will add nothing to the score. The remaining number of operations, which are unavoidable, will each add 1 to the score (bc numerator = denominator), which results in the expression k — (2k — max_dupes) = max_dupes — k. This equals the extra score added to the remaining sum of a[2k+1...n]. If max_dupes — k is <= 0, we know that there are no unavoidable pairs with two identical elements therefore we add max(0, max_dupes — k).

Kiribati233

Can someone help me? In problem F, I do not know why my code fails. Thanks a lot.

https://codeforces.com/contest/1618/submission/139439943

fsstamx

Hi, I think you have to change 18 to 63 because we want to convert x and y to binary numbers and they are up to 10 ^ 18 which means their binary representation has up to 63 bits.

cosenza

There's an even simpler solution for D. First of all, you greedly add the first n — 2k numbers (after sorting of course), then, for the rest of the numbers, you check how many times each number appears. If there's a number that appears more than k times, then you know that there's no avoiding in adding one to the answer; you simply add the amount it appears — k to the answer.

139271250

thoughtFreak

Can anyone tell me what is the time complexity of the second solution of problem F?

longbendy

For E, could you use FFT? I see a system of linear equations, and the resulting matrix is circulant. Hence, you could use a FFT and solve it in nlogn time. It's slower than the accepted solution, however. Still would be interesting to do.

tgp07

16 months ago, # |

Instead of pairing up the last 2k numbers like described in the tutorial for problem D, is it possible to just run the following O(n^2) algorithm: For each i in the range [n — 2k + 1, n — 1] we will look for the smallest index j such that arr[i] < arr[j] and then set arr[i] and arr[j] to -1 so that they aren't used anymore. And if we can't find any index j that works, just look for the smallest index j such that arr[i] = arr[j]. Then you just increase answer by 1 and once again set arr[i] and arr[j] to be -1. Finally, add the first n — 2k numbers to the answer as described in the tutorial.

My submission implements this algorithm and didn't pass, so I am wondering if there are any edge cases that break my O(n^2) algorithm. Here is my submission, just in case it is needed.

143369978

BledDest's blog