Февруарско състезание на USACO, 2005, Задача GOLD1. Jersey Politics
Условието на задачата може да прочетете
тук.
Решение
За тази задача ще предложа две решения, първото от които е “алчно”,
а второто динамично.
И за двете решения ползваме факта че K-те града с най-малко избиратели ще оставим неизползвани, а
ще се опитаме да конструираме решение само с останалите 2*К града. Задачата се свежда до това да разделим множество от 2*К числа на две групи от по К така че разликата от сбора на числата
в двете групи да е минимална.
И така “алчното” решение обхожда на двойки градовете
както са наредени по големина и за всяка двойка решава кое от числата към коя
от групите като поставим разликата между сбора на елементите в двете множества
до момента ще е минимална. На края на това “алчно” разпределяне на градовете в
две множества по К елемента има вероятност да не сме успели да разделим елементите
достатъчно добре и сумата в едното множество да е по–малка или равна от К*500.В тази ситуация намираме един елемент в едното множество и един в
другото, такива че ако им разменим местата разликата между сумите на двете
множества ще се намалее (евентуално множеството чиято сума до преди това е била
по–малка или равна на К*500 ще се
увеличи и ще удовлетворява условието за решение, но е възможно и да влоши
другата сума). И така докато не намерим решение и разполагаме с два елемента,
които като разменим ще получим намаляване на разликата между сумите – разменяме
ги. Ако обаче няма вече такива елементи, а още не сме конструирали решение,
избираме произволни два (най-добре random) и ги сменяме, след което
продължаваме да правим “подобряващи размени” докато не намерим решение. В
случай че пак свършат “подобряващите размени”, отново сменяме два произволни
елемента и пак продължаваме търсенето. Забележете че този алгоритъм ще работи
вечно ако не съществува решение, но в условието съществуването е гарантирано и
се оказва, че той
работи правилно на всички тестове за по – малко от 0.01 сек/тест.
Второто решение се базира на динамичното оптимиране.
Ще намерим всички възможни суми от К
елемента, а щом намерим сума която е по – голяма от 500*К исъщо така сумата от
оставащите елементи е по – голяма от 500*К
тогава значи сме намерили решение. За целта ще ни трябва квадратен масив с
размер 60000 на 60 (1000*К на К), където opt[i][j]ще е равно на 1,когато можем да конструираме сума i,използвайки jелемента. В процеса на динамичното
оптимиране щепробваме да включим всеки един елемент в сумите по следния
начин. Ако d[p]е елемента който ще ползваме
на тази стъпка за конструирането на решения то:
Ако opt[i]][j] = 1, то opt[i+d[p]][j+1]
= 1 .
Като попълваме таблицата отзад напред за да избегнем решения,
конструирани с използването на даден елемент два пъти в получаването на една
сума. Ако тръгнем да попълваме клетка на която i+d[p] > 500*K и j+1=K,
то това е едно потенциално решение и трябва да проверим дали сумата на
останалите елементи е също > 500*К.
В противен случай продължаваме попълването на таблицата. Като на всяка стъпка
ние ползваме един от елементите и обхождаме цялата таблица опитвайки се да
генерираме нов суми с него. Това прави сложността на задачата К*1000*К*К или К^3*1000 което при К = 60
е 216*10^6 операции. Това е твърде
много за ограничението то 0.3 сек изатова се налагат оптимизации. Подходящо би било да обхождаме елементите
от по-големите към по – малките(по този
начин по – бързо ще достигаме до решения). Също така на стъпката когато
използваме p-тия елемент е нужно да обхождаме
клетките в масива opt[i][j]само с j<=p. За да можем да изведем и кои са
числата в двете множества ще трябва и още един масив в който да пазим с използването
на кой последен елемент е конструирана съответната сума.
Примерни реализации:
/*
PROG:jpol
LANG:C++
Nikola Borisof
*/
# include <stdio.h>
# include <stdlib.h>
# define MAXK 64
int d[MAXK*3]; // входните данни
int ind[MAXK*3]; // помощен масив за сортиране
//на входните данни така че да не ги разместваме
int g[MAXK*3]; // този масив оказва даден елемент
//в кое множество е 1,2 или 3
int k;
int cmp(const void *e1, const void *e2) {
return d[*(int *)e1]-d[*(int *)e2];
}
void readf() {
// четене на входа
freopen("jpol.in","r",stdin);
freopen("jpol.out","w",stdout);
scanf("%d",&k);
for ( int i=0 ; i<k*3 ; i++ ) {
scanf("%d",&d[i]);
ind[i] = i;
}
// сортираме масива d[] посредством масива ind[] който съдържа индекси
// примерно d[ind[0]] - е най-малкия
// елемент а d[ind[3*k-1]] - най-големия
qsort(ind,3*k,sizeof(int),cmp);
}
void solve() {
// отбелязваме най-малките числа от множеството като
// част от другия регион за гласуване
// и ги изклучваме от търсенето на решение
for ( int i=0 ; i<k ; i++ ) {
g[ind[i]] = 3;
}
int sum1,sum2;
sum1 = sum2 = 0;
for ( int i=k ; i<3*k ; i+=2 ) {
// проверяваме дали ако сложим елемента d[ind[i]] в
// първото множество а d[ind[i+1]] във второто е
// по-добре от обратното.
if ( abs(sum1+d[ind[i]]-sum2-d[ind[i+1]])<
abs(sum1-d[ind[i]]-sum2+d[ind[i+1]]) ) {
sum1+=d[ind[i]];
g[ind[i]] = 1;
sum2+=d[ind[i+1]];
g[ind[i+1]] = 2;
} else {
sum1+=d[ind[i+1]];
g[ind[i+1]] = 1;
sum2+=d[ind[i]];
g[ind[i]] = 2;
}
}
double p1,p2;
p1 = (double)sum1/(double)k; p2 = (double)sum2/(double)k; // p1 и p2
// - коефициентите на първото и второто множество
// ако и двете са > 500 намерили сме решение
// Проверяваме дали сме намерили решение
while ( p1<=500.000000001 || p2<=500.00000001 ) {
int i;
for ( i=0 ; i<3*k ; i++ ) {
if ( g[i]==1 ) {
for ( int j=0 ; j<3*k ; j++ ) {
if ( g[j]==2 ) {
// ако разместването на d[i] и d[j]
// ще подобри положението разменяме ги
if ( abs(sum1-2*d[i]+2*d[j]-sum2)<abs(sum1-sum2) ) {
sum1 = sum1 - d[i]+d[j];
sum2 = sum2 - d[j]+d[i];
g[i] = 2;
g[j] = 1;
i = 3*k+4; // излизаме от първия цикъл 3*к+4
//за да знамем после дали сме минали от тук
break; // излизаме от втория цикъл
}
}
}
}
}
// ако НЕ сме направили някаква размяна ще
// влезем в този if и ще направим произволната размяна
if ( i != 3*k+5 ) {
for ( i=0 ; i<3*k ; i++ ) {
if ( g[i]==1 ) {
for ( int j=0 ; j<3*k ; j++ ) {
if ( g[j]==2 ) {
sum1 = sum1 - d[i]+d[j];
sum2 = sum2 - d[j]+d[i];
g[i] = 2;
g[j] = 1;
i = 3*k;
break;
}
}
}
}
}
p1 = (double)sum1/(double)k; p2 = (double)sum2/(double)k;
}
}
// отпечатване на изхода
void writef() {
for ( int i=0 ; i<3*k ; i++ ) {
if ( g[i]==1 )
printf("%d\n",i+1);
}
for ( int i=0 ; i<3*k ; i++ ) {
if ( g[i]==2 )
printf("%d\n",i+1);
}
for ( int i=0 ; i<3*k ; i++ ) {
if ( g[i]==3 )
printf("%d\n",i+1);
}
}
int main() {
readf();
solve();
writef();
return 0;
}
Ето и динамичното решение:
/*
PROG: jpol
LANG: C++
Nikola Borisof
Динамичното решение
*/
# include <stdio.h>
# include <stdlib.h>
# define MAXK 64
int d[MAXK*3]; // входните данни
char opt[MAXK*1024][MAXK]; // масив на динамичното оптимиране
// opt[i][j] = 1 ако има сума i от j елемента коя
short m[MAXK*1024][MAXK];
int ind[MAXK*3]; // помощен масив за сортиране на
// входните данни така че да не ги разместваме
int g[MAXK*3]; // този масив оказва даден елемент
// в кое множество е 1,0 или 3
int k;
int cmp(const void *e1, const void *e2) {
return d[*(int *)e1]-d[*(int *)e2];
}
void readf() {
// четене на входа
freopen("jpol.in","r",stdin);
freopen("jpol.out","w",stdout);
scanf("%d",&k);
for ( int i=0 ; i<k*3 ; i++ ) {
scanf("%d",&d[i]);
ind[i] = i;
}
// сортираме масива d[] посредством масива
// ind[] който съдържа индекси
// примерно d[ind[0]] - е най-малкия елемент
// а d[ind[3*k-1]] - най-големия
qsort(ind,3*k,sizeof(int),cmp);
}
void writef(int a, int b) {
// отбелязваме кои елементи са в първото множество
// с 1 в масива g[]. Тези от вторито множество ще останат 0
while ( b ) {
g[m[a][b]] = 1;
a -= d[m[a][b]];
b--;
}
// извеждаме изхода
for ( int i=0 ; i<3*k ; i++ )
if ( g[i]==1 )
printf("%d\n",i+1);
for ( int i=0 ; i<3*k ; i++ )
if ( g[i]==0 )
printf("%d\n",i+1);
for ( int i=0 ; i<3*k ; i++ )
if ( g[i]==3 )
printf("%d\n",i+1);
}
void solve() {
// отбелязваме най-малките числа от множеството
// като част от другия регион за гласуване
// и ги изклучваме от търсенето на решение
for ( int i=0 ; i<k ; i++ ) {
g[ind[i]] = 3;
}
int sumata = 0;
for ( int i=3*k-1 ; i>=k ; i-- ) {
sumata += d[ind[i]];
}
// Внимание сложно динамично!!! Сложни са броячите на
// циклите поради оптимизациите. Пробвайте се да се досетите.
int sum = 0;
int k3 = 3*k, k500 = k*500;
register int i,j,l;
opt[0][0] = 1;
for ( i=k3-1 ; i>=k ; i-- ) {
for ( j=((sum>=MAXK*1024)? MAXK*1024-1:sum) ; j>=0 ; j-- ) {
for ( l=0 ; l<=k3-1-i ; l++ ) {
if ( opt[j][l] == 1 && !opt[j+d[ind[i]]][l+1] ) {
opt[j+d[ind[i]]][l+1] = 1;
m[j+d[ind[i]]][l+1] = ind[i];
if ( l+1 == k && j+d[ind[i]]>k500 &&
sumata-(j+d[ind[i]])>k500 ) {
// намерена е сума от k елемента
// която надвхарля 500*k и сумата
// на оставащите k елемента също
// надвхърля 500*к тоест това е решение.
// Отпечатваме го и прекратяваме програмата.
writef(j+d[ind[i]], l+1);
exit(0);
}
}
}
}
sum+=d[ind[i]];
}
}
int main() {
readf();
solve();
return 0;
}
Автор: Никола Борисов
обратно към брой 27
|