Tävlingsprogrammering/Uppgifter/Summa summarum
Uppgift[redigera]
https://po.scrool.se/problems/summarum
Lösning[redigera]
Delpoäng[redigera]
Delpoäng på detta problem var simpelt. För varje tal i den första listan så provar vi alla andra i den andra listan. Detta är en kvadratisk algoritm, som fungerar för N upp till runt 1000, men inte mycket större N än så.
Full poäng[redigera]
Full poäng kräver lite mer eftertänksamhet. Vi inser att en kvadratisk lösning inte kommer räcka hela vägen, eftersom den aldrig kommer klara N närmare 100 000.
Anta att vi har två listor A och B. Summan av elementen i den första listan är S_A och summan av elementen i den andra listan är S_B. Anta att vi tittar på ett av elementen i lista A, låt oss kalla elementet x. Nu vill vi lista ut vilket element som är bäst att byta mot i den andra listan. Vi kan börja med att fundera på: vilket skulle detta tal y vara i den andra listan, för att listorna ska få exakt samma summa?
Anta att vi redan stoppat in x i den andra listan, så nu har den summa S_B + x. Första listan har summa S_A - x. Listorna har nu alltså differens S_B-S_A+2x. Vi siktar alltså efter att föra över hälften av detta till den andra listan, för att få exakt samma summa i båda listorna. Då har vi klargjort att talet vi letar efter i den andra listan är (S_B - S_A + 2x)/2. Om inte talet finns (eller om det är udda) i den andra listan så är det förstås optimalt att välja det tal som ligger närmast.
Då återstår bara hur vi effektivare än kvadratisk tid (som den naiva lösningen hade) för varje tal i den första listan hittar det optimala bytet i den andra listan. Tricket här är att vi håller den andra listan sorterad (ordningen har ingen betydelse, eller hur?), och vi binärsöker efter (S_B - S_A + 2x)/2. Finns inte detta tal så måste ett av de närliggande talen (till höger eller till vänster i listan) vara det optimala. Tidskomplexiteten är bra, för varje tal binärsöker vi i den andra listan, vi har alltså en tidskomplexitet som uttrycks O(N log N).
En lurig sak: för sista testfallet så rymdes inte differensen av listornas summa i en 32-bitars int. Det verkade som några av de tävlande märkte detta.
Lösning i C++:
// Summa Summarum, KATT 2013
// Solution by Oskar Werkelin Ahlin
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long L;
int main() {
L N;
cin >> N;
vector<L> arr1, arr2;
L A = 0;
L B = 0;
for (int i = 0; i < N; ++i) {
L cur;
cin >> cur;
arr1.push_back(cur);
A += cur;
}
for (int i = 0; i < N; ++i) {
L cur ;
cin >> cur;
arr2.push_back(cur);
B += cur;
}
sort(arr2.begin(),arr2.end());
L minimum = 1LL<<62;
for (int i = 0; i < N; ++i) {
L diff = B + 2*arr1[i] - A;
// diff/2 är det optimala bytet
L look = ceil(diff/2.0);
// binärsök fram det första tal som är större eller lika med det optimala värdet
size_t pos = (lower_bound(arr2.begin(), arr2.end(),look)-arr2.begin());
// kolla om vi hittade något sådant (pos kommer peka utanför listan om det inte finns)
if (pos < N) {
minimum = min(minimum, abs((B-arr2[pos]+arr1[i]) - (A-arr1[i]+arr2[pos])));
}
--pos;
// sedan provar vi talet innan.
if (pos >= 0) {
minimum = min(minimum, abs((B-arr2[pos]+arr1[i]) - (A-arr1[i]+arr2[pos])));
}
}
cout << minimum << endl;
}
Om vi sorterar både Anders och Beatrices tal (i stigande ordning), vektorerna a[] och b[], så kan vi notera följande. Om summan för Anders tal är större än summan för Beatrices tal och det optimala elementet för a[i] att bytas med är b[j], då gäller att det optimala elementet för a[i+1] att bytas med är större eller lika med b[j], d.v.s. finns i intervallet b[j..n-1]. Om summan för Anders tal är mindre än summan för Beatrices tal och det optimala elementet för a[i] att bytas med är b[j], då gäller att det optimala elementet för a[i+1] att bytas med är mindre eller lika med b[j], d.v.s. finns i intervallet b[0..j].
Detta inspirerar till en så kallad två-pekar-lösning. Där steget att hitta minsta differensen går i O(n), men komplexiteten överlag förblir O(n log n) p.g.a. sorteringen. Observera dock att talen är förhållandevis små med absolutbelopp <= 10^5, så vi skulle med counting sort kunna sortera talen i O(n + K) där K = [storleken på intervallet för alla möjliga tal] vilket i vårt fall är ca 200 000. Dock blir lösningen kortare om vi använder oss av färdiga rutiner. Lösning i Java:
import static java.util.Arrays.sort;
import static java.lang.Math.*;
public class Summarum
{
public static void main(String [] klein)
{
final Kattio in = new Kattio(System.in);
final int n = in.getInt();
final int[] a = new int[n], b = new int[n];
long dif = 0;
for(int i = 0; i<n; i++) dif += a[i] = in.getInt();
for(int i = 0; i<n; i++) dif -= b[i] = in.getInt();
sort(a); sort(b);
long best = 1L<<60, prev;
if(dif>0)
for(int i = 0, j = 1; i<n; i++, best = min(best,prev))
for(prev = abs(dif-2*a[i]+2*b[j-1]); j<n && abs(dif-2*a[i]+2*b[j])<prev; j++)
prev = abs(dif-2*a[i]+2*b[j]);
else
for(int i = 0, j = n-2; i<n; i++, best = min(best,prev))
for(prev = abs(dif-2*a[i]+2*b[j+1]); j>=0 && abs(dif-2*a[i]+2*b[j])<prev; j--)
prev = abs(dif-2*a[i]+2*b[j]);
System.out.println(best);
}
}
Där Kattio är den färdiga IO-klassen som tillhandahålls på uppgiftens hemsida https://po.scrool.se/download/Kattio.java.
Lösning i C som använder sig av en variant av counting sort (av Anton Fors Hurdén):
#include <stdio.h>
#include <stdint.h>
#define abs(x) ((x) > 0 ? (x) : -(x))
#define diff(x, y) abs(d - 2 * a[x] + 2 * b[y])
int64_t a[200001], b[200001], A, B, i, j, d, o = INT64_MAX, n;
int main() {
scanf("%lld", &n);
for (i = 0; i < n; i++)
scanf("%lld", &j),
a[j + 100000]++,
d += j;
for (i = 0; i < n; i++)
scanf("%lld", &j),
b[j + 100000]++,
d -= j;
for (i = 0; i < 200001; i++)
a[i] && (a[A++] = i),
b[i] && (b[B++] = i);
if (d > 0)
for (i = 0, j = 0; i < A; i++)
for (n = diff(i, j), n < o && (o = n); n > (n = diff(i, j + 1)); j++)
n < o && (o = n);
else
for (i = 0, j = 0; i < B; i++)
for (n = diff(j, i), n < o && (o = n); n > (n = diff(j + 1, i)); j++)
n < o && (o = n);
printf("%lld\n", o);
}