Tävlingsprogrammering/Uppgifter/EEPROM
EEPROM
Du har tillgång till en rektangulär EEPROM minnesmodul som rymmer R x 16 bitar. En skrivoperation ändrar tillståndet på en sammanhängande sekvens av bitar i en rad eller en kolumn.
Du vill nu att minnesmodulen ska innehålla ett visst bitmönster. Bestäm det minsta antalet skrivoperationer som är nödvändigt för att kunna skapa det bitmönstret. Från början är minnesmodulen tom, dvs den består av enbart nollor.
Indata
Den första raden innehåller heltalet R (1 ≤ R ≤ 50), antalet rader i modulen.
De följande R raderna innehåller en sträng med 16 binära siffror, '0' eller '1', som anger hur motsvarande rad ska se ut när alla operationer har genomförts.
Utdata
Ett heltal som anger det minsta antalet skrivoperationer som måste utföras.
Bedömning
I 20% av testfallen är R ≤ 5.
Exempel 1: Indata
5 0000011111111100 0001000000000000 1110111111111111 0001000000000000 0000000000000000
Exempel 1: Utdata
3
Exempel 2: Indata
4 0000010000000010 0001101110000011 1110010000001111 0000010000000011
Exempel 2: Utdata
6
Lösning
[redigera]Först måste man inse att det inte finns någon poäng med två överlappande horisontella (eller vertikala) skrivoperationer. Man kan alltid göra om en sådan lösning till en annan som inte överlappar och som inte kräver fler skrivoperationer. Däremot kan det förstås vara nödvändigt med en horisontell skrivoperation som korsar en vertikal skrivoperation (vilket framgick av det första exemplet). Varje ruta kan därför antingen vara "utsatt" för ingen skrivoperation alls, exakt en skrivoperation (antingen en horisontell eller en vertikal), eller för två skrivoperationer. Resultatet av 0 eller 2 skrivoperationer blir förstås att rutan kommer innehåller en '0':a, och i de andra fallen så kommer den innehålla en '1':a.
Betrakta nu följande rekursiva lösning. Vi går igenom rutorna en och en i row-major order (första hela rad 1, sedan rad 2 osv). Vid varje ruta x,y bestämmer vi om en horisontell och/eller vertikal skrivoperation ska gå igenom rutan. Beroende på om målvärdet i rutan är 0 eller 1 så finns det bara två alternativ att välja på, och vi måste testa båda. Om vi t ex testar att en horisontell operation ska gå igenom rutan, måste vi också veta om rutan till vänster om den nuvarande (dvs x-1,y) också hade en horisontell operation. Om den har det så kan vi bara förlänga den horisontella linjen ett steg (kostnad 0). I annat fall måste vi påbörja en ny horisontell linje (kostnad 1). Samma sak gäller om vi bestämmer oss för en vertikal operation genom rutan. Vi behöver då kolla om rutan ovanför (dvs x,y-1) hade en vertikal operation osv.
Man kan alltså tänka sig följande rekursiva funktion: (i pseudo-kod)
// Returnerar det minsta antalet skrivoperationer som behöver utföras
int solve(int x, int y, bool[,] hasVertOp, bool[,] hasHorzOp)
{
if x==16 return solve(0, y+1, hasVertOp, hasHorzOp);
if y==N return 0
int best = INF
foreach useHorz in (false, true)
foreach useVert in (false, true)
if useHorz ^ useVert == targetSquare[y,x]
best = min(best, solve(x+1, y, hasVertOp.set(x,y,useVert), hasHorzOp.set(x,y,useHorz))
return best
}
Detta är förstås hopplöst långsamt. En första, och viktig, förbättring är att inse att vi inte behöver hela hasvertOp och hasHorzOp arrayerna. Vi är bara intresserad av föregående ruta (hasHorzOp) eller föregående rad (hasVertOp). Längre tillbaka i "beslutshistoriken" behöver vi aldrig sträcka oss. Däremot behöver vi komma ihåg hasVertOp för samtliga kolumner. Vi kan förändra koden ovan till följande:
int solve(int x, int y, bool[] hasVertOp, bool lastWasHorz)
{
if x==16 return solve(0, y+1, hasVertOp, false);
if y==N return 0
int best = INF
forEach useHorz in (false, true)
forEach useVert in (false, true)
if useHorz ^ useVert == targetSquare[y,x]
best = min(best, solve(x+1, y, hasVertOp.set(x,useVert), useHorz)
return best
}
Programmet är fortfarande lika långsamt, sett till antalet rekursiva anrop som kommer att göras. Men nu har vi fått ner "domänen" på funktionen, dvs antalet möjliga kombinationer av indatat, så att det nästan går att cacha resultatet: x kan vara mellan 0 och 15, y mellan 0 och N-1, hasVertOp kan ha 216 olika värden och lastWasHorz 2 värden. Detta blir total 16*N*65536*2 = (om N är 50) = 16*50*65536*2 = ca 100 miljoner. Detta är för mycket för att det ska rymmas i minnet på en gång (men inte med så mycket), men tillräckligt snabb för att hinna behandlas tidsmässigt.
För att få cachningen att rymmas i minnet måste funktionen skrivas om från rekursiv till iterativ, dvs vi gör om lösning från "memoization" (vilket det kallas när man cachar upp resultaten i en rekursiv funktion) till dynamisk programmering, där man istället beräknar funktioner "bakifrån". Poängen med det är att vi kan återanvända delar av cachen, vilket sparar minne. Slutresultatet kan bli något så här elegant: (början och slutet utelämnade)
for (int r = 0; r < n; r++) {
String buff = io.getWord();
for (int c = 0; c < 16; ++c) {
int val = buff.charAt(c)-'0';
for (int i=0;i<0x10000;i++)
dp[next][i][0] = dp[next][i][1] = INF;
for (int hor = 0; hor < 2; ++hor ) {
for (int mask = 0; mask < 0x10000; mask++ ) {
for (int h = 0; h < 2; ++h ) {
int v = h^val;
int cost = dp[curr][mask][hor];
if (h > 0 && (c == 0 || hor == 0)) ++cost;
if (v > 0 && (mask>>c&1) == 0) ++cost;
int newMask = mask & ~(1<<c) | (v<<c);
dp[next][newMask][h] = Math.min(dp[next][newMask][h], cost);
}
}
}
curr ^= 1;
next ^= 1;
}
}
En sak vi kan lägga märke till är att det faktiskt går att få ut från hasVertOp och aktuell rut-indata vilket värde vi måste ha på lastWasHorz. På det sättet får vi enbart 16*50*65536 = ca 50 miljoner olika möjligheter, som faktiskt får plats att spara i en memoization-tabell, om vi använder unsigned char. Hur som helst, här är en fullständig lösning:
#include <cstdio>
#include <cstdlib>
#define INF 1000000
int R;
unsigned char dp[2][65536];
int indata[50][16];
int main(){
scanf("%d", &R);
for(int i=0; i<R; i++){
char buffer[17];
scanf("%s", buffer);
for(int j=0; j<16; j++)
indata[i][j] = buffer[j]-'0';
}
for(int y=R; y-->0;){
for(int x=16; x-->0;){
for(int hasVertOp=0; hasVertOp<65536; hasVertOp++){
bool lastWasHorz;
if (x != 0)
lastWasHorz = (!!(hasVertOp & (1<<(x-1)))) ^ indata[y][x-1];
else
lastWasHorz = false;
int best = INF;
for(int useVert = 0; useVert < 2; useVert++){
int useHorz = useVert ^ indata[y][x];
int res = dp[x%2][(hasVertOp & ~(1<<x)) | (useVert<<x)] + (useVert && !(hasVertOp & (1<<x))) + (useHorz && !lastWasHorz);
if (best > res)
best = res;
}
dp[(x%2) == 0][hasVertOp] = best;
}
}
}
printf("%d\n", dp[1][0]);
}