Nyhetsflöde

Logga in till din kurswebb

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

Har du frågor om kursen?

Om du är registrerad på en aktuell kursomgång, se kursrummet i Canvas. Du hittar rätt kursrum under "Kurser" i personliga menyn.

Är du inte registrerad, se Kurs-PM för DD2458 eller kontakta din studentexpedition, studievägledare, eller utbilningskansli.

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

September 2015

I have a question about NCPC15:

Do we have to apply in some special way to get course credit or do we apply via the registration process described here?

Anmäl missbruk

Visa tidigare händelser (2)

Lärare

Per Austrin kommenterade 17 september 2015

You register via the process described there.

I have a question regarding Aspen Avenue:

The problem says errors should be within 10^-6 absolute and relative error, but i suspect the judge actually does a string match or has calculated it's test values with sub-optimal precision. Thus one must calculate the answer in the same way as the judge, rather than actually being within error bounds. Are Aspen Avenue's test cases really correct?

A similar problem occurred in ljutnja where the answer must be cast to a 64 bit unsigned integer so that it overflows to an erroneous answer, thus matching the test data and giving a "correct" answer on Kattis.

Anmäl missbruk

Visa tidigare händelser (9)

Fabian Schilling kommenterade 9 september 2015

I'm having the same problem with aspen. Kattis won't accept my answer even after rounding exactly like in the examples. Any help would be appreciated!

Lärare

Per Austrin kommenterade 10 september 2015

I have double-checked and Kattis does use the stated absolute/relative tolerance. So printing the answer with 6 digits and rounding either way will be sufficient (and adding a few more digits to the output doesn't hurt).

In other words the output formatting is not the likely culprit, but there is probably some other bug, either in the algorithm, or in its implementation. I can try to give more concrete hints if I get a Kattis submission ID.

(PS regarding ljutnja I just answered on that post, but do note that what you write here about the answer having to be truncated to a 64-bit integer is not correct.)

Johan Kvastad kommenterade 10 september 2015

Thank you for the answer!

Could you take a look at ID 766056 then? All the test cases i try just give me correct answers to the last decimal.

Also: I commented the ljutnja post and double checked. There is something strange going on having to do with 64 bit integers, as i can get the correct answers simply by taking mod 2^64 to my existing python algorithm, which otherwise gives "wrong answer" on Kattis.

Lärare

Per Austrin kommenterade 10 september 2015

Johan, here is a hint: some parts of the C/C++ standard library do not behave the way you might expect them to, make sure to use the right functions.

Johan Kvastad kommenterade 10 september 2015

Ok, thank you! I am quite new to c++ so this is very likely.

Johan Kvastad kommenterade 10 september 2015

TIL i learned that std::abs is very different from abs. Sometimes.

Johan Brodin kommenterade 15 september 2015

Per Austrin: I think I have a related issue with the tolerance/precision when running in Java. Could you look into ID 790961?

Lärare

Per Austrin kommenterade 15 september 2015

Hi Johan! Your issue is not related to tolerance/precision. You should probably try to convince yourself that your algorithm is correct.

Here's a very unofficial corollary problem to Spiderman's workout which i thought was fun (we might not be allowed to answer it here since we are not supposed to collaborate but you can answer it for yourself for bonus nerd points):

If Spiderman's workout consists of the Fibonacci sequence, for which sequence lengths will he be able to complete the workout, and what are the sequences of up/down moves?

Anmäl missbruk

Visa tidigare händelser (1)

Johan Kvastad taggade med hemtal 1 och spiderman. 11 september 2015

I have a question about the problem formulation in problem Ljutnja (https://kth.kattis.com/problems/ljutnja)

There is a note in the output section of the problem "Note: The test cases will ensure that the result fits in a 64-bit unsigned integer.".

Does this mean that the we should give the answer in a 64-bit unsigned integer, or that answers will never overflow if we use 64-bit unsigned integers?

Anmäl missbruk

Visa tidigare händelser (6)

Lärare

Per Austrin kommenterade 10 september 2015

It means that you can assume that the input satisfies the property that the correct answer, which is an integer, lies between 0 and 18446744073709551615 (inclusive).

(I'm not really sure what you mean by "give the answer in a 64-bit unsigned integer": you always give the answer as a string of digits.)

Johan Kvastad kommenterade 10 september 2015

I might be wrong, let's double check. Compare my submissions id 756596 and 765908:

In both i print the answer using python 3.4 integers which have "unlimited" precision. In one i take the answer mod 2^64. I get correct answer in the one using modulus. I suspect this means that there is a test where the correct answer is larger than 2^64. Such a testcase is possible, e.g. all children want 2*10^9, there are 10^5 children, and only 1 candy, yielding about 22000 times more anger than can fit in a 64 bit unsigned integer. Correct?

Lärare

Per Austrin kommenterade 10 september 2015

Good catch, thanks! The test data for the problem indeed contained some invalid test cases where the correct answer exceeded 64 bits.

I have fixed this, and all old non-Accepted submissions are currently being rejudged -- your initial submissions using unlimited precision will switch state to Accepted in a little while.

2 personer gillar kommentaren

Hi! (question in english, i think there was at least one non-swedish speaking person taking the course)

Question: The course description says we are not supposed to discuss the Hemtal with other students, but can we discuss the problem formulation? That is, can we ask each other to clarify/double check that we understood the problem?

Anmäl missbruk

Visa tidigare händelser (2)

Lärare

Per Austrin kommenterade 4 september 2015

If you have questions about the problem formulations, please ask them here.