BledDest's blog

By BledDest, 5 months ago, In English

1618A - Polycarp and Sums of Subsequences

Idea: Brovko, preparation: Brovko

Tutorial
Solution (Brovko)

1618B - Missing Bigram

Idea: BledDest, preparation: awoo

Tutorial
Solution (awoo)

1618C - Paint the Array

Idea: BledDest, preparation: BledDest

Tutorial
Solution (BledDest)

1618D - Array and Operations

Idea: BledDest, preparation: BledDest

Tutorial
Solution (BledDest)

1618E - Singers' Tour

Idea: shnirelman, preparation: shnirelman

Tutorial
Solution (shnirelman)

1618F - Reverse

Idea: Lankin, preparation: Lankin

Tutorial
Solution (awoo)
Solution (BledDest)

1618G - Trader Problem

Idea: BledDest, preparation: BledDest

Tutorial
Solution (awoo)
Solution (BledDest)
 
 
 
 
  • Vote: I like it
  • +93
  • Vote: I do not like it

»
5 months ago, # |
  Vote: I like it +32 Vote: I do not like it

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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I also had the same thought, that's why I submitted A pretty quickly (I just looked up for my old submission)

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
5 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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 :((

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

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

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you! I didn't notice I also changed that. That makes much more sense.

»
5 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like 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.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        5 months ago, # ^ |
        Rev. 2   Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    See basically we took first 2*k elements from the array(sorted in descending order) and now we have to pair these 2*k elements. we make pair in such a way that both numbers are not same else it will add 1 to the final score . so if we pick an element then we will look for it's partner that is as far from it and that could be max 'k' distance apart. if we take partners at a distance greater than k then all elements will not able to form pairs. Also we always take farthest because if we take closest ones then they could be same as they are in descending order so we try to avoid this.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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).

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Same here.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This is what I was searching for. I have also done the same because the same concept was asked in a div3 D problem just a few contests ago. My question is ,what is the reason for using priority queue there? What is the intution that makes you think that a priority queue will be appropriate to solve that part of the problem ?

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I tried D with DP I was getting WA for testcase 2. I am not getting where I am going wrong,

Please check my submission and please tell where I am going wrong

Submission Link : My Submission Code

Thanks in advance for helping

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Spoiler
    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes :(

      Got your point , I am just checking of i+1,j-1 and i,j-2. That's mistake.Is there any way to solve this problem using dp?

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        During contest, I came up with greedy approach. I don't know if there is any dp solution for this.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it
    1. add 0 and reverse (10111 -> 11101)
    2. add 1 and reverse (110111)
    3. add 0 and reverse (111011)
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain C question? How do we know , when to use this idea of gcd?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We have to find a number d which will divide either array a or b ( a and b are decided from original array) Now gcd(a) will give you that number d.

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Lets us assume (a1,a3,...ap) and (a2,a4,...aq) be the set of elements present in odd and even positions respectively.

    Consider a case where a number K is a value such that it divides all numbers present in elements in odd indices and doesn't divide any of the elements in the even indices. So to find K one naive approach could be to traverse from 2 to MAX_POSSIBLE and then, you will find K in between. But is it optimal?? NO

    Now consider a scenario where G is the largest possible value of K (satisfying the condition of dividing all elements in even indices and not dividing any of the elements in odd index or vice versa), no matter how many of K values satisfies this criterion, G always does (assuming there is a solution). Because if there is a K value P < G, that doesn't divide a set of numbers then implicitly G also doesn't divide those numbers as G will be t*P since we are talking about common divisors. So now what's the largest number G nothing but G.C.D, so since we can find G.C.D efficiently , there is no need to do traversal from 2 to MAX to find GCD.

    Hope it helps and any feedback or suggestions are appreciated. Thank you :)

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone help Where it fails Solution of D : https://codeforces.com/contest/1618/submission/139321551

  • »
    »
    5 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it
    1
    8 3
    1 1 6 6 6 6 2 2
    

    The answer is 3, you get 4, Btw I hacked my submission with this input :))

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved D using greedy approach. For each unique element assign a count where count is the number of elements with the same value. Store the pair {num, count(num)} in a list and create two lists with elements sorted in ascending and descending order. Greedily, come from front and back respectively for both. Minimum of both these is the answer.

Submission: https://codeforces.com/contest/1618/submission/139296896

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone please explain the intuition behind problem C?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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 ?

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Bt how can you prove that it will be the greatest common divisor but not other any divisor?

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Because, see, if the other numbers are not divisible by GCD , then GCD is the answer. If GCD divides at least one of the numbers that is supposed not to be divisible by the GCD ,then all the factors of GCD will also divide that number. Let GCD=x, the number that it divides is y which is supposed not to be divisible by x . Now let z be a factor of x. if x divides y, then z also divides y. if any other number is there other than GCD that divides all the numbers that it is supposed to divide, then this divisor will always be a factor of GCD. So it will face the same obstacle as the GCD faces .

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/blog/Ancient221 This may help if you have any query in Problem-D or if your solution was hacked.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Really the nice problemset but i am able to solve 2 problems;)

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D for last 2k element instead of calculation sum of n−2k+i/n−k+i i had calculated sum of n-2k-1+i/n-1-i in sorted order and got wrong.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

Spoiler
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In this submission : https://codeforces.com/contest/1618/submission/139367835 , I am using z/n > n and my submission is getting WA , when I remove it : https://codeforces.com/contest/1618/submission/139368605 , I am getting AC

I am not able to understand why it is like that, z/n >n is correct, it can be redundant, but not wrong according to me, Please help in this

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I really loved the last question! Thanks for the instructive editorial, got to learn many things :)

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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]);

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You need to use Markdown in the code(like good[i % 2] = good[i % 2] && (a[i] % g[(i % 2) ^ 1] > 0);.

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Just testing...

      Test of code formatting
      
      int i = 0, x = 0;
      while (i < 100) x++;
      cout << x;
      

      ---

      test of bold font

      ---

      test of italics

»
5 months ago, # |
  Vote: I like it +7 Vote: I do not like it

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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi guys I need some help with problem D.

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

I seem to be off by 1 in the test case and I can't seem to understand why. Much appreciated.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If possible, add graphs tag to problem F.

»
5 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Nice solution bro!

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    576460752303423487 is 11...11 (59 times)

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
5 months ago, # |
Rev. 2   Vote: I like it -6 Vote: I do not like it

Can Somebody help with problem C my code was giving me TLE but I think its logic is similar to the solution?

#include <bits/stdc++.h>
#define ll int
#define pb push_back
#define ld long double
 
using namespace std;
 
//Global variables
ll t, n, k, m;
const ll template_size = 100002;
//template arrays
// ll a[template_size] = {};
// ll b[template_size] = {};
// ll dp[template_size] = {};
 
 
int main()
{
	//makes the io faster
	ios::sync_with_stdio(0);
	cin.tie(0);
 
	t = 1;
	cin >> t;
	while (t--)
	{
		cin >> n;
		vector<ll> a(n,0);
		ll ge,  go;
		cin >> a[0];
		cin >> a[1];
		ge = a[0];
		go = a[1];
		for (int i{2}; i < n; i++){
			cin >> a[i];
			if (i%2 == 0){
				ge = __gcd(ge, a[i]);
			}
			if (i%2 != 0){
				go = __gcd(go, a[i]);
			}
		}
		// if (ge == go){
		// 	cout << 0 << '\n';
		// 	continue;
		// }
		ll ans{0};
		bool flag1 = true, flag2 = true;
		for(int i{}; i < n; i++){
			if (i%2 == 0){
				flag1 = flag1 & (a[i]%go != 0);
			}
			else {
				flag2 = flag2 & (a[i]%ge != 0);
			}
		}
		
		if (flag2){
			ans = max(ans, ge);
		}
		if (flag1){
			ans = max(ans, go);
		}
		cout << ans << '\n';
	}
 
	return 0;
}
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You need to use Markdown in your code(the first 7 lines).

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I need help in C.

My logic find min of all elements at odd position and min of all elements at even position. Then I find all divisors of both the numbers and store it in a map of divisors vs frequency.

Then I iterate map and if frequency of any element is 1, I check if it divides all even and no odd position elements or all odd and no even position elements. It gives WA in my code. please help.

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

»
5 months ago, # |
Rev. 3   Vote: I like it +9 Vote: I do not like it

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]$$$.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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).

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh,you are right! It works. This problem has confused me for a long time. Thanks bro!

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

good game

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what means g[(i % 2) ^ 1] ?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

is anybody tell me why i use cout it will print `'�?���;�? but the code can run perfectly on my computer?

»
5 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain what awoo implemented in problem G in having trouble. in understanding it.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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