Till KTH:s startsida Till KTH:s startsida

Nyhetsflöde

Logga in till din kurswebb

Du är inte inloggad på KTH så innehållet är inte anpassat efter dina val.

I Nyhetsflödet hittar du uppdateringar på sidor, schema och inlägg från lärare (när de även behöver nå tidigare registrerade studenter).

Maj 2014
under HT 2013 adk13

Viggo Kann skapade sidan 21 augusti 2013

Administratör Viggo Kann ändrade rättigheterna 4 september 2013

Kan därmed läsas av alla och ändras av lärare.
kommenterade 16 maj 2014

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

 
Februari 2014
under HT 2013 adk13

Lärare Viggo Kann skapade sidan 18 februari 2014

Viggo Kann flyttade sidan från Algoritmer, datastrukturer och komplexitet (DD1352) 18 februari 2014

Lärare Viggo Kann ändrade rättigheterna 11 april 2014

Kan därmed läsas av alla och ändras av lärare.
 
Januari 2014
under HT 2013 adk13

Viggo Kann skapade sidan 21 augusti 2013

Administratör Viggo Kann ändrade rättigheterna 4 september 2013

Kan därmed läsas av alla och ändras av lärare.
En användare har tagit bort sin kommentar
En användare har tagit bort sin kommentar
kommenterade 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?

En användare har tagit bort sin kommentar
Lärare kommenterade 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.

kommenterade 10 november 2013

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

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

Lärare kommenterade 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.

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

Assistent kommenterade 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.

kommenterade 12 november 2013

I uppgift 3:

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

Assistent kommenterade 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. 

En användare har tagit bort sin kommentar
En användare har tagit bort sin kommentar
kommenterade 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

Assistent kommenterade 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!

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

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

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

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

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

Assistent kommenterade 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!  

Lärare kommenterade 29 november 2013

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

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

Assistent kommenterade 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.

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

Lärare kommenterade 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.

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

kommenterade 9 december 2013

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

Lärare kommenterade 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.

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

kommenterade 14 december 2013

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

En användare har tagit bort sin kommentar
En användare har tagit bort sin kommentar
En användare har tagit bort sin kommentar
kommenterade 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?

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

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

kommenterade 17 december 2013

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

kommenterade 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,

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

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

En användare har tagit bort sin kommentar
kommenterade 17 december 2013

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

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

Assistent kommenterade 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.

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

kommenterade 20 december 2013

De verkar vara i storleksordningen ca 100.

kommenterade 7 januari 2014

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

kommenterade 7 januari 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.

Lärare kommenterade 7 januari 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å.

kommenterade 7 januari 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

kommenterade 8 januari 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?

Lärare kommenterade 8 januari 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.

En användare har tagit bort sin kommentar
kommenterade 9 januari 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.

kommenterade 9 januari 2014

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

kommenterade 10 januari 2014

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

kommenterade 10 januari 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) ?

kommenterade 10 januari 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.

 
Lärare Viggo Kann skrev inlägget 1 januari 2014
 
December 2013
under HT 2013 adk13

Viggo Kann skapade sidan 21 augusti 2013

Administratör Viggo Kann ändrade rättigheterna 4 september 2013

Kan därmed läsas av alla och ändras av lärare.
kommenterade 17 oktober 2013

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

kommenterade 22 oktober 2013

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

 

Viggo Kann taggade med detaljschema. 31 oktober 2013

kommenterade 29 december 2013

Hej

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

kommenterade 29 december 2013

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?

 
under HT 2013 adk13

Viggo Kann skapade sidan 21 augusti 2013

Administratör Viggo Kann ändrade rättigheterna 3 september 2013

Kan därmed läsas av alla och ändras av lärare.
kommenterade 11 november 2013

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

Lärare kommenterade 12 november 2013

Nu bytt till 2013! Tack!

En användare har tagit bort sin kommentar
kommenterade 1 december 2013

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?

Lärare kommenterade 1 december 2013

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.

kommenterade 5 december 2013

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

En användare har tagit bort sin kommentar
Lärare kommenterade 5 december 2013

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.

En användare har tagit bort sin kommentar
kommenterade 27 december 2013

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

Lärare kommenterade 27 december 2013

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

kommenterade 28 december 2013

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

Lärare kommenterade 29 december 2013

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.

 
Lärare Viggo Kann skrev inlägget 20 december 2013
kommenterade 27 december 2013

Ska man dyka upp sin bokade tid eller starttiden för passet man har bokat in sig på?

Lärare kommenterade 27 december 2013

Trots att bokningssystemet visar starttiden för hela redovisningspasset så ska du dyka upp på den tid du bokat och inte på starttiden för passet.

 
under HT 2013 adk13

Viggo Kann skapade sidan 21 augusti 2013

Administratör Viggo Kann ändrade rättigheterna 4 september 2013

Kan därmed läsas av alla och ändras av lärare.
kommenterade 10 september 2013

angånde labteorin ska hur ska den redovisas?

Administratör kommenterade 10 september 2013

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.

kommenterade 11 september 2013

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

Administratör kommenterade 12 september 2013

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

kommenterade 13 september 2013

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?

Administratör kommenterade 13 september 2013

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

kommenterade 18 september 2013

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?

Administratör kommenterade 18 september 2013

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.

kommenterade 19 september 2013

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.

kommenterade 16 december 2013

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?

Lärare kommenterade 16 december 2013

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

 
under HT 2013 adk13

Viggo Kann skapade sidan 21 augusti 2013

Administratör Viggo Kann ändrade rättigheterna 4 september 2013

Kan därmed läsas av alla och ändras av lärare.
kommenterade 6 december 2013

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

Lärare kommenterade 6 december 2013

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.

 
November 2013
under HT 2013 adk13

Viggo Kann skapade sidan 21 augusti 2013

Administratör Viggo Kann ändrade rättigheterna 4 september 2013

Kan därmed läsas av alla och ändras av lärare.
kommenterade 18 oktober 2013

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.

Lärare kommenterade 19 oktober 2013

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.

kommenterade 19 oktober 2013

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?

Lärare kommenterade 23 oktober 2013

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.

kommenterade 23 oktober 2013

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

kommenterade 28 oktober 2013

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?

kommenterade 28 oktober 2013

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

Lärare kommenterade 29 oktober 2013

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

kommenterade 29 oktober 2013

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

Lärare kommenterade 29 oktober 2013

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

kommenterade 29 oktober 2013

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

Lärare kommenterade 29 oktober 2013

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

kommenterade 30 oktober 2013

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?

Lärare kommenterade 30 oktober 2013

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.

kommenterade 30 oktober 2013

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
kommenterade 30 oktober 2013

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.

Assistent kommenterade 30 oktober 2013

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

kommenterade 30 oktober 2013

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

Tack Emma! :)

En användare har tagit bort sin kommentar
kommenterade 31 oktober 2013

Är cykler tillåtna i uppgift 2?

Lärare kommenterade 31 oktober 2013

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.

En användare har tagit bort sin kommentar
kommenterade 31 oktober 2013

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

Assistent kommenterade 31 oktober 2013

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

Lärare kommenterade 31 oktober 2013

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.

kommenterade 6 november 2013

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?

Assistent kommenterade 6 november 2013

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. 

En användare har tagit bort sin kommentar
En användare har tagit bort sin kommentar
kommenterade 7 november 2013

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.

kommenterade 7 november 2013

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?

kommenterade 7 november 2013

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?

kommenterade 7 november 2013

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

kommenterade 7 november 2013

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

Assistent kommenterade 7 november 2013

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.

Assistent kommenterade 7 november 2013

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.

kommenterade 7 november 2013

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.

Assistent kommenterade 7 november 2013

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!

Assistent kommenterade 7 november 2013

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.

kommenterade 7 november 2013

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++ ;)

kommenterade 15 november 2013

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?

Lärare kommenterade 16 november 2013

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.

kommenterade 16 november 2013

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

Assistent kommenterade 18 november 2013

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