Tävlingsprogrammering/Uppgifter/Udda mullvadar

Uppgift

https://po.scrool.se/problems/mullvadar

Lösning

Talet t kunde i det här problemet vara väldigt stort, upp emot 10¹⁸. Detta brukar signalera att det söks en algoritm som antingen går i konstant tid eller är logaritmisk i t.

Delpoäng

Det finns flera sätt att lösa delpoängsproblemet. En bra resurs att känna till är http://oeis.org/, The Online Encyclopedia of Integer Sequences. Genom att räkna ut svaren för de första värdena på t (antingen för hand eller med en enkel brute force) så kan man hitta följande sekvens: http://oeis.org/A071053. Därifrån kan man leta sig vidare till hjälpfulla länkar som beskriver hur en rekursion kan tas fram.

Full poäng

På grund av all komplicerad interferens som uppstår när man har flera mullvadar så känns det inte så troligt att man kan lösa problemet på konstant tid. En logaritmisk lösning brukar dock vara ungefär lika bra så det är vad vi kommer sikta på.

Något man ofta vill eftersträva när man söker efter en sådan algoritm är förmågan att kunna halvera problemstorleken. Detta skulle kunna uppnås om vi hittade ett sätt att simulera två tidssteg i taget (och sedan fyra tidssteg i taget osv.). Vi börjar med att se hur man kan simulera ett tidssteg.

För att underlätta så kan vi representera mullvadar som ettor och nollor, där en etta innebär en aktiv mullvad och en nolla en inaktiv. Om vi då vill ta oss från tillstånd $x$ till tillstånd $y$, ett tidssteg fram, så kan vi definiera $y_{i}=x_{i-1}\oplus x_{i}\oplus x_{i+1}$, där $\oplus$ står för xor-operationen. Detta fungerar eftersom vi endast är intresserade av pariteten för varje mullvad (jämnt eller udda) och xor kan ses som addition modulo 2. Om vi istället vill ta oss till tillstånd $z$, två tidssteg fram, så får vi följande formel:

${\begin{matrix}z_{i}&=&y_{i-1}\oplus y_{i}\oplus y_{i+1}\\&=&x_{i-2}\oplus x_{i-1}\oplus x_{i}\oplus x_{i-1}\oplus x_{i}\oplus x_{i+1}\oplus x_{i}\oplus x_{i+1}\oplus x_{i+2}\\&=&x_{i-2}\oplus x_{i}\oplus x_{i+2}\\\end{matrix}}$

, eftersom $x\oplus x=0$ och $x\oplus 0=x$

Mullvad $z_{i}$ påverkas alltså inte av $x_{i-1}$ och $x_{i+1}$ utan endast av mullvadarna på avstånd 0 eller 2, och beror på dessa på samma sätt som $y_{i}$ beror på $x_{i-1}$, $x_{i}$ och $x_{i+1}$. Detta säger oss att om vi går 2 tidssteg fram i taget så är mullvadar på positioner av olika paritet oberoende och vi kan behandla dessa var för sig. Detta gör att vi nu är redo att skriva vår rekursion, som tar en konfiguration av mullvadar $x$ samt en tid t och returnerar antalet aktiva mullvadar efter t tidssteg, definierat som följer:

$rec(x,t)=\left\{{\begin{matrix}\sum _{k\in x}k,&{\mbox{om }}t{\mbox{ = 0}}\\rec(y,t-1),&{\mbox{om }}t\equiv {\mbox{1 mod 2}}\\rec(x_{even},t/2)+rec(x_{odd},t/2),&{\mbox{annars}}\\\end{matrix}}\right\}$

, där $y$ som förut är $x$ simulerat ett tidssteg fram, och $x_{even}$ och $x_{odd}$ är en uppdelning av $x$ i två nya konfigurationer med mullvadar på endast jämna respektive udda positioner i $x$.

Det enda som behövs nu är att snabba upp uträkningarna med lite memoization. Ett sätt att göra detta på är att spara resultatet för varje tid t då $x$ endast innehåller en enda etta, samt att i varje rekursivt anrop plocka bort alla nollor i utkanterna av $x$ (som ändå inte kan påverka resultatet).

Lösning för delpoäng i Java:

import java.io.*;

public class MullvadarPartial {
        
        public static void main(String[] args) throws IOException {
                BufferedReader in = new BufferedReader(new InputStreamReader(System.in));   
                in.readLine();
                System.out.println(solve(Long.parseLong(in.readLine())));
                in.close();
        }
        
        static long solve(long t) {
                if (t == 0) return 1;
                else if (t % 2 == 0) return solve(t/2);
                else if (t % 4 == 1) return 3*solve(t/4);
                return solve(t/2) + 2*solve(t/4);
        }
}

Elegant lösning för delpoäng i C (av Anton Fors Hurdén):

#include <stdio.h>
#include <stdint.h>

int main() {
	uint64_t t, i, n = 1;

	scanf("%*s %llu", &t);

        while (t) {
		t /= t & (~t + 1);
		t /= (i = ~t & (t + 1));
		n *= ((i << 2) + 1) / 3;
	}

	printf("%llu\n", n);
}

Lösning för full poäng i Java:

import java.util.*;
import java.io.*;

public class Mullvad {
	
	static HashMap<Long, Long> mem;
	
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

		String s = in.readLine();
		long t = Long.parseLong(in.readLine());
		
		mem = new HashMap<Long, Long>();
		int[] x = new int[s.length()];
		for (int i = 0; i < s.length(); i++) {
			if (s.charAt(i) != '.') x[i] = 1;
		}
		out.println(solve(x, t));
		
		in.close();
		out.close();
	}
	
	static long solve(int[] x, long t) {
		if (t == 0) return getCount(x);
		x = reduce(x);
		if (x.length == 0) return 0;
		if (x.length == 1) {
			Long memorized = mem.get(t);
			if (memorized != null) return memorized;
		}
		long res = 0;
		if (t % 2 == 1) {
			res = solve(expand(x), t - 1);
		} else {
			int[] x1 = new int[(x.length + 1)/2];
			int[] x2 = new int[x.length / 2];
			for (int i = 0; i < x1.length; i++) x1[i] = x[i*2];
			for (int i = 0; i < x2.length; i++) x2[i] = x[1 + i*2];
			res = solve(x1, t/2) + solve(x2, t/2);
		}
		if (x.length == 1) {
			mem.put(t, res);
		}
		return res;
	}
	
        // Return the number of ones in the array x.
	static int getCount(int[] x) {
		int res = 0;
		for (int i = 0; i < x.length; i++) res += x[i];
		return res;
	}
	
        // Simulate one time step.
	static int[] expand(int[] x) {
		int[] res = new int[x.length + 2];
		for (int i = 0; i < x.length; i++) {
			for (int j = i; j < i + 3; j++) {
				res[j] ^= x[i];
			}
		}
		return res;
	}
	
        // Remove all zeroes on the left or right end of the array x.
	static int[] reduce(int[] x) {
		int l = x.length;
		int r = -1;
		for (int i = 0; i < x.length; i++) {
			if (x[i] == 1) {
				r = i;
				l = Math.min(l, i);
			}
		}
		if (l > r) return new int[0];
		int[] res = new int[r - l + 1];
		for (int i = 0; i < res.length; i++) {
			res[i] = x[i + l];
		}
		return res;
	}
}