Minimize the Error – Codeforces Round 474 (Div. 2)

alt text

Problem Summary

We are given two arrays:

$A$ of size $n$
$B$ of size $n$

The error between them is:

E = \sum_{i=1}^{n} (A_i - B_i)^2

We must perform:

exactly $k_1$ operations on array $A$
exactly $k_2$ operations on array $B$

In one operation, we can choose an element and either:

increase it by $1$
decrease it by $1$

We must output the minimum possible value of $E$ after exactly $(k_1 + k_2)$ operations.

Key Observation

The error depends only on the differences:

d_i = |A_i - B_i|

Because:

(A_i - B_i)^2 = d_i^2

So the problem becomes:

We have an array of differences $d_1, d_2, ..., d_n$ We must perform exactly $k = k_1 + k_2$ operations. In one operation we can modify one $d_i$ by 1.

How Does One Operation Affect $d_i$ ?

If we change $A_i$ or $B_i$ by $1$ , the difference changes by:

either decrease by 1
or increase by 1

But to minimize the error, we always want to reduce the biggest difference.

So the best move is always:

pick the maximum $d_i$
reduce it by 1 (if possible)

Special Case: When the Maximum Difference is 0

If all differences become zero but we still have remaining operations, then:

any operation will make a $0$ become $1$

So:

if $d_i = 0$ , then after one operation it becomes $1$

That is why the greedy rule is:

if $x > 0$ → do $x = x - 1$
else → do $x = x + 1$

Greedy Strategy

At every step:

choose the largest difference
reduce it by 1 (or increase if it’s already 0)
put it back

This greedy is correct because:

the function $x^2$ grows very fast
reducing a large value decreases the total sum much more than reducing a small one

Example:

decreasing $10^2$ to $9^2$ reduces error by 19
decreasing $2^2$ to $1^2$ reduces error by 3

So we always want to reduce the biggest value first.

Why Use a Max Heap?

We need to repeatedly get the maximum difference quickly.

A max heap supports:

extract maximum: $O(\log n)$
insert: $O(\log n)$

So total complexity:

O(k \log n)

Where:

k = k_1 + k_2 \le 1000

So this is very fast.

Algorithm

For each test case:

Read $n, k_1, k_2$
Read arrays $A$ and $B$
Compute differences:

d_i = |A_i - B_i|

Insert all $d_i$ into a max heap
Repeat $k = k_1 + k_2$ times:
- extract maximum $x$
- if $x > 0$ decrease it
- else increase it
- insert it back
Compute final answer:

E = \sum d_i^2

alt text

Complexity Analysis

Building heap: $O(n)$
Each operation: extract + insert = $O(\log n)$
Total operations: $k$

So:

\text{Time} = O(n + k\log n)

With constraints:

$n \le 1000$
$k \le 1000$

This runs easily within limits.

Memory:

O(n)

Final C Code (Heap Solution)

1
#include <stdio.h>
2
#include <stdlib.h>
3

4

5
struct Heap {
6
    int* arr;
7
    int size;
8
    int capacity;
9
};
10
typedef struct Heap heap;
11

12
typedef struct {
13
    int a;
14
    int b;
15
    int diff;
16
} Pair;
17

18
heap* createHeap(int capacity, int* nums);
19
void insertHelper(heap* h, int index);
20
void maxHeapify(heap* h, int index);
21
int extractMax(heap* h);
22
void insert(heap* h, int data);
23
void printHeap(heap* h);
24

25
int cmp(const void *x, const void *y);
26

27
int main()
28
{
29
    int n, k1, k2;
30
    scanf("%d %d %d", &n, &k1, &k2);
31

32
    int A[n], B[n], C[n];
33

34
    for (int i = 0; i < n; i++)
35
        scanf("%d", &A[i]);
36

37
    for (int i = 0; i < n; i++)
38
        scanf("%d", &B[i]);
39

40
    Pair arr[n];
41

42
    for (int i = 0; i < n; i++) {
43
        arr[i].a = A[i];
44
        arr[i].b = B[i];
45
        arr[i].diff = abs(A[i] - B[i]);
46
    }
47

48
    qsort(arr, n, sizeof(Pair), cmp);
49

50
    for (int i = 0; i < n; i++) {
51
        A[i] = arr[i].a;
52
        B[i] = arr[i].b;
53
    }
54

55
    for (int i = 0; i < n; i++) {
56
        C[i] = arr[i].diff;
57
    }
58

59
    heap* h = createHeap(n, C);
60

61
    int k = k1 + k2;
62

63
    for (int i = 0; i < k; i++) {
64
        int x = extractMax(h);
65
        if (x > 0) x--;
66
        else x++;
67

68
        insert(h, x);
69
    }
70

71

72
    long long E = 0;
73

74
    for (int i = 0; i < h->size; i++) {
75
        long long x = h->arr[i];
76
        E += x * x;
77
    }
78

79
    printf("%lld\n", E);
80

81
    return 0;
82

83
}
84

85
heap* createHeap(int capacity, int* nums)
86
{
87
    heap* h = (heap*)malloc(sizeof(heap));
88
    if (h == NULL) {
89
        printf("Memory error\n");
90
        return NULL;
91
    }
92

93
    h->size = capacity;
94
    h->capacity = capacity;
95

96
    h->arr = (int*)malloc(capacity * sizeof(int));
97
    if (h->arr == NULL) {
98
        printf("Memory error\n");
99
        free(h);
100
        return NULL;
101
    }
102

103
    for (int i = 0; i < capacity; i++)
104
        h->arr[i] = nums[i];
105

106
    // Build heap
107
    for (int i = (h->size - 2) / 2; i >= 0; i--)
108
        maxHeapify(h, i);
109

110
    return h;
111
}
112

113
void insertHelper(heap* h, int index)
114
{
115
    if (index == 0)
116
        return;
117

118
    int parent = (index - 1) / 2;
119

120
    if (h->arr[parent] < h->arr[index]) {
121
        int temp = h->arr[parent];
122
        h->arr[parent] = h->arr[index];
123
        h->arr[index] = temp;
124

125
        insertHelper(h, parent);
126
    }
127
}
128

129
void maxHeapify(heap* h, int index)
130
{
131
    int left = index * 2 + 1;
132
    int right = index * 2 + 2;
133
    int max = index;
134

135
    if (left < h->size && h->arr[left] > h->arr[max])
136
        max = left;
137

138
    if (right < h->size && h->arr[right] > h->arr[max])
139
        max = right;
140

141
    if (max != index) {
142
        int temp = h->arr[max];
143
        h->arr[max] = h->arr[index];
144
        h->arr[index] = temp;
145

146
        maxHeapify(h, max);
147
    }
148
}
149

150
int extractMax(heap* h)
151
{
152
    if (h->size == 0) {
153
        printf("Heap is empty.\n");
154
        return -999;
155
    }
156

157
    int deleteItem = h->arr[0];
158
    h->arr[0] = h->arr[h->size - 1];
159
    h->size--;
160

161
    maxHeapify(h, 0);
162
    return deleteItem;
163
}
164

165
void insert(heap* h, int data)
166
{
167
    if (h->size >= h->capacity) {
168
        printf("Heap is full.\n");
169
        return;
170
    }
171

172
    h->arr[h->size] = data;
173
    h->size++;
174

175
    insertHelper(h, h->size - 1);
176
}
177

178
void printHeap(heap* h)
179
{
180
    for (int i = 0; i < h->size; i++)
181
        printf("%d ", h->arr[i]);
182
    printf("\n");
183
}
184
int cmp(const void *x, const void *y)
185
{
186
    Pair *p1 = (Pair *)x;
187
    Pair *p2 = (Pair *)y;
188
    return p1->diff - p2->diff;
189
}

alt text

Takeaways

The problem only depends on the differences $|A_i - B_i|$ .
Minimizing the sum of squares requires always reducing the maximum difference.
A max heap is perfect to repeatedly extract the current maximum efficiently.
If all values become $0$ but operations remain, the answer increases (because we must still perform operations).

This greedy + heap approach is the standard optimal solution for this problem.

Minimize the Error – Codeforces Round 474 (Div. 2) Writeup

Minimize the Error – Codeforces Round 474 (Div. 2)

Problem Summary

Key Observation

How Does One Operation Affect did_idi​?

Special Case: When the Maximum Difference is 0

Greedy Strategy

Why Use a Max Heap?

Algorithm

Complexity Analysis

Final C Code (Heap Solution)

Takeaways

How Does One Operation Affect $d_i$ ?