L19 Programming Problem Championship: Round 3 (Graphs)

[Solomon]

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)

[Solomon]

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

[Solomon]

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 .

[Kirby]

My feeling so far with problem 1...

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

[Kirby]

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

[Schachus]

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

Scanner sc = new Scanner(System.in);
while (sc.hasNextInt()) {
int M = sc.nextInt();
int N = sc.nextInt();
// M = 5;
// N = 6;

karte = new int[M][N];
for (int i = 0; i < M; i++) {
String line = sc.nextLine();
for (int j = 0; j < N; j++) {

karte[j]=(int)line.charAt(j);
}
}
Edit: the first while went all the way, because I wasnt sure whether there would be multiple inputs in one file.

Thanks

[quantumf]

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?

[bernds]

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.

[bernds]

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

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.

[Schachus]

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

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

[bernds]

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

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.

[Schachus]

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

[quantumf]

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.

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?

[bernds]

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.

Code: Select all

|
|
| |
  |
| |
|
|

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

[quantumf]

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.

Code: Select all

|
|
| |
  |
| |
|
|

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?