Flash Memory

Dana jest pamięć zawierająca $B$ bitów, w której chcemy zapisywać wartość $M$-bitowej zmiennej (w testach $B$ i $M$ są potęgami dwójki oraz $M$ jest dzielnikiem $B$). Na początku pamięć zawiera same bity 0, a podczas zapisu można jedynie zmieniać bity z 0 na 1.

Napisać program zapisujący nową wartość zmiennej oraz odczytujący zmienną. Wartość zmiennej do zapisu będzie losowana z rozkładem jednostajnym. Jest to zadanie optymalizacyjne. Wynik punktowy będzie uzależniony od średniej liczby zapisów, które będziemy w stanie wykonać.

Niezależne kodowania

Dzielimy pamięć na $B/M$ bloków i zapisujemy zmienną w pierwszym bloku, który zawiera same zera. Nie będziemy w stanie zapisać zmiennej równej 0, ale zdarzy się to z prawdopodobieństwem $\frac{1}{2^M}$. Odczytujemy wartość zmiennej z ostatniego niezerowego bloku.

Średnio zapiszemy nieco poniżej $B/M$ razy. Takie rozwiązanie dostaje około $30$ punktów:

const int N=520;
int t,B,M,c;
char b[N],m[N];

void write() {
  int zero=1;
  REP(j,M) if (m[j] == '1') zero=0;
  if (!zero) {
    REP(i,B/M) {
      int free=1;
      REP(j,M) if (b[i*M+j] == '1') free=0;
      if (free) {
        REP(j,M) b[i*M+j] = m[j];
        printf("1\n%s\n", b);
        fflush(stdout);
        return;
      }
    }
  }
  printf("0\n");
  fflush(stdout);
}

void read() {
  REP(i,B/M) {
    int free=1;
    REP(j,M) if (b[i*M+j] == '1') free=0;
    if (free) break;
    REP(j,M) m[j] = b[i*M+j];
  }
  printf("%s\n", m);
  fflush(stdout);
}

int main() {
  scanf("%d%d%d",&t,&B,&M);
  while (true) {
    int c; scanf("%d",&c);
    if (c == 0) break;

    if (t == 0) {
      scanf("%s%s",b,m);
      write();
    } else {
      scanf("%s",b);
      read();
    }
  }
}

Innym pomysłem może być niezależne kodowanie bitów. Dzielimy pamięć na $M$ bloków, każdy o długości $B/M$. W $i$-tym bloku będziemy zapisywać $i$-ty bit zmiennej jako xor z bitów w tym bloku.

Zatem przy zapisie zliczamy parzystość jedynek w bloku i, jeśli jest inna niż bit zmiennej, to dopisujemy kolejną jedynkę w bloku. Ponieważ zdarzy się to z prawdopodobieństwem $\frac12$, więc średnio powinniśmy zapisać $2B/M$ razy (niestety będzie mniej z powodu tego, że pojedynczy blok może się nam zapełnić szybciej).

Takie rozwiązanie dostaje około $35$ punktów:

void write() {
  REP(i,M) {
    int v=0;
    REP(j,B/M) if (b[i*B/M + j] == '1') v++;
    if (m[i]-'0' != (v & 1)) {
      if (v != B/M) {
        b[i*B/M + v] = '1';
      } else {
        printf("0\n");
        fflush(stdout);
        return;
      }
    }
  }
  printf("1\n%s\n", b);
  fflush(stdout);
}

void read() {
  REP(i,M) {
    int v=0;
    REP(j,B/M) if (b[i*B/M + j] == '1') v++;
    m[i] = '0' + (v & 1);
  }
  printf("%s\n", m);
  fflush(stdout);
}

Programowanie dynamiczne

Idea będzie taka, żeby każdemu z $B$ bitów pamięci przypisać losowy wektor $M$-bitowy. W każdym momencie wartością zmiennej będzie xor z tych wektorów, których bity są ustawione na 1.

Oznaczmy przez $v_i$ wektor dla $i$-tego bitu ($0 \leq v_i < 2^M$). Należy pamiętać, żeby losowanie przebiegało deterministycznie, tzn. aby program zapisujący i odczytujący wylosowały takie same wektory. Można tego dokonać, ustawiając początkowe ziarno generatora losowego funkcją srand().

W celu zapisania nowej wartości, będziemy chcieli poszukać minimalnej liczby bitów, które musimy zmienić na 1. Wykorzystamy do tego programowanie dynamiczne. Niech $dp[i][m]$ będzie minimalną liczbą zmian, które musimy zrobić, żeby bity z pozycji od 1 do $i$ dały w sumie wartość $m$ (gdzie $0 \leq i \leq B$ oraz $0 \leq m < 2^M$).

Rekurencja jest prosta: jeśli $i$-ty bit jest już ustawiony na 1, to mamy $dp[i][m] = dp[i-1][m \ \mathrm{xor}\ v_i]$. W przeciwnym wypadku mamy $dp[i][m] = \min(dp[i-1][m], 1 + dp[i-1][m \ \mathrm{xor}\ v_i])$.

Czas działania programowania dynamicznego wynosi $O(B 2^M)$, czyli będzie sensowny jedynie dla małych wartości $M$. W przypadku dużych $M$ możemy podzielić zmienną na $M/k$ bloków długości $k=8$ oraz pamięć na $B/(M/k)$ bloków i uruchamiać algorytm niezależnie dla bloków. Da to złożoność czasową $O(B 2^k)$.

Takie rozwiązanie dostaje około $70$ punktów, co jest przyzwoitym wynikiem, gdyż nawet jurorzy nie mieli rozwiązania dostającego więcej niż $80$ punktów:

int v[N];
pair<int,int> dp[N][1<<K];

void write() {
  const int LEN = B/(M/K);
  REP(i,M/K) {
    int val = 0;
    REP(j,K) if (m[i*K + j] == '1') val |= 1<<j;

    REP(mask,1<<K) dp[0][mask] = make_pair(infty, -1);
    dp[0][0] = make_pair(0, -1);
    REP(j,LEN) REP(mask,1<<K) {
      if (b[i*LEN + j] == '1') {
        dp[j+1][mask] = make_pair(dp[j][mask ^ v[i*LEN + j]].first, 1);
      } else {
        dp[j+1][mask] = min(
            make_pair(dp[j][mask].first, 0),
            make_pair(1 + dp[j][mask ^ v[i*LEN + j]].first, 1));
      }
    }

    int ans = dp[LEN][val].first;
    if (ans == infty) {
      printf("0\n");
      fflush(stdout);
      return;
    }

    int j=LEN, mask=val;
    while (j) {
      if (dp[j][mask].second) {
        b[i*LEN + j-1] = '1';
        mask ^= v[i*LEN + j-1];
      }
      j--;
    }
  }
  printf("1\n%s\n", b);
  fflush(stdout);
}

void read() {
  const int LEN = B/(M/K);
  REP(i,M/K) {
    int val = 0;
    REP(j,LEN) if (b[i*LEN+j] == '1') {
      val ^= v[i*LEN+j];
    }
    REP(j,K) m[i*K + j] = '0' + !!(val & (1<<j));
  }
  printf("%s\n", m);
  fflush(stdout);
}

void init() {
  srand(0);
  REP(i,B) v[i] = rand() % (1<<K);
}