Labb 4

NP-fullständighetsreduktioner - Rollbesättning

Om du redovisar labben senast den 22 november får du en bonuspoäng på tentan. På övningen den 13 november har du dessutom möjlighet att redogöra för lösningen på teoriuppgifterna nedan. Korrekt lösning av dessa ger en bonuspoäng på tentan. Sen redovisning ger ingen bonus. 
Det är frivilligt att redovisa teoriuppgifterna, men för att klara av att göra labben bör du ha gjort dom.

Ansvarig för castingen på ett filmbolag behöver koppla ihop rätt skådespelare med rätt roller. Samma person kan spela flera roller, men samma roll kan endast innehas av en person. Manus anger vilka roller som är med i samma scener. Inga monologer får förekomma. Varje skådespelare får bara ha en roll i varje scen.

Dessutom är divorna p1 och p2 garanterade vid varje castingtillfälle. Detta medför extraarbete eftersom de båda inte tål varandra och rollerna ska besättas så att de aldrig spelar mot varandra. Rollbesättningsproblemet är att avgöra ifall alla roller kan besättas med de skådespelare som finns till hands. Ingående parametrar är alltså: 
Roller r1r2,... , rn 
Skådespelare p1p2,... ,pk 
Villkor typ 1 (till varje roll): rt kan besättas av p1p2p6 
Villkor typ 2 (till varje scen): i su medverkar r1r3r5r6 och r7

Indataformat
Rad ett består av tre tal: ns och k (antal roller, antal scener och antal skådespelare, n≥1, s≥1, k≥2). 

De följande n raderna representerar villkoren av typ 1 och börjar med ett tal som anger antalet efterföljande tal på raden, följt av de möjliga skådespelarnas nummer (mellan 1 och k, kursiverade i exemplen nedan). 
De sista s raderna är villkor av typ 2 och börjar ett tal som anger antalet efterföljande tal på raden, följt av tal som representerar de olika rollerna som är med i respektive scen. Varje roll förekommer högst en gång på varje sådan rad, så antalet roller på en rad ligger mellan 2 och n.

Fråga: Kan rollerna besättas med högst k st skådespelare så att p1 och p2 deltar men inte är med i samma scener som varandra?

Exempel på godkända indata

nej-instans:
5 5 3
3 1 2 3
2 2 3
2 1 3
1 2
3 1 2 3
2 1 2
2 1 2
3 1 3 4
2 3 5
3 2 3 5
       ja-instans:
6 5 4
3 1 3 4
2 2 3
2 1 3
1 2
4 1 2 3 4
2 1 4
3 1 2 6
3 2 3 5
3 2 4 6
3 2 3 6
2 1 6 

Uppgift
I den här laborationen ska du visa att rollbesättningsproblemet är NP-svårt genom att reducera ett känt NP-fullständigt problem, som finns inlagt i Kattis. Din reducerade instans kommer att granskas och lösas av Kattis. Du får välja mellan att reducera problemen Graffärgning (problem-id: oldkattis:adkreduction1) och Hamiltonsk cykel oldkattis:adkreduction2). Indataformat för dessa problem beskrivs nedan. Din uppgift är alltså att implementera en reduktion, inte att lösa problemet.

Kattis testar om din reduktion är korrekt, men du måste naturligtvis kunna bevisa att den är det vid redovisningen. Kattis svar är egentligen avsedda att vägleda dig i arbetet med beviset och påpeka om du glömt något viktigt specialfall. Vid redovisningen kommer handledaren också att fråga varför problemet ligger i NP och vad komplexiteten är för din reduktion.

Vid rättningen utnyttjas en lösare för instanser av ett (annat) NP-fullständigt problem inom rimliga storleksgränser. Av tekniska skäl har Kattis en maximal tillåten storlek på instanserna. Du får bara meddelanden om den ifall du skickar in en för stor instans. Du får redovisa din reduktion om du kan bevisa att den är korrekt, oavsett om Kattis har godkänt den eller inte.

Graffärgning
Indata: En oriktad graf och ett antal färger m. Isolerade hörn och dubbelkanter kan förekomma, inte öglor.

Fråga: Kan hörnen i grafen färgas med högst m färger så att inga grannar har samma färg?

Indataformat: 
Rad ett: tal V (antal hörn, V≥1) 
Rad två: tal E (antal kanter, E≥0) 
Rad tre: mål m (maxantal färger, m≥1) 
En rad för varje kant (E stycken) med kantens ändpunkter (hörnen numreras från 1 till V)

Hamiltonsk cykel
Indata: En riktad graf.

Fråga: Finns det en tur längs kanter i grafen som börjar och slutar på samma ställe och som passerar varje hörn exakt en gång?

Indataformat: 
Rad ett: tal V (antal hörn, V≥1) 
Rad två: tal E (antal kanter E≥0) 
En rad för varje kant (E stycken) med kantens starthörn och sluthörn (hörnen numreras från 1 till V)

Teoriuppgifter

  1. Skriv på valfritt sätt ned en lösning till ja-instansen av rollbesättningsproblemet som finns som indataexempel.
  2. Visa att rollbesättningsproblemet ligger i NP.
  3. Förändra nej-instansen i exemplet på indata till en ja-instans. Hur många skådespelare behöver du lägga till i just detta fall?
  4. Vilken är den minsta möjliga produktion som uppfyller indatakraven för rollbesättningsproblemet och som går att sätta upp? Skriv upp indata för denna produktion!
  5. Tänk dig en instans där rollerna är indelade i två grupper, ungefär som i matchningsproblemet, där rollerna aldrig förekommer i samma scener som roller ur samma grupp. Hur många skådespelare behövs då?
  6. Anta att film a innehåller en scen med rollerna 4, 7 och 12 medan film b har tre scener med rollerna 4 och 7, 7 och 12 samt 4 och 12. Om alla övriga villkor är identiska mellan filmerna - kommer svaren då att bli likadana? Varför/varför inte?

Extrauppgift

Frivillig extrauppgift som redovisas på ett särskilt redovisningstillfälle den 10 januari 2014 kl 13-16 i Spelhallen och då kan ge betyg A eller B på lärandemålet om hantering av problem med hög komplexitet (och då behöver man inte examineras på det lärandemålet på muntan). Uppgiften görs individuellt. För att få redovisa extrauppgiften måste du vara godkänd på teoritentan.

Du ska välja att implementera valfri heuristik som löser konstruktionsproblemet: Vilka skådespelare ska ha vilka roller för att lösa rollbesättningsinstansen med så få skådespelare som möjligt? Indataformatet för rollbesättningsproblemet är detsamma som tidigare. Divorna är 1 och 2.

Utdataformat: 
Rad ett: antal skådespelare som fått roller 
En rad för varje skådespelare (som fått roller) med skådespelarens nummer, antalet roller skådespelaren tilldelats samt numren på dessa roller

Problemet ska lösas enligt villkoren som specificerats för rollbesättningsproblemet, dvs divorna måste vara med men får inte mötas, ingen roll får spelas av flera personer, och ingen skådespelare får spela mot sig själv i någon scen. Bättre heuristik (dvs färre skådespelare) ger bättre betyg. Endast lösbara instanser kommer att ges som indata, men för att heuristiken i polynomisk tid säkert ska kunna hitta en lösning så är det tillåtet att använda högst n-1 särskilda superskådisar med nummer k+1k+2, ... Varje superskådis kan spela vilken roll som helst, men kan bara spela en enda roll.

Några testfall att testa ditt program med finns på /info/adk13/labb4/testfall/

Problemet heter oldkattis:adkcasting i Kattis. Kattis summerar antalet använda skådespelare i testfallen och returnerar summan. För betyg B krävs ett resultat bättre än 560. För betyg A krävs 460 eller bättre. Bara den som är godkänd på teoritentan får redovisa extralabben.

Viggo Kann created page 21 August 2013

Administrator Viggo Kann changed the permissions 4 September 2013

Kan därmed läsas av alla och ändras av lärare.
Erik Lindén removed his/her comment
Carl Thomé removed his/her comment
commented 9 November 2013

Kan det tillhöra en ja-instans om varken divorna p1 eller p2 får minst en roll i någon scen men båda var med vid castingen för minst en roll i samma produktion?

Viggo Kann removed his/her comment
Teacher commented 9 November 2013

Ja-instanser är instanser som har svaret ja på frågan: Kan rollerna besättas med högst k st skådespelare så att p1 och p2 deltar men inte är med i samma scener som varandra? Divorna måsta alltså spela med i filmen.

commented 10 November 2013

Är det giltigt med indata som har roller som aldrig är med i någon scen?

commented 11 November 2013

Får man i teroiuppgift 3 ändra indata så att divorna byter plats? Tex att r4 kan innehas av diva 1 istället för diva 2?

Teacher commented 11 November 2013

I teoriuppgift 3 kan du tänka att du är castingansvarig på riktigt. Då kan du inte peka ut vilka skådisar som ska vara divor, utan du får acceptera dom skådisar (och scener) som finns. Försök alltså att göra om instansen till en ja-instans genom att anlita nya skådisar, för det är något som är rimligt att göra i verkligheten.

commented 11 November 2013

På teorifråga 5, gäller reglerna kring divorna även i denna fråga eller ska man inte räkna med divorna alls? 

Assistant commented 12 November 2013

Även på teorifråga 5 är det rollbesättningsproblemet som vi utgår ifrån. Det är bara "tilläggsvillkor" som presenteras i frågan.

commented 12 November 2013

I uppgift 3:

Får man ta bort scener för att lösa castingproblemet?

Assistant commented 12 November 2013

Se Viggos inlägg igår - tänk dig att någon annan har skrivit filmerna, och berättat vilka (sorters) skådisar som passar för de olika rollerna. 

Johan Arnör removed his/her comment
David Ekermann removed his/her comment
commented 18 November 2013

Jag är lite förvirrad då jag inte riktigt vet vad ni vill att jag ska göra!

Jag började för några dagar sedan att skriva ett program som översätter casting problemet till ett problem som löses med graffärgning.. I mina ögon så var detta uppgiften! Nu idag fick jag reda på att man ska reducera problemet graffärgning till casting och inte vise versa, av en kompis.. Och hans argument lät rimligt, det står: "reducera ett känt NP-fullständigt problem"

Varför är alla exempel som är bifogade i casting-format och inte hamilton/graffärgning om vi nu inte ska reducera dessa? 

Mvh förvirrad student

Assistant commented 18 November 2013

Labb 4 berättar om ett problem (inklusive indataformat) som vi vill veta något om. Det är oftast det man har när man vill visa att ett problem är NP-fullständigt: en formulering av problemet, mer eller mindre välspecificerad. Det är för att det är det nya problemet som vi behöver veta saker om och ge exempel på. De "kända NP-fullständiga problemen" känner vi redan till.

Att läsa lydelsen noga är bra, men tänk också på att vi gör på samma sätt när vi visar att ett problem är NP-fullständigt i labben som vi gör på föreläsningar, övningar och mästarprov! Det är att välja problem att reducera, att utföra reduktionen och att argumentera för att den är effektiv och korrekt som de olika kursaktiviteterna är tänkta att träna.

Hoppas att detta hjälper mot förvirringen!

commented 18 November 2013

Hej Emma!
Tyvärr så blev jag inte klokare av vad du skrev!

Kanske går det att svara på.. i mappen labb4 så har vi exempel på indata, men till vad?

commented 18 November 2013

Testfallen i mappen är till extrauppgiften då man ska lösa rollbesättningsproblemet och har inget med labb 4 att göra.

Labb 4: Visa att rollbesättningsproblemet är NP-svårt.
Extrauppgift: Lös rollbesättningsproblemet approximativt.

commented 18 November 2013

Det som ligger i mappen labb4 tillhör extrauppgiften som kan redovisas den 10 januari, och alltså inget som skall användas nu.

commented 20 November 2013

Hur kan n och s tillåtas vara 1 så att man får en scen med en roll och ändå hävda att man förbjuder monologer? Jag kanske missförstår? :)

commented 29 November 2013

Hej. Jag får "Otillåtet skådisnummer i lösningen". Hur kommer det sig, man fick ju lägga till hur många superskådisar man ville?

Assistant commented 29 November 2013

Emil: "Hur många superskådisar man vill" ska tydligen tolkas som att det får finnas max k+n st skådespelare totalt, och det högsta tillåtna skådespelarnumret var k+n-1, att döma av hur felmeddelandet uppstår. :)

Det vore klart bättre om den restriktionen inte såg ut just så, helt odokumenterat, tack för buggrapporten!  

Teacher commented 29 November 2013

Jag har nu lagt till information i labblydelsen om begränsningen av antalet superskådisar.

commented 29 November 2013

Hmm. Men om det får finnas högst n + k skådespelare och de numeras från 1 och uppåt blir väl den sistas nummer n + k, och inte n + k - 1 väl?

Assistant commented 30 November 2013

Emil: My bad, jag tittade inte jättenoga igår, och tolkade villkoret att skådespelarnumret skulle vara mindre än n+k som om någon tänkt sig max n+k skådespelare. Då tänkte jag förstås nollindexerat. Viggo läste noggrannare och hans uppdatering av problemlydelsen ovan tar hänsyn till 1-indexeringen. Eftersom divorna ändå måste vara med är det ju inga problem med att ha den gränsen, bara man berättar om den...

Elias: Jag tror att det enda som faktiskt kommer att tolkas som monologer just nu är scener som skrivs ut och som bara innehåller en skådespelare, åtminstone i grundversionen av labben. Att instanser får ha endast en scen kommer i en striktare tolkning "monologer" bara att betyda att det är en nej-instans. Nästa år när labben anpassas till Kattis nya problemformat kan vi även passa på att göra monologdefinitionen lite mera intuitiv, dvs explicit kräva att alla roller är med i någon scen.

commented 30 November 2013

Finns det några speciella krav för koden/algoritmen för extrauppgiften när man ska redovisa, förutom att programmet blir accepterat på Kattis och kommer under så många poäng man behöver (460 för A eller 560 för B)?

Teacher commented 1 December 2013

Emil: Koden ska lösa problemet i uppgiftslydelsen och den ska passera Kattis. Det är allt. Sedan måste man som vanligt kunna svara på frågor om sin kod vid redovisningen.

commented 1 December 2013

En sak jag funderat på:

Divorna "är garanterade vid varje castingtillfälle", betyder det att de är garanterade minst en roll, eller betyder det att de är garanterade minst en roll som faktiskt medverkar i någon scen. Det vill säga är det tillåtet att divan spelar bara en enda roll, fast rollen medverkar aldrig i någon scen?

Eller kan man anta att man inte får ha indata med roller som aldrig medverkar i någon scen?

commented 9 December 2013

Kan man få godkänt på uppgiften ifall man har en ickedeterministisk heuristik?

Teacher commented 9 December 2013

Ja. Heuristiker som använder slump är ofta bra, och speciellt bra är att man kan köra flera varv och få olika lösningar och plocka den bästa.

commented 14 December 2013

Någon som vet vad som "Otillåtet skådisnummer i lösningen" innebär? Är det endast att man har för många superskådisar? För även som jag inte skriver ut något superskådis överhuvudtaget så får jag samma felmeddelande på första testfallet i Kattis.

commented 14 December 2013

Det är löst nu iaf. Antar att otillåtet skådisnummer innebär < 1 samt >= n+k.

Jonas Stendahl removed his/her comment
Jonas Stendahl removed his/her comment
Jonas Stendahl removed his/her comment
commented 16 December 2013

Jag har felsökt detta felmeddelande i 6 timmar idag och vill försäkra mig om att jag har förstått det rätt.

"Fel i lösningen: en skådis har tilldelats ett otillåtet rollnummer"


Tillåtna rollnummer är [1 - antalet roller i indata].
Kan detta meddelande även antyda att samma skådespelare spelar i två skilda roller i samma scen? Eller är detta ett annat felmeddelande?

Ytterliggare en fråga är hur man ska hantera roller som inte är med i någon scen? Ska dessa fortfarande tilldelas till en skådis?

commented 16 December 2013

"Endast lösbara instanser kommer att ges som indata, men för att heuristiken i polynomisk tid säkert ska kunna hitta en lösning så är det tillåtet att använda högst n-1 särskilda superskådisar med nummer k+1k+2, ... Varje superskådis kan spela vilken roll som helst, men kan bara spela en enda roll."

Det högsta tillåtna skådespelarnumret är alltså k+n-1. Det minsta skådespelarnumret är 1.

"Kan detta meddelande även antyda att samma skådespelare spelar i två skilda roller i samma scen? Eller är detta ett annat felmeddelande?"

Jag tror det är ett annat felmeddelande.

I fallet hur man ska göra med en roll som inte ingår i någon scen verkar det som att denna ändå måste tillsättas en skådespelare. Emma får gärna bekräfta det. Jag antar att detta även gäller för divorna, dvs. att det räcker att de får en roll, oavsett om rollen faktiskt spelar i någon scen eller inte?

commented 17 December 2013

Kommentarerna här antyder att man ska få olika typer av felmeddelanden beroende på vilka "regler" ens lösning bryter mot. Jag har en lösning som jag testat med flera testfall lokalt och allt går fint... men när jag skickar in den till kattis får jag felmeddelandet "wrong answer" på problem 2 av 8. Jag funderar på om man utifrån detta våga göra tolkningen att det är ett fel i utskriftformat som triggas på andra problemet snararare än att det är någon regel som bryts?

commented 17 December 2013

Står det inget mer under "Error information"?

commented 17 December 2013

Detta är allt jag får

This is a mail from your friendly local Problemset Judge. I'm
saddened to inform you that your submission (ID: 476088) on problem
"oldkattis:adkcasting" was not accepted. It ran for 0.235000 seconds.
On test file 2/8 it failed:
Wrong Answer
I will now go and sulk in a corner for the next 5 minutes while
you fix this problem and resubmit.

Yours truly,

commented 17 December 2013

Ok, men om du går in under dina submissions och trycker på ID-numret så borde du får lite mer info. 

commented 17 December 2013

Jag hade på labb 3 där Kattis klagar på att jag hade extra mellanslag i utskriften och testet inte gick igenom..

Jonas Stendahl removed his/her comment
commented 17 December 2013

Angående min fråga ovan så undrade jag vad tillåtna rollnummer är, inte tillåtna skådespelarnummer?

commented 17 December 2013

Tillåtna rollnummer är ju från 1 till n, i samma ordning som listan över roller i indata där det specificeras vilka skådespelare som klarar den rollen.

Assistant commented 18 December 2013

För att förhoppningsvis göra det lite enklare att lista ut om ett felmeddelande innefattar händelse X eller om det är ett annat felmeddelande, här kommer en lista på alla felmeddelanden som domarprogrammet verkar kunna spotta ur sig:

  • Fel i lösningens första rad
  • Otillåtet skådisnummer i lösningen 
  • Fel i lösningen: samma skådis nämns flera gånger
  • Otillåtet antal roller i en skådisrad i lösningen
  • Fel i lösningen: en reservskådis har fått mer än en roll
  • Fel i lösningen: en skådis har tilldelats ett otillåtet rollnummer
  • Fel i lösningen: en skådis har tilldelats en otillåten roll
  • Fel i lösningen: för många roller angivna för en skådis
  • För mycket data i lösningen
  • Alla roller är inte besatta
  • Skådespelare 1 som är diva är inte med i lösningen
  • Skådespelare 2 som är diva är inte med i lösningen
  • Samma skådespelare har flera roller i samma scen
  • Båda divorna är med i samma scen
  • Trailing output (standardfelmeddelande om utdatat inte är slut när allt data som utlovats på rad 1 är läst)

Det stämmer alltså att alla roller måste besättas, och att det är olika felmeddelanden för ett otillåtet rollnummer (utanför den range som indata specificerat) och otillåten roll (en som inte hade skådespelaren på sin lista över tillåtna roller) och ytterligare ett annat felmeddelande för att en skådis har flera roller i samma scen. 

Ni ska inte behöva göra något aktivt för att undvika monologer - om det förekommer roller som inte medverkar i någon scen så är det tillåtet med sådana roller, för alla skådisar.

commented 20 December 2013

(Tävlingsprogrammerings)uppgifter på Kattis tenderar att specificera gränser för storlek på indata, exempelvis "1 ≤ K ≤ 1000". Finns det några sådana övre gränser på storleksparametrarna n, s, k till castingproblemet, eller måste man stödja "obegränsat" stora tal ("får plats i en 32-bitars int") för dessa?

commented 20 December 2013

De verkar vara i storleksordningen ca 100.

commented 7 January 2014

Kan samma skådespelare stå flera gånger på en rad som representerar en roll i indata?

commented 7 January 2014

Är det något speciellt med testfall nr 6? Jag klarar alla testfall fram tills 6:an då jag får time limit exceeded. Även om jag inte kör flera gånger utan bara kör en enda gång och tar den lösningen så får den time limit exceeded och jag förstår inte varför.

Teacher commented 7 January 2014

Victor: Testfall 6 är stort. Det har omkring 1000 scener.

Tonima: Samma skådespelare borde inte förekomma flera gånger på samma rad. Men jag har inte tillgång till alla testdata så jag kan inte lova att det är så.

commented 7 January 2014

Okej, Är det fortfarande godkänt om man passar Kattis nån gång?

Jag kör exakt samma kod och får ibland Time Limit Exceeded från Kattis

commented 8 January 2014

Ja den beter sig ytterst märkligt för mig med, jag gör små ändringar som bör förbättra tidskomplexiteten, men istället anser kattis att den blir mycket sämre, beror det då på att min herustik baseras på slump och just denna körning tog det lång tid att slumpa fram en lösning, eller beror det på att det faktiskt tar längre tid?

Teacher commented 8 January 2014

Om algoritmen använder slump så är det inte konstigt om vissa körningar tar längre tid. Det är den bästa godkända körningen i Karttis som ska redovisas på labben på fredag.

Victor Hung removed his/her comment
commented 9 January 2014

Om man kör C++ och använder rand() så kommer den alltid generera exakt samma sekvens vid varje körning. Vad jag känner till finns det inget bra sätt att seeda den (med srand) med ett slumpvärde, då time(0) alltid returnerar 0 på Kattis istället för tiden.

Om man kör Java och använder new Random() så genererar den olika tal vid varje körning. Om man dock seedar med ett konstant värde så kommer den alltid ge samma sekvens vid varje körning.

commented 9 January 2014

Emil: Vet du om det finns något bra alternativ till rand() annat än att implementera en egen slumpfunktion för C++?

commented 10 January 2014

rand() är det enda jag känner till. Varför skulle du vilja använda någon annan slumpfunktion?

commented 10 January 2014

rand() är väl pseudo-random så om man seedar den med samma värde får man väl samma resultat varje gång i kattis om man inte kan seeda srand med time(0) ?

commented 10 January 2014

Yes, det stämmer. För att få slump som inte är pseudo-random behöver man ha tillgång till hårdvara, vilket inte går på Kattis. Men pseudo-random räcker så gott som alltid så länge det inte är kryptografi man sysslar med.

Feedback News