Текущ брой на Списание ИнфоМан
 


Февруарско състезание на 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