Nyhetsflöde

Bra länkar! :)

Jag hittade denna, kanske är värd att få en plats här:

http://www.cs.usfca.edu/~galles/visualization/Algorithms.html

Riktigt bra och pedagogisk grafisk representation om algoritmer! :)

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?

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.

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

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?

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.

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

Ä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.

I uppgift 3:

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

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. 

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

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!

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?

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.

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

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? :)

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?

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!  

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

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?

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.

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)?

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.

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?

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

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.

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.

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

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?

"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+1, k+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?

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?

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

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,

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

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

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

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.

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.

(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?

De verkar vara i storleksordningen ca 100.

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

Ä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.

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å.

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

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?

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.

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.

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

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

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) ?

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.

I Chrome blir marginalerna väldigt konstiga på denna sida.

Hej

Vi har tittat på sidan i Chrome och förstår inte riktigt vad som är fel. Är det att texten efter punkt kommer längre in än texten utan? I så fall är det för att man gjort en radbrytning efter texten med punken.

/Åsa

Hej

Hur anmäler man sig till muntan? Får man själv välja en av dagarna 15-17 jan?

Sidan där man anmäler sig till muntan ligger inte under någon sida under den vanliga menystrukturen utan ligger lite dolt här: https://www.kth.se/social/course/DD1352/subgroup/adk13/post/munta-och-ommastarprov-den-som-har-minst/

Kanske det vore bättre att lägga in den på sidan Examination under Muntlig tenta?

"Ordinarietentan går den 20 december 2012 klockan 9.00 i sal F1." verkar vara felaktigt, 2012 har varit.

Nu bytt till 2013! Tack!

Om man får A eller B på extralabben, stämmer det då att betyget på teoritentan (så länge det är godkänt) är helt irrelevant för slutbetyget?

Till exempel: Om man får A på båda mästarproven, E på teoritentan och A på extralabben, stämmer det då att man får A i slutbetyg utan att behöva munta?

Ja. För att få redovisa extralabben måste man ha godkänt på teoritentan. Det betyg (A eller B) som man får på extralabben rapporteras som betyg på TEN-momentet. På sista föreläsningen kommer jag att gå igenom betygsättningen och svarar på alla frågor om den.

Hej! Kan någon förklara om tentan kommer vara 20p max? Och om det är så, hur mycket är den maximala bonusen man kan få och vad är gränserna? Är bonuspoängen på summan så man max kan få 20p + bonus eller är de på enskilda uppgifter? Tack

På teoritentan finns frågor som ger totalt 20 poäng. Till det adderas bonuspoängen från labbteori och labbredovisningar, som maximalt är 8. Kolla gärna på extentorna för att se upplägget.

Vilken typ av frågor kommer på muntan för att höja betyget från tentan?

Frågorna på muntan är problemlösningsuppgifter av den typ som finns på mästarprov och på kursens övningar, men eftersom presentationen görs muntligt är det inte samma krav på detaljnivån som på mästarproven. Det är betygskriterierna som bestämmer vad frågorna kan handla om. Till exempel, för nivå A på tentabetyget är betygskriteriet: "konstruera och analysera approximationsalgoritmer eller heuristiker, eller visa undre gränser för approximation". Då kan en fråga till exempel vara: "Konstruera och analysera en algoritm som approximerar problemet X inom en konstant" eller "Visa att problemet Y inte kan approximeras inom 3/2 om inte P=NP".

Jag skrev inte tentamen den 20:e december - när ges omtentan i ADK?

Nästa teoritentatillfälle för ADK är ordinarietentan för kursen DD2352 Algoritmer och komplexitet som går 5 juni 2014 klockan 9-12. En gemensam omtenta för DD1352 och DD2352 ges också i augusti 2014. Efter varje teoritenta finns det möjlighet att munta till högre betyg.

angånde labteorin ska hur ska den redovisas?

Labbteoriuppgifterna får lösas i grupp men till övningen ska var och en ta med sig en egen skriftlig lösning. Det är dock okej om två personer har med var sitt exemplar av samma lösning som man har skrivit tillsammans.

Någon gång under övningens första timme kommer labbteorin att redovisas muntligt för en kamrat. Ni kommer då att grupperas två och två och ställa ett urval av teorifrågorna till varandra. Efter detta ska ni lämna in frågeprotokollet och era skriftliga lösningar till övningsassistenten.

Resultatet av labbteorin kommer några dagar senare att synas i Rapp.

Hur många tecken bör man ta hänsyn till utöver å, ä, ö?

Det givna programmet tokenizer.c definierar vilka tecken som ska vara med och vad som utgör ett ord.

Förstår att en viktig del av labben är att inte använda mycket minne. För att träna på att lösa problem där man inte kan lagra allt i primärminnet. Hur mycket minne får man använda?

Konstant minne (dvs oberoende av antalet ord i indexet) är okej att använda.

Vi får felmeddelandet "export: command not found" när vi försöker export LC_COLLATE=C. Vi har även testat bash -c "export LC_COLLATE=C" utan framgång. Vad gör vi för fel?

Kommandot export hör till bash shell, så om ni kör något annat shell får ni sätta variabler med något annat kommando (till exempel setenv LC_COLLATE C om ni kör tcshell). Eller också startar ni bash med kommandot bash och därefter ger export-kommandot. Se Unixlathunden för mer information.

Annars brukar det gå bra med att skriva allt på samma rad (åtminstone i bash):

anvnamn@dator:~$ LC_COLLATE=C sort ...

Då sätter man temporärt LC_COLLATE=C bara för det programmet som körs.

Om man kör /info/adk13/labb1/tokenizer < /info/adk13/labb1/korpus | sort > /var/tmp/ut hamnar orden å, ä, ö längst upp - vad gör man för att åtgärda detta?

Ge kommandot    export LC_COLLATE=C       innan du kör sort så blir sorteringsordningen som den ska.

Finns det flera möjligheter att redovisa restlabbar eller är det bara den 10:e som gäller?

Det finns en restlabbstid 19 december 2013 och en 10 januari 2014. Se detaljschemat för detaljer. Därefter går det normalt att redovisa restlabbar på labbtillfällena i systerkursen DD2352 under våren.

Vi får NullPointerExeption på testfall 27 på "Reduktion av bipartit matchning till flöde". Något tips om vad som kan vara felet här? Vi har testat med kantmängder som 0 och hörnmängder som 0. Dessutom skapar vi inga objekt, så vi känner oss lite lost.

Tacksam för svar.

Testfall 27 är en stor graf. Det är nog interaktionen med domaren som ger upphov till felet. Se till att in- och utmatningen använder Kattio och att ni gör flush efter att flödesinstansen skrivits ut, så att domaren kan lösa instansen och skriva ut en flödeslösning innan programmet läser den.

Ah det löste sig. Bytte ut allt mot Kattio istället så fungerade samma kod :)

Men en anna sak. Om kattis har accepterat din lösning av "den svarta lådan" i steg två, och sen får du time limit exceeded på steg 3 när man lägger ihop allting, kan man förutsätta att den svarta lådan är bra, och man borde snabba på reduktionen, eller finns det en möjlighet att även flödesproblemet löses för långsamt, även om steg 2 är passerat?

Steg 2 testar flödesalgoritmen på många olika typer av flödesgrafer. I steg 3 kommer flödesalgoritmen bara att testas med instanser som kommer från reduktionen av bipartit matchning, och dessa har ett speciellt utseende. Därför kan det ibland hända att flödesalgoritmer som klarar steg 2 tar lite för lång tid på steg 3, även om detta inte är avsikten.

Tack. Kom på lite fler optimeringar man kunde göra, så löste det sig fint.

Vi får felet "Försöker trycka mer flöde genom kant än den har kapacitet" på första testfallet i labbdel 2 på Kattis. Vi har testat med alla tesfall i kursmappen och allt ser korrekt ut, vi lyckas inte få något likande fel alls med någon testkörning utan allt verkar fungera. När vi skriver ut värdet för flödet för varje kant har vi till och med en koll att den inte är högre än kapaciteten. Några idéer? Hur kan graferna se ut, finns dubbelkanter, lömska grafer eller s och t som inte finns, osv? Hur stora värden på flödet kan det vara, så stora att de inte får plats i en short?

Varför köra short? Int fungerar väl bra?

Om man får felet "Försöker trycka mer flöde genom kant än den har kapacitet" beror det ofta på att man fått flöde i en bakåtkant som har kapaciteten noll. Algoritmen ska klara alla sorters grafer som uppfyller indatakraven, även såna som inte har någon förbindelse mellan källan och utloppet. Inga dubbelkanter. Kapaciteterna ryms i en int (och kanske också i en short).

Testar kattis med flöden som är över 1 i storlek i första uppgiften?

Kattis testar med bipartita grafer, inte med flödesgrafer, i första uppgiften. Flödesgrafen ska ert program generera i reduktionen.

Okej, men kan en kantvikt i den bipartita grafen ha ett värde över 1?

För jag printar ut:  io.println(a + " " + b + " " + 1); vid en kant och tar ingen hänsyn till kantvikten

I reduktionen av problemet bipartit matchning till flödesproblemet så ska alla kanter i flödesgrafen ha kapaciteten 1. Varje kant har flera värden så det är oklart vad du menar med "kantvikten".

Lite osäker på varför jag får wrong answer isf, men det blir ett trevligt problem för dagen...
Som tur är så har jag en till fråga!

I ett av exemplen ovan så är indata:

4
1 4
5
1 2 1
1 3 2<----
2 4 2<----
3 2 2<----
3 4 1

När kattis testar programmet kommer indatan att kunna se ut såhär, för jag har valt att inte läsa av värdet i sista kolumnen då jag antar att i vårt problem kommer den alltid att vara 1!

Men det kan vara så att ni vill ha en generell lösning till ett flödesproblem, stämmer detta?

I uppgift 2 ska ett program som löser flödesproblemet för generella flödesgrafer konstrueras. Det betyder att kapaciteterna inte behöver vara bara 1. Detta framgår av uppgiftslydelsen och exemplen som getts.

Vi har också problem med just uppgift 2 där Kattis anser att vi har "Wrong Answer" men vi kan inte finna var felet ligger, vi passerar aldrig case 1.
Vi har dessutom genererat flertalet grafer med programmet flowgen och jämfört vårt resultat med det som programmet maxflow visar och ser ingen skillnad.

Här är en körning med exemplet som nämndes ovan från io (fet-stil output):

4
1 4
5
1 2 1
1 3 2
2 4 2
3 2 2
3 4 1
4
1 4 3
5
1 2 1
1 3 2
2 4 2
3 2 1
3 4 1

Vi har också problem med wrong answer i uppgift 2. Vi har byggt 3 separata program i java som alla klarar våra testfall utanför kattis. Men i kattis får vi endast "Försöker ta ut mer flöde än vad som trycks in i nod skiljd från källan" samt "Försöker trycka ut mer flöde genom kant än den har kapacitet". Vad kan vara fel? Vi har hittat på så många specialfall vi kan men programmet fungerar för alla.

Tänk på att bakåtkanterna ska ha "initialkapacitet" 0! (Det är inte förrän man har ett flöde genom kanten e som det kan bli aktuellt att minska det flödet. Restkapaciteten på en bakåtkant talar ju om hur mycket man kan minska flödet längs den kanten.)

Ahhh.. sant :) Hade missade de, nu till att optimera koden så att den klarar case 27 :)

Tack Emma! :)

Är cykler tillåtna i uppgift 2?

Flödesgrafen är en generell riktad graf och kan innehålla cykler. Men ett flöde i grafen kan förstås aldrig gå i en cykel.

Vi får Time limit exceeded på testfall 28, är det något speciellt med den grafen eller är den bara väldigt stor?

28 är ungefär lika stort som 27 (nära maxstorleken) och jag har ingen lathund som berättar vad varje testfall är till för...

Det finns ingen dokumentation av vilket testfall som testar vad i Kattis. Labbuppgiften är att skriva ett program som är korrekt och tillräckligt snabbt, och det visas genom att det klarar alla testfall. Om man kör fast på ett specifikt testfall kan man fråga en labbhandledare på nästa labbtillfälle och då kan labbhandledaren (om ni har gått med i adk13 i Kattis) kolla i Kattis på just det testfallet och kanske ge en ledtråd till varför programmet fastnar på det.

Vår algoritm får problem när flowgen ger oss kanter både mellan a och b och mellan b och a. Dvs det finns kanter vars bakåtkant inte har kapacitet 0 i början. Är denna typ av indata korrekt?

Ja, en riktad graf kan ha kanter både från a till b och från b till a. Bakåtkanterna ni lägger till hör till restflödesgrafen som behövs i lösningsmetoden ni använder (Ford-Fulkerson/Edmond-Karp), och är ett sätt att representera att man kan minska flödet längs en kant som redan har flöde. 

Vi klarar alla testfall i del 1, och del 3, men i del 2 får vi time limit exceeded på testfall 27. Finns det nån förklaring till detta? Känns oerhört konstigt. Vi har exakt samma maxflödesalgoritm.

Vi klarar i uppgift 2 galant upp till 26, men i uppgift 27 får vi plötsligt "Utdatafilen inte fullständig, saknades kanter". Att felsöka detta testfall är extremt svårt då vi inte kan hitta några testfall där detta gäller. Hjälp?

Vi får time limit exceeded på testfall 26 i steg 2. Vi kommer inte på fler sätt att göra programmet snabbare, och vi har gjort alla uppenbara optimeringar. Är det något speciallfall som vi kan ha missat?

På uppgift 2 säger Kattis "Memory limit exceeded" på testfall 2. Hur begränsat är minnesutrymmet?

Minnesutrymmet är 64 MB. Det kan man se om man tittar i Kattis på problemsidan. Där ser man dessutom tidsgräns.

Till er som undrar om TLE i steg 3: Det är inte meningen att man ska ha större problem i uppgift 3 än i uppgift 2 med tiden, men det kan ju vara gränsfall. Om ni inte använder Kattio, och skriver i Java, kan ni eventuellt snabba upp IO med att använda Kattio.

Titta i övrigt på vilka datastrukturer ni använder, och att de är tillräckligt snabba, inte innebär en massa indirekta ominstansieringar osv.

Den som använder DFS kan skissa på ett testfall som triggar värstafallskomplexiteten, och se att det kan vara värt att byta till BFS.

För alla som undrar över "Wrong answer" för steg 2, fundera på om er algoritm gör rätt på ett testfall med exempelvis s=1, t=7 och kanterna 

1 2 10, 1 3 11, 2 4 8, 2 5 2, 2 6 11, 3 4 11, 4 2 3, 4 7 8, 5 7 2, 6 7 11,

där det inte ska spela någon roll i vilken ordning stigarna hittas. Det här är ett exempel jag gav till någon som frågade mig tidigare.

Eric, det fel som rapporteras som att det saknades kanter i utdatafilen, är att ni inte skriver ut en så stor utdatainstans som ni påstår i början. Jag vet inte om det är relaterat till andra testfallet ovan.

Vad jag har märkt så verkar trean alltid ta längre tid än tvåan, om man använder samma kod från tvåan i trean.

Marcus: Specialfall i för testfall 26 i adkmaxflow känner jag inte till något om. Jag har bara samma tips som för steg 3 i labben: kontrollera om det finns snabbare datastrukturer eller standardmetoder för det ni vill göra, se till att in- och utläsning är effektiv!

Emil: tack för iakttagelsen!

Den som vill utsätta sitt program för lite tuffare tester kan skicka in koden till problemet maxflow. Formatet för de första raderna av in- och utdata behöver ändras då, men algoritmen ska vara densamma.

Ni som kör Java och får Time Limit Exceeded, här är några optimeringstips:

1. Använd inte LinkedList. Kör istället ArrayList alternativt ArrayDeque (för kö-funktionalitet).

2. För att iterera över en ArrayList, använd inte inbyggda iteratorer utan gör det manuellt, dvs. skriv inte for(Obj obj : list) { ... } utan skriv for(int i=0; i<list.size(); i++) { Obj obj = list.get(i); ... }

I i alla fall uppgift 3 verkar man kunna spara ca 1.5 sekunder på att göra detta enligt mina tester.

För att få ännu bättre tid bör man givetvis köra C++ ;)

Hej!
Jag får felet: "Fel!  Kunde inte läsa svarsgrafen" i uppgift 2.
Någon som vet vad jag gör för fel?

Meddelandet "Fel!  Kunde inte läsa svarsgrafen" i uppgift 2 betyder att programmet inte matade ut något som kunde tolkas som en  "svarsgraf", alltså ett flöde. Det kan till exempel bero på att det inträffat ett särfall (exception) som programmet fångat och skrivit ut istället för att skriva ut ett flöde.

Fast exceptions brukar väl skrivas ut till stderr och inte stdout? Vad jag vet så ignorerar Kattis allting som kommer på stderr.

Det stämmer att Kattis ignorerar stderr, och att det därför är lämpligt att göra sina debug-utskrifter där (även om det har hänt en gång att väldigt frekventa debug-utskrifter gjort att ett program tagit för lång tid).

KATTIS verkar inte ha kursen adk13 ännu. När ändras detta?

Nu är kursen adk13 skapad i Kattis och labb 2-domaren finns med där. Övriga labbar läggs till efter hand.

Gå till adk13 i Kattis och klicka på Jag är student på den här kursen och vill registrera mig på Kattis.

I fråga 4, ska det stå O(2max(n,m)) (linjär tid) eller O(2^max(n,m)) (exponentiell tid)?

Detta uttryck blev fel i överföringen från gamla kurswebben. Det ska stå 2^max(n,m) alltså exponentiell tid. Tack för påpekandet! Jag har nu korrigerat sidan.

Finns det någon begränsning på hur långa orden i ordlistan eller indata är?

Försök konstruera programmet utan att sätta någon ordlängdsbegränsning i programkoden (men självklart sätter tillgången på minne en praktisk gräns). Alla ord i testordlistorna är äkta ord, så minnesutrymmet ska räcka till även om programmet använder kvadratiskt mycket minne.

Får man fler än ett förösk på KATTIS?

Det går bra att skicka in om och om igen till Kattis, även efter det att Kattis godkänt inskickningen. På det sättet kan man fortsätta att optimera och se hur snabbt programmet kan bli, om man har lust med det.

Hej. Kolumnen för A-betyget syns inte här på hemsidan?

Det gick bra att se betygskriterierna i den gamla versionen av KTH Social, men nu när kurswebben lanserats med det nya utseendet så klipps för breda tabeller av. Jag har felanmält detta. Den som vill se betygskriterierna i sin helhet kan kolla i kurs-PM.

Jag ber om ursäkt för detta krångel som beror på att KTH bytte utseende på kurswebben utan att ha testat systemet tillräckligt.

Nu har en ny version av kurswebbspresentationen lagts upp där det finns en Min/Max-knapp uppe till höger som gör att man kan se hela tabellen!