Leaderboard

1. bernds - 11
2. dfan - 9
3. ugoertz - 8
4. Solomon - 7
5. quantumf - 3
6. Kirby - 2
7. jeromie - 2
8. peti29 - 2
9. gamesorry - 1

Contest Link: https://open.kattis.com/contests/wvz68t

Start Time: 2017-05-12 17:00:00 UTC (Fri May 12 2017 10am PST, 19:00 CEST)
Duration: 60 hours
Problems: 6
Theme: Graphs

Past Rounds:

• Round 1 (April 28 2017)

• Round 2 (May 6 2017)

For those not familiar with graph theory or want to at least feel ready for the contest on Friday, there's a great section on Kattis where the problems are strictly for implementing certain graph structures or algorithms to test your understanding.

• Minimum Spanning Tree (MST)
• Single source shortest path (SSSP), non-negative weights
• SSSP, time table
• SSSP, negative weights
• All pairs shortest path
• Eulerian path
• Max Flow
• Min-cost Max Flow

One thing I want to note is that A is not so trivial like last round's, so don't feel bad if you can't get it right away! And the contest starts early today to accommodate European programmers .

My feeling so far with problem 1...

TLE TLE TLE TLE TLE TLE TLE TLE TLE TLE :-p

_________________
be immersed

inverted my thinking to do the problem backwards from my first impression, and finally got it :-p

_________________
be immersed

Hey, I tried to do something, but I'm already not sure how to read the input.

can someone tell me if this code in java would achieve reading the input(of the first problem) into a matrix called "karte"(and if not, what do I need to do to achieve that?) :


Thanks

Dominoes 2 is the first really ambiguous question I've seen. Can someone who's solved it explain:

Does a domino knocked over by hand count as "fallen"?
Does the starting domino count as "fallen"?
Can we assume that something magical starts the process?

Or, put in terms of the only given test, is the answer 2 because 1 falls over, then 2 doesn't fall over, then 2 is manually knocked over, after which 3 falls, so its 2 because of 1 and 3, or is 2 because the starting domino is 2, knocked over by hand, which knocks over 3, so the answer is 2 because of 2 and 3?

It's easier if you just ignore the sentences "However, sometimes a domino fails to knock the next one down. In that case, we have to knock it down by hand to get the dominoes falling again."

And yes, knocked down by hand means fallen - you can tell from the example. It's a simple problem.

Not about to comment on Java code since I'm not competent. Easiest way to find out is to print out the map from what you read in and see if it matches what you expect.

Thanks,
That is what I tried and it didnt work, but I wasnt sure whether is was cause the code doesnt work, or because I somehow messed up the console message specifying input and output...

Maybe read the input specification again to see if you got your Ns and Ms mixed up maybe, or something else is different than your program expects? Print out the numbers and lines as you read them in to make sure that is all as expected.

yeah thanks, reading the input seems to work now at least, it was indeed wrong(I read one empty line and also I converted char to int in the wrong way).
Edit: so at least after submitting I now got the first test case right, and then "wrong answer" on the second one, which means, I can now maybe focus on mistakes in my logic rather than my syntax

Thanks, that helps. The sparse test data and vague phrasing means it's ambiguous and anything but simple. Follow up question - what is the point of the m pairs? Surely there will be a pair for every domino (1:2, 2:3, 3:4 etc up to n-1:n)? Or should we deal with potential gaps, or pairings that are not consecutive, e.g. domino 2 knocks over domino 7, or even worse, domino 6 knocks over domino 3?

The numbers are just there to unambiguously identify each domino, they do not specify how they are placed on the table. You could place dominos like this (view from above, these are supposed to be three dominos in a triangular formation), and pushing the right one over to the left would topple the other two.


The other way to go about it is to consider the theme of this round and think about how it relates to this problem.

That's a fair point and good hint. Now I keep failing on Test 3, but I can't conceive of a test scenario that makes my code fail. Can anyone advise a fiendish structure that will challenge my solution?

Still get TLE on dominoes2. When I tried using an array to store lists of rules, I got memory limit exceeded.

For me, these problems are about 10% getting the right answer, and 90% trying to get it fast enough.

I must be doing something inefficient... A little frustrating for something that should be simpler...

Maybe I'll take another look tonight. Depends on my mood.

_________________
be immersed

No idea, it could be anything. Are you sure none of your dominos fall more than once?

I'll give the same advice as I gave to quantumf earlier: consider the theme of the round and how it relates to the problem. What kind of data structure are you trying to build? Have you ever worked with such a structure before or at least seen one in another program? Think about how you need to represent it.

If you've never taken any kind of algorithms or data structures course, you'll probably want to go and buy a book. I have a really old one by Robert Sedgewick which has pretty good coverage; it looks like modern versions of that are available, even on Kindle.

Every scenario I devise I test by hand to check the result, and the algorithm does it correctly. I've tried branching, multiple branching, nested branching, re-combining, isolated structures. Nothing doesn't work. Most probably I'm still missing some fundamental concept.



Here, for instance, I calculate 11, which is presumably correct?

I can confirm that my program computes 11 as well.

It's most likely a very simple issue somewhere. Maybe a corner case when any of the numbers are zero? Maybe there's an issue related to counting from 1..n versus 0..n-1?

One thing I do when I'm stumped by "WA" evaluations is write a testcase generator (I did that for the chess problem in this round). Although in this particular case I have no good idea of how the generator would produce the expected answer, other than by running the same algorithm as the real solution which obviously defeats the purpose.