Problem link: https://codeforces.com/contest/1618/problem/D
Wrong answer submission: https://codeforces.com/contest/1618/submission/189086969
Correct answer submission: https://codeforces.com/contest/1618/submission/189088442
Approach for correct answer is, we combine n-2*k and n-k (0-indexed), then n-2*k+1 and n-k+1 and so on... till n-k-1 and n-1
I feel like same thing I am doing with stack as well in wrong answer submission, what I am doing is, I am combining current element with a next element that is different using stack, so that when divide we get 0. And finally when there are still elements present, count of it will be obviously even, so just count/2 times 1 will be added. But it is showing wrong answer.
Example
3 3 4 4 5 5 6 6
Combining 3 and 4,then 3 and 4, then 5 and 6, then 5 and 6.
In which case this fails?
I can clearly tell that you have the correct idea. You want to combine the 2*k biggest elements in the array in such a way such that the least number of pairs of numbers are equal. However, it seems like you made one greedy assumption which is incorrect. This assumption is that: to minimise the number of pairs of numbers that are equal, for each number, i just have to find another number that is different from it.
For example, in your example:
8 4
3 3 4 4 5 5 6 6
You first add both 3s to the stack. Then, you look at 4. 3 (which is at the top of the stack) is different from 4 so you combine it. And you keep doing this until the end. However, this is a wrong greedy approach. Because consider the testcase:
6 3
1 1 2 2 3 3.
Your code will incorrectly combine the numbers (1, 2), (1, 2), (3, 3) which has a cost of 1. However, using the following combinations, (1, 2), (1, 3), (3, 2), you can achieve a score of 0.
However, considering this, i cannot give you a concise explanation of why the correct submission you posted works. Instead, I can give you how I would implement it.
Notice that you are only forced to combine two numbers that are equal if that number occurs more than k times in the last 2*k numbers. Furthermore, let x be the number of times that a number appears in the last 2*k numbers. If x <= k, then don't increment answer. Otherwise, ans += x — k.
All you have to do to implement this is store the number of times each number occurs in a map. then loop through the map and make the corresponding changes to the answer.
This is my relatively simple correct submission: https://codeforces.com/contest/1618/submission/189125639