It is currently Thu Mar 28, 2024 3:17 pm

All times are UTC - 8 hours [ DST ]




Post new topic Reply to topic  [ 66 posts ]  Go to page 1, 2, 3, 4  Next
Author Message
Offline
 Post subject: L19 Programming Problem Championship: Round 3 (Graphs)
Post #1 Posted: Mon May 08, 2017 1:59 pm 
Gosei
User avatar

Posts: 1848
Location: Bellevue, WA
Liked others: 90
Was liked: 837
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
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:

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 3
Post #2 Posted: Tue May 09, 2017 1:40 pm 
Gosei
User avatar

Posts: 1848
Location: Bellevue, WA
Liked others: 90
Was liked: 837
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
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.


Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 3
Post #3 Posted: Fri May 12, 2017 10:44 am 
Gosei
User avatar

Posts: 1848
Location: Bellevue, WA
Liked others: 90
Was liked: 837
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
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 :).

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 3
Post #4 Posted: Fri May 12, 2017 8:59 pm 
Honinbo

Posts: 9545
Liked others: 1600
Was liked: 1711
KGS: Kirby
Tygem: 커비라고해
My feeling so far with problem 1...

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

_________________
be immersed

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 3
Post #5 Posted: Fri May 12, 2017 9:57 pm 
Honinbo

Posts: 9545
Liked others: 1600
Was liked: 1711
KGS: Kirby
Tygem: 커비라고해
inverted my thinking to do the problem backwards from my first impression, and finally got it :-p

_________________
be immersed

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 3
Post #6 Posted: Sat May 13, 2017 5:28 am 
Lives with ko

Posts: 211
Liked others: 16
Was liked: 62
Rank: KGS 1k EGF 2k
KGS: Schachus12
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[i][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


Last edited by Schachus on Sat May 13, 2017 6:09 am, edited 1 time in total.
Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 3
Post #7 Posted: Sat May 13, 2017 6:05 am 
Lives in sente
User avatar

Posts: 842
Liked others: 180
Was liked: 151
Rank: 3d
GD Posts: 422
KGS: komi
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?

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 3
Post #8 Posted: Sat May 13, 2017 6:07 am 
Lives with ko

Posts: 259
Liked others: 46
Was liked: 116
Rank: 2d
quantumf wrote:
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.

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 3
Post #9 Posted: Sat May 13, 2017 6:09 am 
Lives with ko

Posts: 259
Liked others: 46
Was liked: 116
Rank: 2d
Schachus wrote:
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.

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 3
Post #10 Posted: Sat May 13, 2017 6:12 am 
Lives with ko

Posts: 211
Liked others: 16
Was liked: 62
Rank: KGS 1k EGF 2k
KGS: Schachus12
bernds wrote:
Schachus wrote:
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...

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 3
Post #11 Posted: Sat May 13, 2017 6:25 am 
Lives with ko

Posts: 259
Liked others: 46
Was liked: 116
Rank: 2d
Schachus wrote:
bernds wrote:
Schachus wrote:
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.

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 3
Post #12 Posted: Sat May 13, 2017 6:30 am 
Lives with ko

Posts: 211
Liked others: 16
Was liked: 62
Rank: KGS 1k EGF 2k
KGS: Schachus12
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 ;)

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 3
Post #13 Posted: Sat May 13, 2017 6:44 am 
Lives in sente
User avatar

Posts: 842
Liked others: 180
Was liked: 151
Rank: 3d
GD Posts: 422
KGS: komi
bernds wrote:
quantumf wrote:
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?

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 3
Post #14 Posted: Sat May 13, 2017 6:48 am 
Lives with ko

Posts: 259
Liked others: 46
Was liked: 116
Rank: 2d
quantumf wrote:
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:
|
|
| |
  |
| |
|
|


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

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 3
Post #15 Posted: Sat May 13, 2017 8:34 am 
Lives in sente
User avatar

Posts: 842
Liked others: 180
Was liked: 151
Rank: 3d
GD Posts: 422
KGS: komi
bernds wrote:
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:
|
|
| |
  |
| |
|
|


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?

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 3
Post #16 Posted: Sat May 13, 2017 8:39 am 
Honinbo

Posts: 9545
Liked others: 1600
Was liked: 1711
KGS: Kirby
Tygem: 커비라고해
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

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 3
Post #17 Posted: Sat May 13, 2017 8:54 am 
Lives with ko

Posts: 259
Liked others: 46
Was liked: 116
Rank: 2d
quantumf wrote:
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?
No idea, it could be anything. Are you sure none of your dominos fall more than once?

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 3
Post #18 Posted: Sat May 13, 2017 8:59 am 
Lives with ko

Posts: 259
Liked others: 46
Was liked: 116
Rank: 2d
Kirby wrote:
Still get TLE on dominoes2. When I tried using an array to store lists of rules, I got memory limit exceeded.
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.

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 3
Post #19 Posted: Sat May 13, 2017 9:03 am 
Lives in sente
User avatar

Posts: 842
Liked others: 180
Was liked: 151
Rank: 3d
GD Posts: 422
KGS: komi
bernds wrote:
quantumf wrote:
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?
No idea, it could be anything. Are you sure none of your dominos fall more than once?


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.

Code:
1
13 14 3
1 2
1 3
2 4
2 5
4 6
4 7
4 8
6 10
7 11
8 12
5 12
3 9
12 13
9 12
4
5
3


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

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 3
Post #20 Posted: Sat May 13, 2017 9:14 am 
Lives with ko

Posts: 259
Liked others: 46
Was liked: 116
Rank: 2d
quantumf wrote:
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.

Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 66 posts ]  Go to page 1, 2, 3, 4  Next

All times are UTC - 8 hours [ DST ]


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group