I Tried to Write A Solution for this Problem.↵
==================↵
### D. Array and Operations Codeforces Round 760 (Div. 3)↵
https://codeforces.net/problemset/problem/1618/D↵
↵
#### Observation <br>↵
1. When performing an operation where $a_i = a_j$, the score will increase by `1`, ↵
because if $a_i \equiv x$, then:↵
$$↵
\left\lfloor \frac{a_i}{a_j} \right\rfloor \Leftrightarrow ↵
\left\lfloor \frac{x}{x} \right\rfloor \Leftrightarrow ↵
\lfloor 1 \rfloor \Leftrightarrow↵
$$↵
On the other hand, when performing an operation where $a_i \neq a_j$, the score will minimally increase by `0`, ↵
because if $a_i < a_j$, then:↵
$$↵
\left\lfloor \frac{a_i}{a_j} \right\rfloor = 0,↵
$$↵
and vice versa.↵
↵
2. Exactly $k$ operations will be performed on an array of $n$ integers, where each operation ↵
increases the score according to the rule in point 1. ↵
Additionally, there are $n - (2 \cdot k)$ integers that will be added to the score without any special operation.↵
Thus, $\boxed{2 \cdot k}$ numbers undergo operations, and $\boxed{n - (2\cdot k)}$ numbers do not.↵
↵
---↵
↵
#### Steps <br>↵
↵
1. Sort the array in ascending order.↵
↵
2. Add $ \displaystyle{\sum_{i = 1}^{n-2\cdot k}a_i}$ to the score. ↵
I believe this is correct because $n - 2 \cdot k$ numbers without operations should be taken from the ↵
beginning of the sorted array to minimize the score addition (proof unknown). ↵
The next step is to exhaust the remaining numbers in the array with special operations,↵
where the remaining numbers are guaranteed to be even in count.↵
↵
3. The final step is to increase the score using special operations. ↵
The main goal of this step is to pair each number, ensuring:↵
as much as possible, avoid pairing the same number to minimize the score increase to 0 ↵
(following the rule in Observation point 1).↵
↵
---↵
↵
#### Conjecture for Step 3↵
↵
Example of an array after Step 2: [1, 1, 1, 1, 2, 3] ↵
Optimal pairing: [1, 2], [1, 3], [1, 1] ↵
↵
From the example above, the conjecture can be stated as: ↵
$$↵
\text{if } (f_{max} > f_{total} - f_{max}) \text{ then}↵
$$↵
$$↵
\text{score} = \text{score} + \frac{f_{max} - (f_{total} - f_{max})}{2}↵
$$↵
where $f =$ frequency of a number. ↵
↵
For the example above, the frequencies are: ↵
$1:4$, $2:1$, $3:1$. ↵
↵
$$↵
f_{total} = 6, \, f_{max} = 4, \, \text{and } f_{total} - f_{max} = 2.↵
$$↵
↵
---↵
↵
#### Proof for Step 3↵
↵
There are three critical variables: ↵
- $m = f_{max}$ ↵
- $t = f_{total} - f_{max}$ ↵
- $g = \frac{m + t}{2}$ ↵
↵
*Note*: ↵
- $m =$ number of occurrences of the number with the maximum frequency. ↵
- $t =$ total frequency of all numbers except for the number with the maximum frequency. ↵
- $g =$ total groups formed, where each group contains 2 numbers. ↵
↵
If $m > t$: the maximum frequency of a number exceeds the total frequency of other numbers. ↵
This means there are cases where a number is paired with itself. Why can this happen? ↵
I recall the pigeonhole principle from discrete mathematics. ↵
The number of pigeonholes is $g$, and there are $m + t$ pigeons entering the pigeonholes in order, ↵
starting with $m$ followed by $t$. ↵
The same number will end up in the same pigeonhole if $m > g$. ↵
$$↵
m > g ↵
$$↵
$$ m > \frac{m + t}{2} $$↵
$$ 2 \cdot m > m + t $$↵
$$ m > t $$↵
Since $m > g$ and each pigeonhole already contains one pigeon of value $f_{max}$, ↵
there are $m - g$ pigeons that will fly to the pigeonholes already containing a pigeon of the same value.↵
It is then to be added to the score.↵
$$↵
m - g↵
$$↵
$$ m - \frac{m + t}{2} $$↵
$$ \frac{2 \cdot m}{2} - \frac{m + t}{2} $$↵
$$ \frac{2 \cdot m - (m + t)}{2} $$↵
$$ \boxed{\frac{m - t}{2}} $$↵
↵
` Remaining pigeons entering will not affect the score, as they are of different values. `↵
↵
---↵
↵
#### Proof if $m \leq t \Rightarrow \text{score} = \text{score} + 0$↵
↵
This visualization does not use pigeonholes but instead uses rows of 2. ↵
The grouping is organized as: ↵
$row_1, column_i$ with $row_2, column_i$. ↵
↵
Example grouping for the array [1, 1, 1, 1, 2, 3]: ↵
$ \boxed{1} \boxed{1} \boxed{1} $ <br>↵
$ \boxed{1} \boxed{2} \boxed{3} $ <br>↵
↵
↵
Example of grouping when $m = 4\;and\; t = 6:$ <br>↵
$ \boxed{x} \ \boxed{x} \ \boxed{x} \ \boxed{x} \ \boxed{y} $ <br>↵
$ \boxed{y} \ \boxed{z} \ \boxed{z} \ \boxed{a} \ \boxed{b} $ <br>↵
where $x$ is the maximum frequency. <br>↵
↵
↵
If $m = t$, then the grouping will look like this: <br>↵
$ \boxed{x} \ \boxed{x} \ \boxed{x} \ \boxed{x} $ <br>↵
$ \boxed{y} \ \boxed{y} \ \boxed{y} \ \boxed{z} $ <br>↵
The first row will always contain $m$ and the second row will contain $t$. \\↵
Thus, each group will always have different pairs. <br>↵
`Score does not increase.`↵
↵
↵
If $m < t$, then↵
$$↵
m < t↵
$$↵
$$↵
m + m < t + m↵
$$↵
$$↵
2 \cdot m < t + m↵
$$↵
$$↵
\frac{2\cdot m}{2} < \frac{t + m}{2}↵
$$↵
$$↵
m < \frac{t + m}{2}↵
$$↵
$$↵
\boxed{m < g}↵
$$↵
Since $m < g \Rightarrow$ the construction of the first row will have leftover space for placing $t$ (all m is to be ↵
constructed first). <br>↵
$ \boxed{x} \ \boxed{x} \ \boxed{x} \ \boxed{?} $ <br>↵
$ \boxed{?} \ \boxed{?} \ \boxed{?} \ \boxed{?} $ <br>↵
↵
↵
There will be numbers grouped with the same numbers if and only if↵
there is a number from the first row that meets again in the second row↵
as shown in the following example. <br>↵
$ \boxed{x} \ \boxed{x} \ \boxed{x} \ \boxed{y} $ <br>↵
$ \boxed{y} \ \boxed{y} \ \boxed{y} \ \boxed{y} $ <br>↵
> `However, this cannot happen because the following condition cannot be met: `↵
$$ \boxed{y \geq g + 1} $$ <br>↵
> where $y$ is the frequency of one of $t$. <br>↵
Since $m < g$ and $y \leq m$, we have $$ \boxed{y < g} $$ <br>↵
`Score does not increase.`↵
↵
---↵
↵
<spoiler summary="C++ Code">↵
```c++↵
int main() {↵
fastio;↵
↵
int t;↵
cin >> t;↵
↵
while (t--) {↵
int n, k;↵
cin >> n >> k;↵
↵
vector<int> arr(n);↵
for (auto &x : arr) cin >> x;↵
↵
sort(arr.begin(), arr.end());↵
↵
int score = 0;↵
int ptr = 0;↵
for (int i = 0; i < n - k * 2; i++) {↵
score += arr[ptr];↵
ptr++;↵
}↵
if (debug) cout << "pointer now " << ptr << endl;↵
↵
vector<int> cnt(LIMIT);↵
for (; ptr < n; ptr++) {↵
cnt[arr[ptr]]++;↵
}↵
↵
int max_idx = 0;↵
int total = 0;↵
for (int i = 0; i < LIMIT; i++) {↵
if (cnt[i] > cnt[max_idx]) {↵
max_idx = i;↵
}↵
total += cnt[i];↵
} ↵
↵
total -= cnt[max_idx];↵
if (cnt[max_idx] > total) {↵
score += (cnt[max_idx] - total) / 2;↵
}↵
↵
cout << score << endl;↵
}↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
==================↵
### D. Array and Operations Codeforces Round 760 (Div. 3)↵
https://codeforces.net/problemset/problem/1618/D↵
↵
#### Observation <br>↵
1. When performing an operation where $a_i = a_j$, the score will increase by `1`, ↵
because if $a_i \equiv x$, then:↵
$$↵
\left\lfloor \frac{a_i}{a_j} \right\rfloor \Leftrightarrow ↵
\left\lfloor \frac{x}{x} \right\rfloor \Leftrightarrow ↵
\lfloor 1 \rfloor \Leftrightarrow↵
$$↵
On the other hand, when performing an operation where $a_i \neq a_j$, the score will minimally increase by `0`, ↵
because if $a_i < a_j$, then:↵
$$↵
\left\lfloor \frac{a_i}{a_j} \right\rfloor = 0,↵
$$↵
and vice versa.↵
↵
2. Exactly $k$ operations will be performed on an array of $n$ integers, where each operation ↵
increases the score according to the rule in point 1. ↵
Additionally, there are $n - (2 \cdot k)$ integers that will be added to the score without any special operation.↵
Thus, $\boxed{2 \cdot k}$ numbers undergo operations, and $\boxed{n - (2\cdot k)}$ numbers do not.↵
↵
---↵
↵
#### Steps <br>↵
↵
1. Sort the array in ascending order.↵
↵
2. Add $ \displaystyle{\sum_{i = 1}^{n-2\cdot k}a_i}$ to the score. ↵
I believe this is correct because $n - 2 \cdot k$ numbers without operations should be taken from the ↵
beginning of the sorted array to minimize the score addition (proof unknown). ↵
The next step is to exhaust the remaining numbers in the array with special operations,↵
where the remaining numbers are guaranteed to be even in count.↵
↵
3. The final step is to increase the score using special operations. ↵
The main goal of this step is to pair each number, ensuring:↵
as much as possible, avoid pairing the same number to minimize the score increase to 0 ↵
(following the rule in Observation point 1).↵
↵
---↵
↵
#### Conjecture for Step 3↵
↵
Example of an array after Step 2: [1, 1, 1, 1, 2, 3] ↵
Optimal pairing: [1, 2], [1, 3], [1, 1] ↵
↵
From the example above, the conjecture can be stated as: ↵
$$↵
\text{if } (f_{max} > f_{total} - f_{max}) \text{ then}↵
$$↵
$$↵
\text{score} = \text{score} + \frac{f_{max} - (f_{total} - f_{max})}{2}↵
$$↵
where $f =$ frequency of a number. ↵
↵
For the example above, the frequencies are: ↵
$1:4$, $2:1$, $3:1$. ↵
↵
$$↵
f_{total} = 6, \, f_{max} = 4, \, \text{and } f_{total} - f_{max} = 2.↵
$$↵
↵
---↵
↵
#### Proof for Step 3↵
↵
There are three critical variables: ↵
- $m = f_{max}$ ↵
- $t = f_{total} - f_{max}$ ↵
- $g = \frac{m + t}{2}$ ↵
↵
*Note*: ↵
- $m =$ number of occurrences of the number with the maximum frequency. ↵
- $t =$ total frequency of all numbers except for the number with the maximum frequency. ↵
- $g =$ total groups formed, where each group contains 2 numbers. ↵
↵
If $m > t$: the maximum frequency of a number exceeds the total frequency of other numbers. ↵
This means there are cases where a number is paired with itself. Why can this happen? ↵
I recall the pigeonhole principle from discrete mathematics. ↵
The number of pigeonholes is $g$, and there are $m + t$ pigeons entering the pigeonholes in order, ↵
starting with $m$ followed by $t$. ↵
The same number will end up in the same pigeonhole if $m > g$. ↵
$$↵
m > g ↵
$$↵
$$ m > \frac{m + t}{2} $$↵
$$ 2 \cdot m > m + t $$↵
$$ m > t $$↵
Since $m > g$ and each pigeonhole already contains one pigeon of value $f_{max}$, ↵
there are $m - g$ pigeons that will fly to the pigeonholes already containing a pigeon of the same value.↵
It is then to be added to the score.↵
$$↵
m - g↵
$$↵
$$ m - \frac{m + t}{2} $$↵
$$ \frac{2 \cdot m}{2} - \frac{m + t}{2} $$↵
$$ \frac{2 \cdot m - (m + t)}{2} $$↵
$$ \boxed{\frac{m - t}{2}} $$↵
↵
` Remaining pigeons entering will not affect the score, as they are of different values. `↵
↵
---↵
↵
#### Proof if $m \leq t \Rightarrow \text{score} = \text{score} + 0$↵
↵
This visualization does not use pigeonholes but instead uses rows of 2. ↵
The grouping is organized as: ↵
$row_1, column_i$ with $row_2, column_i$. ↵
↵
Example grouping for the array [1, 1, 1, 1, 2, 3]: ↵
$ \boxed{1} \boxed{1} \boxed{1} $ <br>↵
$ \boxed{1} \boxed{2} \boxed{3} $ <br>↵
↵
↵
Example of grouping when $m = 4\;and\; t = 6:$ <br>↵
$ \boxed{x} \ \boxed{x} \ \boxed{x} \ \boxed{x} \ \boxed{y} $ <br>↵
$ \boxed{y} \ \boxed{z} \ \boxed{z} \ \boxed{a} \ \boxed{b} $ <br>↵
where $x$ is the maximum frequency. <br>↵
↵
↵
If $m = t$, then the grouping will look like this: <br>↵
$ \boxed{x} \ \boxed{x} \ \boxed{x} \ \boxed{x} $ <br>↵
$ \boxed{y} \ \boxed{y} \ \boxed{y} \ \boxed{z} $ <br>↵
The first row will always contain $m$ and the second row will contain $t$. \\↵
Thus, each group will always have different pairs. <br>↵
`Score does not increase.`↵
↵
↵
If $m < t$, then↵
$$↵
m < t↵
$$↵
$$↵
m + m < t + m↵
$$↵
$$↵
2 \cdot m < t + m↵
$$↵
$$↵
\frac{2\cdot m}{2} < \frac{t + m}{2}↵
$$↵
$$↵
m < \frac{t + m}{2}↵
$$↵
$$↵
\boxed{m < g}↵
$$↵
Since $m < g \Rightarrow$ the construction of the first row will have leftover space for placing $t$ (all m is to be ↵
constructed first). <br>↵
$ \boxed{x} \ \boxed{x} \ \boxed{x} \ \boxed{?} $ <br>↵
$ \boxed{?} \ \boxed{?} \ \boxed{?} \ \boxed{?} $ <br>↵
↵
↵
There will be numbers grouped with the same numbers if and only if↵
there is a number from the first row that meets again in the second row↵
as shown in the following example. <br>↵
$ \boxed{x} \ \boxed{x} \ \boxed{x} \ \boxed{y} $ <br>↵
$ \boxed{y} \ \boxed{y} \ \boxed{y} \ \boxed{y} $ <br>↵
> `However, this cannot happen because the following condition cannot be met: `↵
$$ \boxed{y \geq g + 1} $$ <br>↵
> where $y$ is the frequency of one of $t$. <br>↵
Since $m < g$ and $y \leq m$, we have $$ \boxed{y < g} $$ <br>↵
`Score does not increase.`↵
↵
---↵
↵
<spoiler summary="C++ Code">↵
```c++↵
int main() {↵
fastio;↵
↵
int t;↵
cin >> t;↵
↵
while (t--) {↵
int n, k;↵
cin >> n >> k;↵
↵
vector<int> arr(n);↵
for (auto &x : arr) cin >> x;↵
↵
sort(arr.begin(), arr.end());↵
↵
int score = 0;↵
int ptr = 0;↵
for (int i = 0; i < n - k * 2; i++) {↵
score += arr[ptr];↵
ptr++;↵
}↵
if (debug) cout << "pointer now " << ptr << endl;↵
↵
vector<int> cnt(LIMIT);↵
for (; ptr < n; ptr++) {↵
cnt[arr[ptr]]++;↵
}↵
↵
int max_idx = 0;↵
int total = 0;↵
for (int i = 0; i < LIMIT; i++) {↵
if (cnt[i] > cnt[max_idx]) {↵
max_idx = i;↵
}↵
total += cnt[i];↵
} ↵
↵
total -= cnt[max_idx];↵
if (cnt[max_idx] > total) {↵
score += (cnt[max_idx] - total) / 2;↵
}↵
↵
cout << score << endl;↵
}↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
