Tävlingsprogrammering/Uppgifter/Troféhyllan
Troféhyllan
FIGUR 2. Troféhyllan i exemplet. Pilen visar från vilket håll hyllan betraktas. De streckade troféerna är de två som ska tas bort för att öka antalet synliga troféer från två till tre.
Oskar har N troféer stående på en perfekt rad på sin hylla. Han bekymrar sig dock över att man inte kan se allihop när man tittar längs raden, eftersom en trofé med höjden H skymmer alla bakomvarande troféer med en höjd som är mindre eller lika med H. Oskar undrar därför om han, genom att plocka bort några troféer (men inte flytta om dem) kan göra så att fler blir synliga. Skriv ett program som, givet höjden för varje trofé i raden, beräknar hur många troféer som maximalt kan bli synliga om han plockar bort valfritt antal troféer. Programmet ska också ange vilka troféer han ska ta bort. Om det finns flera sätt att få det maximala antalet synliga troféer, ska antalet borttagna troféer vara så litet som möjligt.
På första raden i filen trofe.dat står ett heltal N , antalet troféer (2 ≤ N ≤ 100). Sedan följer en rad med N heltal, höjden för varje trofé (1 ≤ H ≤ 100), i den ordning de står på hyllan (den närmaste först).
Programmet ska skriva ut det maximala antalet troféer som kan synas om man får plocka bort valfritt antal. Dessutom ska programmet skriva ut en minimal uppsättning troféer som ska plockas bort för att uppnå detta. Troféerna är numrerade från 1 till N i den ordning de står på hyllan. Om det finns flera olika lösningar med minimalt antal troféer bortplockade ska programmet ange vilken som helst av dem.
Körningsexempel: Filen trofe.dat med innehållet
6 5 3 3 7 4 6
ska ge svaret
Max synliga: 3 Ta bort: 1 4
Lösning
[redigera]Den här uppgiften är en typisk dynamisk programmeringsuppgift, nämligen longest increasing subsequence.
Läs mer här: http://www.csc.kth.se/contest/ioi/ioitraning/lis.htm
Det handlar kort om att spara de bästa subsekvenserna av alla längder fram till längden, m, där m är den längsta ökande subsekvsen. Med bästa subsekvens menar vi den subsekvens som slutar på ett så lågt tal som möjligt, vilket ger oss bästa förutsättningar för att lägga till fler tal till sekvensen.
Men det räcker inte att bara använda ovanstående algoritm för att hitta den längsta möjliga ökande subsekvensen.
Betrakta denna hylla:
1 7 10 5 6 11
Vi har två möjliga subsekvenser som är av maximal längd:
1 7 10 11
1 5 6 11
I ena fallet behöver vi inte ta bort några troféer, men i andra fallet behöver vi ta bort två. Så för att minimera antalet troféer som behöver tas bort behöver vi den längsta ökande subsekvens med så höga troféer som möjligt. Detta kan vi få genom att använda samma algoritm, beskriven ovan, men med ett annat villkor.
Om vi använder samma algoritm, men ändrad för att istället hitta den längsta minskade subsekvensen kommer vi alltid få de högsta värdena i subsekvensen. Detta faktum kan vi utnyttja genom att söka den längsta minskade subsekvensen av vår bakåtvända vektor.
Alltså kommer denna implementation av längsta möjliga subsekvens ge oss de maximala höjderna för troféerna i denna sekvens.
När man har denna subsekvens handlar det bara om att iterera igenom hyllan för att se om en trofée kommer skymma den kommande troféen som finns i den längsta subsekvensen.
#include <iostream>
#include <fstream>
using namespace std;
int main() {
fstream fin("trofe.dat");
int num_trophies;
fin >> num_trophies;
int rack[num_trophies];
for (int i = 0; i < num_trophies; ++i) {
fin >> rack[i];
}
int q[num_trophies], p[num_trophies], len_longest = 1;
q[0] = num_trophies-1;
p[num_trophies-1] = -1;
for (int i = num_trophies-2; i >= 0; --i) {
if (rack[q[len_longest-1]] > rack[i]) {
p[i] = q[len_longest-1];
q[len_longest] = i;
++len_longest;
continue;
}
bool flag = true;
for (int j = len_longest-2; j >= 0; --j) {
if (rack[q[j]] > rack[i]) {
if (rack[q[j+1]] < rack[i]) {
p[i] = q[j];
q[j+1] = i;
flag = false;
}
break;
}
}
if (flag) {
q[0] = i;
}
}
int lis[len_longest];
int pos_temp = q[len_longest-1];
for (int i = 0; i < len_longest; ++i) {
lis[i] = rack[pos_temp];
pos_temp = p[pos_temp];
}
cout << "Max synliga: " << len_longest << "\nTa bort: ";
pos_temp = 0;
for (int i = 0; i < num_trophies && pos_temp < len_longest; ++i) {
if (rack[i] == lis[pos_temp]) {
++pos_temp;
} else if (rack[i] > lis[pos_temp]) {
cout << i+1 << ' ';
}
}
cout << '\n';
return 0;
}
Här nedan följer ett lösningsexempel i Java. Vi går igenom hyllan från vänster till höger. För varje trofé kan vi göra ett val, vi kan välja att ta bort den och vi kan välja att låta den stå kvar. Men om vi helt naivt bara gjorde så, så skulle vi få 2^100 olika kombinationer att testa och det vill vi inte. Dock minskar kombinationerna drastiskt av det faktum att vi inte ens behöver bemöda oss med att testa ta bort en trofé om det finns en lika hög eller högre trofé till vänster om den, då kan vi låta den stå kvar.
Dock blir det fortfarande för många kombinationer att testa. Vad gör man då? Ja då tar man till lite dynamisk programmering. Vi sparar helt enkelt vilken den högsta trofén till vänster om en trofé var, för det antalet troféer man kunde se just då. Om det visar sig att vår högsta trofé till vänster är högre än den sparade (om det finns någon sparad) för det antal troféer vi kan se för tillfället, ja då behöver vi inte fortsätta. Någon kan kanske nu ha någon invändning mot att vi riskerar att döda eventuella "bästa kombinationer" med färre borttagna troféer, men eftersom vi testar att låta trofén stå kvar före vi testar att ta bort den, så kommer en eventuellt lika bra kombination med färre borttagna troféer redan att ha sparats som bäst.
import java.util.*;
import java.io.*;
public class Trofehyllan
{
//Hur många troféer vi tagit bort i den bästa serien.
static int moves = 0;
//Mesta antalet troféer vi kan se.
static int max = 0;
//Vilka vi tog bort för att nå dit.
static String sequence = "";
//Antalet troféer.
static int N;
//"Karta" för dynamisk programmering.
static int [][] chart;
//Våra troféer.
static int [] trophies;
//Vilka vi plockat bort.
static boolean [] removed;
//Rekursiv metod för att lösa uppgiften.
//top: Högsta trofén i serien fram till i.
//removals: Hur många vi plockat bort.
//i: Index för den den trofé vi ska behandla.
public static void rek(int top, int removals, int i)
{
//Hur många vi kan se.
int visible = count();
//Om vi behandlat alla troféer.
if(i==N)
{
//Om vi är bättre än tidigare bästa, så ska vi såklart spara resultate.
if(visible>max)
{
max = visible;
moves = removals;
saveMoves();
}
else if(visible==max && removals<moves)
{ //Om vi är lika bra, så är det minsta antalet bortplockningar som avgör.
moves = removals;
saveMoves();
}
return;
}
//Om vi vid denna troféposition i behandlandet tidigare har sett samma antal troféer,
// fast vi då hade en lägre högsta trofé, då är det onödigt att fortsätta.
if(chart[i][visible]!=0 && chart[i][visible]<top) return;
else
{
//Annars sparar vi vår topp på positionen.
chart[i][visible] = top;
}
//Om trofén på platsen är högre än vår tidigare högsta.
if(trophies[i]>top)
{
//Då kan vi välja att inte ta bort den.
rek(trophies[i], removals, i+1);
//Eller så kan vi välja att ta bort den.
removed[i] = true;
rek(top, removals+1, i+1);
removed[i] = false;
}
else
{
//Om trofén är lägre eller lika hög som den tidigare högtsa,
// då behöver vi inte ens bry oss om att behandla den, utan går bara vidare till nästa.
rek(top, removals, i+1);
}
}
//Metod som sparar vilka troféer det var vi tog bort i den vinnande serien.
public static void saveMoves()
{
sequence = "";
for(int i = 0; i<N; i++)
{
if(removed[i]) sequence += (i+1) + " ";
}
}
//Räknar antalet troféer man kan se.
public static int count()
{
int nr = 0;
int top = 0;
for(int i = 0; i<N; i++)
{
//Vi ser en trofé om den inte är bortplockad och
// högre än alla till vänster om sig.
if(trophies[i]>top && !removed[i])
{
nr++;
top = trophies[i];
}
}
return nr;
}
//Orka fånga exceptions. Vi är lata och säkra på vår sak.
public static void main(String [] klein) throws FileNotFoundException
{
//Vi ska läsa av filen trofe.dat i mappen/katalogen data.
Scanner scan = new Scanner(new File("data\\trofe.dat"));
//Antalet troféer.
N = scan.nextInt();
//Skapar troféhyllan.
trophies = new int [N];
//Skapar arrayen för var vi noterar vilka vi plockat bort.
removed = new boolean [N];
//Skapar karta för dynamisk programmering.
chart = new int [N][N+1];
//Läser in troféer.
for(int i = 0; i<N; i++)
{
trophies[i] = scan.nextInt();
}
//Räknar antalet troféer vi kan se i dagsläget.
max = count();
//Tar reda på svaret.
//Vår högsta trofé är 0, vi har tagit bort 0, och vi ska börja på trofén med index 0.
rek(0, 0, 0);
//Skriver ut svaret.
System.out.println("Max synliga: " + max);
System.out.println("Ta bort: " + sequence);
}
}
Lösning i Haskell där vi konsekvent väljer att bara förlänga den för närvarande längsta sekvensen med den högsta trofén. Så om vi har sekvenserna [1,3,4] och [1,3,5] och ska förlänga någon av dem med siffran 6, så är det den senare som kommer att förlängas. På så sätt hittar vi den längsta sekvensen där vi behöver ta bort så få troféer som möjligt. (Sedan kan det dock vara lite bökigt att ta reda på vilka troféer som ska tas bort, men ingenting är omöjligt.)
-- Troféhyllan
module Main where
import IO
import Data.List
main = do {
ih <- openFile "trofe.dat" ReadMode;
content <- hGetContents ih;
hyllan <- return $ ((map read).tail.words) content;
lngincsub <- return $ lis hyllan [];
putStrLn $ "Max synliga: " ++ (show $ length lngincsub);
putStrLn $ "Ta bort:" ++ (which (index hyllan) lngincsub []);
hClose(ih)
}
index = zipWith (\x y -> (y,x)) [1..]
myComp x y | (length x) > (length y) = LT
| (length x) < (length y) = GT
| null x = GT
| null y = LT
| (head x) > (head y) = LT
| (head x) < (head y) = GT
| otherwise = EQ
lis :: [Int] -> [[Int]] -> [Int]
lis [] acc = reverse $ head acc
lis (h:t) acc = lis t (insertBy myComp new acc)
where
new = let p = (dropWhile (\x -> (head x) >= h) acc) in if (null p) then [h] else h:(head p)
which :: [(Int,Int)] -> [Int] -> [Int] -> String
which _ [] acc = concat $ map ((\x -> ' ':x).show) acc
which hylla (h:t) acc = which (tail (dropWhile (\x -> (fst x) /= h) hylla)) t (acc ++ [snd x | x <- (takeWhile (\y -> (fst y) /= h) hylla), (fst x)>h])