Problem G
Kärleksbrev

Mio och Sara kommer från två väldigt olika familjer. I Mios familj har alla på sig hattar som är formade som rektanglar, medan i Saras familj har alla på sig triangelformade hattar. Denna smakskillnad har lett till bråk som varat flera generationer. Trots detta råkade Mio och Sara träffas en dag och blev förälskade vid första ögonkast.

Eftersom det är svårt för dem att träffas, så brukar de istället skicka meddelanden sinsemellan för att kommunicera. Eftersom de är väldigt hemliga så vet vi inte exakt hur apparatererna de använder för att kommunicera fungerar. Vi vet dock lite: om Sara vill skicka ett meddelande skriver hon in det som en sekvens av ettor och nollor i apparaten, och den skickar sedan iväg meddelandet. Tyvärr kan oväder sätta käppar i hjulet (metaforiskt sett). När maskinen skickar iväg ettor och nollor under oväder, så skickas exakta motsatsen. Exempelvis, om det är oväder och maskinen försöker skicka 0, så skickar den istället iväg 1.

Sara har observerat att varje gång hon skickar ett meddelande, så är det oväder exakt en gång under en sammanhängande period. Detta innebär att om hon försöker skicka iväg ett särskilt meddelande, kommer meddelandet som mottagaren tar emot vara fel på så sätt att i ett intervall (som kan vara av storlek 1 eller mer, men inte noll), så har alla nollor blivit till ettor och alla ettor blivit nollor. Vi benämner detta med att intervallet har fördärvats.

Till exempel: om Sara skickar iväg 11101001, så är det möjligt att vädret leder till följande fördärvning: 11101001 $\Rightarrow $ 11010111.

Beteckna meddelandet som Sara vill skicka som $S$ och meddelandet som Mio mottar som $M$. $S$ är alltså aldrig lika med $M$ på grund av oväder. Sara och Mio vill nu utveckla ett system för att kunna kommunicera med varandra trots oväder. Det går att visa att om Sara skickar exakt $S$, så är det omöjligt för Mio att använda $M$ för att hitta $S$. Men det kanske går om Sara skickar ett meddelande som är lite längre än $S$?

Ditt jobb är att utveckla systemet åt Sara och Mio, så att de kan kommunicera felfritt. Detta gör du genom att implementera två funktioner, encode och decode. Funktionen encode kommer att anropas med $S$, och ska sedan returnerna $E$. Sara kommer sedan att skicka iväg $E$ med sin maskin. Därefter mottar Mio strängen $M$ och anropar funktionen decode med $M$, och dess jobb är att använda $M$ för att hitta $S$.

För att få poäng på uppgiften måste systemet funka. Därmed ska decode alltid kunna hitta $S$, oavsett hur oväder fördärvar $E$. Du får mer poäng om $E$ är kort.

Implementation

Din lösning till problemet måste vara skriven i ett av följande språk: C++, Java, Python eller Rust. Nedan finns en beskrivning av hur implementationen ser ut i C++. I de flesta andra språken fungerar det på ett liknande sätt. Du kan ladda ner en referensimplementation för ditt språk vid attachments längst nere på sidan.

Du ska inte skapa en main-funktion. Istället ska du implementera följande funktioner:

• string encode(string S)
  

  • Parametern $S$ är meddelandet som Sara vill skicka till Mio. $S$ består endast av karaktärerna 0 och 1. I alla testfall håller det att $S$ består av exakt 100 karaktärer.

  • Returvärdet ska vara $E$, meddelandet som Sara ska skicka igenom maskinen. $E$ måste innehålla minst en karaktärerna, och får endast bestå av karaktärerna 0 och 1.

• Sedan skickas $E$. Medan den skickas kommer ett intervall att fördärvas.

• string decode(string M)
  

  • Parametern $M$ är meddelandet som Mio mottar. Detta kommer vara $E$ efter att ett intervall har fördärvats. Alltså består $M$ endast av karaktärerna 0 och 1.

  • Returvärdet ska vara $S$, meddelandet som encode ursprungligen anropades med. Om returvärdet är samma som $S$ får du rätt svar på testfallet.

encode och decode får endast kommunicera genom parametrarna de anropas med, $S$ och $M$. Därför kommer ditt program att startas om mellan anropat av vardera funktion. encode och decode måste vara snabba nog för att kunna anropas 50 gånger vardera inom tidsgränsen. Dessutom är domaren inte adaptiv. Detta innebär att hur den väljer $S$ inte beror på vad du väljer att skicka som $E$. När den ska välja vilket intervall att fördärva kollar den bara på antalet tecken i $E$, inte innehållet av $E$.

Referensimplementationer

Alla referensimplementationer i attachments implementerar följande protokoll: encode skickar varje bokstav i $S$ 5 gånger på raken. decode tar sedan varje grupp av 5 karaktärer, och säger att värdet av bokstaven i $S$ är den i mitten av gruppen. Detta protokollet funkar inte, men visar hur implementationen av ett protokoll kan se ut.

Det är viktigt att din lösning inte läser eller skriver från standard input/output. Om din lösning gör det kommer du troligtvis att få ett konstigt felmeddelande. För vissa språk är filnamnet viktigt, så ändra inte det. Ändra heller inte namnet på funktioner och klasser osv. om dessa finns. Rust kräver extra steg för att funka, vilket du kan om läsa i filen rust/readme.txt i karleksbrev.zip.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Beteckna $E_{max}$ som längden på det $E$ med flest karaktärer som encode producerar i en viss testfallsgrupp. För att få poäng för ett testfall måste $E_{max}$ vara tillräckligt litet.

Låt också $l$ och $r$ beteckna ändpunkterna för intervallet som fördärvas. Om $E$ är noll-indexerad kommer $E[l],E[l+1],\dots ,E[r]$ att fördärvas.

Det är även givet att $S$ alltid består av exakt 100 bokstäver.

Indataformat för exempeldomaren

Exempeldomaren läser indata på följande format:

• En rad med heltalen $N$ och $K$.

• En rad med bitsträngen $S$.

• En rad med heltalen $l$ och $r$. Detta är intervallet i $E$ som domaren kommer att fördärva.

Exempel-interaktion

Betrakta följande indata till domaren:

5 25
01011
1 3

Om man kör exempelprogrammet som tillhandahålls sker följande. Notera att exempelprogrammet inte löser problemet i detta fallet.