It is currently Wed Aug 23, 2017 8:07 pm

All times are UTC - 8 hours [ DST ]




Post new topic Reply to topic  [ 28 posts ]  Go to page 1, 2  Next
Author Message
Offline
 Post subject: L19 Programming Problem Championship: Round 4 (Japan)
Post #1 Posted: Wed May 17, 2017 7:20 am 
Gosei
User avatar

Posts: 1828
Location: Bellevue, WA
Liked others: 89
Was liked: 818
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
Leaderboard

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

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

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

Past Rounds:


This post by Solomon was liked by 2 people: bernds, gamesorry
Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 4
Post #2 Posted: Wed May 17, 2017 12:15 pm 
Dies in gote

Posts: 46
Liked others: 5
Was liked: 7
Rank: 2d
Nice to see this is still going on, thanks for doing it Solomon. Is there a theme for this round? I might have to let you all catch up, there's a new DLC for Assetto Corsa coming out tomorrow.

I did find my Arctic Networks bug, and it's truly embarrassing. I used qsort to sort the final array of edges, and the comparison function subtracted two doubles from each other and returns the result. Why this is terrible is left as an exercise to the reader.

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 4
Post #3 Posted: Wed May 17, 2017 12:38 pm 
Gosei
User avatar

Posts: 1828
Location: Bellevue, WA
Liked others: 89
Was liked: 818
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
bernds wrote:
Is there a theme for this round?
Yes, the theme is Japan. I thought I'd do something a little different for this round, where instead of the theme revolving around a certain data structure (graphs) or problem-solving paradigm (dp, recursion), it's on the topic of the problems themselves. This will make the problems a little more difficult to solve, since it won't be clear right away which technique should be used to solve the problems (which is why I reduced the number of problems to 5 for this round; it would have been 4 but some of the problems are just lukewarm in difficulty), but hopefully it will be more enjoyable as well! I think people will especially like the last one, even though it's also the most difficult.

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 4
Post #4 Posted: Wed May 17, 2017 2:55 pm 
Judan

Posts: 7470
Liked others: 1359
Was liked: 1150
KGS: Kirby
Tygem: 커비라고해
I was so angry from last week's competition that I was considering giving up. But I guess there's that saying, "no pain, no gain"...

I'll try to find time to participate again this week. :salute:

_________________
Discipline is remembering what you want. -David Campbell

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 4
Post #5 Posted: Thu May 18, 2017 8:46 am 
Lives with ko

Posts: 125
Liked others: 13
Was liked: 11
Rank: KGS 5 kyu
Yes. I myself was also considering withdrawing from these contests. But, "not today"!
The thing is, I have very limited free time. On the other hand though it really helps "unrusting" my brain!
(I finally managed to complete my iterative solution for Building Dependencies last night - I'll post it in a moment in the other thread. These problems just stick with me... you can guess my astrology sign...)

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 4
Post #6 Posted: Thu May 18, 2017 8:59 am 
Judan

Posts: 7470
Liked others: 1359
Was liked: 1150
KGS: Kirby
Tygem: 커비라고해
peti29 wrote:
Yes. I myself was also considering withdrawing from these contests. But, "not today"!
The thing is, I have very limited free time. On the other hand though it really helps "unrusting" my brain!
(I finally managed to complete my iterative solution for Building Dependencies last night - I'll post it in a moment in the other thread. These problems just stick with me... you can guess my astrology sign...)


I think that getting good at these programming competitions is just a skill to be learned. I played around with Google code jam before, but never really got into competitive programming that much. I think it's a useful skill, because both speed of development and small perf optimizations matter.

It's a very specific type of programming that these contests require, but getting good at that type of programming probably makes you a better programmer overall.

By the way, I'm not up to date on astrological signs, so I have no idea what sign you are.

_________________
Discipline is remembering what you want. -David Campbell

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 4
Post #7 Posted: Thu May 18, 2017 9:37 am 
Oza
User avatar

Posts: 2725
Location: Seattle, WA
Liked others: 248
Was liked: 540
KGS: oren
Tygem: oren740, orenl
IGS: oren
Wbaduk: oren
Kirby wrote:
It's a very specific type of programming that these contests require, but getting good at that type of programming probably makes you a better programmer overall.


At the very least, good for interviews. :)

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 4
Post #8 Posted: Thu May 18, 2017 9:44 am 
Judan

Posts: 7470
Liked others: 1359
Was liked: 1150
KGS: Kirby
Tygem: 커비라고해
oren wrote:
Kirby wrote:
It's a very specific type of programming that these contests require, but getting good at that type of programming probably makes you a better programmer overall.


At the very least, good for interviews. :)


Indeed :-)

_________________
Discipline is remembering what you want. -David Campbell

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 4
Post #9 Posted: Thu May 18, 2017 9:49 am 
Lives with ko

Posts: 125
Liked others: 13
Was liked: 11
Rank: KGS 5 kyu
Kirby wrote:
I think that getting good at these programming competitions is just a skill to be learned. I played around with Google code jam before, but never really got into competitive programming that much. I think it's a useful skill, because both speed of development and small perf optimizations matter.

It's a very specific type of programming that these contests require, but getting good at that type of programming probably makes you a better programmer overall.

By the way, I'm not up to date on astrological signs, so I have no idea what sign you are.


I'm not into astrology either, but this "relentless trying over and over again" trait of Taurus actually fits quite well in my case.

I'm a professional software developer btw and (to my experience) the focus is considerably shifted in the industrial environment. One is supposed to write easy to understand code, rely on other components, be good at teamwork, follow certain incentives (e.g. the MVVM way of doing things).
The need to come up with (optimal, non-trivial) algorithms to solve complicated mathematical problems seldom arises (again, in my experience).
Premature optimization is even frowned upon as it makes the code more complicated (more difficult to understand for others, more error-prone), costs more time to implement, and may end up totally unnecessary as the part you are to optimize in most cases will not be the performance bottleneck.

That said these problems trigger a part of your problem solving skills that you seldom use, thus help maintain your overall cognitive fitness.

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 4
Post #10 Posted: Thu May 18, 2017 10:53 am 
Dies in gote

Posts: 46
Liked others: 5
Was liked: 7
Rank: 2d
peti29 wrote:
I'm a professional software developer btw and (to my experience) the focus is considerably shifted in the industrial environment. One is supposed to write easy to understand code, rely on other components, be good at teamwork, follow certain incentives (e.g. the MVVM way of doing things).
The need to come up with (optimal, non-trivial) algorithms to solve complicated mathematical problems seldom arises (again, in my experience).
Premature optimization is even frowned upon as it makes the code more complicated (more difficult to understand for others, more error-prone), costs more time to implement, and may end up totally unnecessary as the part you are to optimize in most cases will not be the performance bottleneck.
You'd still want to pick those high-level components that are the most suitable for the task at hand, and I think this is where some of the attempts I've seen posted fall down. Choosing the right representation for the problem at hand will provide an immediate performance benefit and cause fewer problems in the long run.

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 4
Post #11 Posted: Thu May 18, 2017 11:00 am 
Judan

Posts: 7470
Liked others: 1359
Was liked: 1150
KGS: Kirby
Tygem: 커비라고해
bernds wrote:
peti29 wrote:
I'm a professional software developer btw and (to my experience) the focus is considerably shifted in the industrial environment. One is supposed to write easy to understand code, rely on other components, be good at teamwork, follow certain incentives (e.g. the MVVM way of doing things).
The need to come up with (optimal, non-trivial) algorithms to solve complicated mathematical problems seldom arises (again, in my experience).
Premature optimization is even frowned upon as it makes the code more complicated (more difficult to understand for others, more error-prone), costs more time to implement, and may end up totally unnecessary as the part you are to optimize in most cases will not be the performance bottleneck.
You'd still want to pick those high-level components that are the most suitable for the task at hand, and I think this is where some of the attempts I've seen posted fall down. Choosing the right representation for the problem at hand will provide an immediate performance benefit and cause fewer problems in the long run.


I think you're both right, because it depends on what you're trying to solve. Obviously, there's benefit to choosing the right algorithm, and having something that runs fast. It's a very important dimension to software development.

But it's not the only dimension.

Considerations like readability and maintainability aren't important for programming competitions, but can have a big business impact in some cases. I've seen cases where someone doesn't understand code 100%, makes a bug fix, and things get more confusing. After years and years of this stuff, the code gets complicated and buggy. In this case, the problem is in the person checking in a fix that he doesn't understand, but it happens now and then.

Anyway, you don't have to worry about maintainability for this competition, which is a great way to improve your ability in the performance dimension of software development.

_________________
Discipline is remembering what you want. -David Campbell

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 4
Post #12 Posted: Thu May 18, 2017 11:19 am 
Gosei
User avatar

Posts: 1828
Location: Bellevue, WA
Liked others: 89
Was liked: 818
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
oren wrote:
Kirby wrote:
It's a very specific type of programming that these contests require, but getting good at that type of programming probably makes you a better programmer overall.


At the very least, good for interviews. :)
I think it's a bit of a double edged sword. Keeps your DS&A sharp, but especially in competitions where you only have a 90 minutes - 2 hours to solve several problems, readability and cleanliness are sacrificed for keystroke reductions (single-letter variables, huge macro lists, and globals seem to be standard on platforms like TopCoder and Codeforces).

For me, it's no different than any other competitive video games I play. Go and this thing seem to be the only two games I enjoy thus far where I don't feel like I'm wasting my time (unlike games like Hearthstone, which leave me feeling empty inside after several hours of play and wondering what I'm doing with my life...).

One thing I like about doing these problems though as opposed to problems from interview prep books is that you don't have to deal with any sort of temptation on trying to memorize the solutions rather than trying to deeply understand the technique, and the problems are way less dryer than the problems in those books (does anyone actually enjoy "prepping" by studying those books?).


This post by Solomon was liked by: gamesorry
Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 4
Post #13 Posted: Thu May 18, 2017 11:32 am 
Judan

Posts: 7470
Liked others: 1359
Was liked: 1150
KGS: Kirby
Tygem: 커비라고해
Good pont. Sometimes, interviewers aren't only looking for a correct answer, too.

Once in an interview, I was asked to program a fan clock. That was all they told me - there wasn't any other spec.

As it turned out, more than what I actually wrote up on the whiteboard, they were evaluating how well I asked questions to clear up the ambiguity behind the problem they posed...

Not sure I agree that this is a good way of interviewing, but people do it that way sometimes.

_________________
Discipline is remembering what you want. -David Campbell

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 4
Post #14 Posted: Thu May 18, 2017 12:19 pm 
Dies in gote

Posts: 46
Liked others: 5
Was liked: 7
Rank: 2d
Solomon wrote:
I think it's a bit of a double edged sword. Keeps your DS&A sharp, but especially in competitions where you only have a 90 minutes - 2 hours to solve several problems, readability and cleanliness are sacrificed for keystroke reductions (single-letter variables, huge macro lists, and globals seem to be standard on platforms like TopCoder and Codeforces).
Yes, I also saw that effect, and I'm not terribly interested in that sort of competition. "Mickey Mouse time limits" comes to mind :)
Quote:
One thing I like about doing these problems though as opposed to problems from interview prep books is that you don't have to deal with any sort of temptation on trying to memorize the solutions rather than trying to deeply understand the technique, and the problems are way less dryer than the problems in those books (does anyone actually enjoy "prepping" by studying those books?).
Didn't know such things exist.

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 4
Post #15 Posted: Thu May 18, 2017 12:54 pm 
Judan

Posts: 7470
Liked others: 1359
Was liked: 1150
KGS: Kirby
Tygem: 커비라고해
I feel kind of inspired to learn the STL better in C++. Up until now, I've been using C# since I use that for some stuff at work, but C++ seems to be a more popular programming competition language.

The primary dev language I use at work is actually C++, but we don't use STL at all, and have a bunch of custom data structures created internally.

_________________
Discipline is remembering what you want. -David Campbell


This post by Kirby was liked by: Solomon
Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 4
Post #16 Posted: Thu May 18, 2017 2:08 pm 
Dies with sente

Posts: 105
Liked others: 0
Was liked: 11
Rank: KGS 2k
GD Posts: 100
KGS: Tryss
Kirby wrote:
As it turned out, more than what I actually wrote up on the whiteboard, they were evaluating how well I asked questions to clear up the ambiguity behind the problem they posed...

Not sure I agree that this is a good way of interviewing, but people do it that way sometimes.


That depend on what the job is about: If they need you to work with the client (intern or extern) to define their exact needs, this skill may be far more important than your "problem solving" skill.

Missunderstanding between the client and the dev team can cost some serious money

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 4
Post #17 Posted: Thu May 18, 2017 2:57 pm 
Judan

Posts: 7470
Liked others: 1359
Was liked: 1150
KGS: Kirby
Tygem: 커비라고해
Tryss wrote:
Kirby wrote:
As it turned out, more than what I actually wrote up on the whiteboard, they were evaluating how well I asked questions to clear up the ambiguity behind the problem they posed...

Not sure I agree that this is a good way of interviewing, but people do it that way sometimes.


That depend on what the job is about: If they need you to work with the client (intern or extern) to define their exact needs, this skill may be far more important than your "problem solving" skill.

Missunderstanding between the client and the dev team can cost some serious money


Agree. I suppose my main point was just that programming interviews are not always the same as programming competition questions. Programming jobs aren't always, either. It often comes down to what they are looking for and/or what the requirements are.

_________________
Discipline is remembering what you want. -David Campbell

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 4
Post #18 Posted: Fri May 19, 2017 5:29 pm 
Lives with ko

Posts: 125
Liked others: 13
Was liked: 11
Rank: KGS 5 kyu
Hm. This is the first time that I'm reasonably sure that my solution is correct, yet I get rejected with "wrong answer". I suspect that Problem B (Pachinko Probability) might be erroneous... (44% wrong answer can be a hint?)
  • Maybe there is a trick with the input? Maybe there are 500 machines thus no EOF after the last one?
  • Maybe there is some definition ambiguity? Can a declaration of "gate"-ness erase the outgoing edges of a node for example?
Hah, I just tried those two to no avail...

Edit: ah, never mind, I got it. :scratch:
Edit2: 7th best time :D
Edit3: ... out of 18 :roll:


Last edited by peti29 on Sat May 20, 2017 1:33 am, edited 1 time in total.

This post by peti29 was liked by: Solomon
Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 4
Post #19 Posted: Fri May 19, 2017 6:07 pm 
Gosei
User avatar

Posts: 1828
Location: Bellevue, WA
Liked others: 89
Was liked: 818
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
For Problem A, I started off with a pretty naive algorithm that was only passing half of the test cases. After some digging on special graphs, I find myself reading this paper (1981, Rotem) for Problem A... I'm kind of sure it's the right idea, but we'll see.

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 4
Post #20 Posted: Sat May 20, 2017 6:06 pm 
Gosei
User avatar

Posts: 1828
Location: Bellevue, WA
Liked others: 89
Was liked: 818
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
Really puzzled with how much I'm struggling with problem B...it seems like a simple DFS + memo table should get me there, but I'm hitting WA :(. Some of my test cases below and my output:

TC1: (ignore the purple; gates are marked with (G))
Image
Code:
9
8
0 4
1 4
2 4
3 4
4 5
4 6
4 7
4 8
2
5
7

winning paths 8
total paths 16

TC2:
Image
Code:
12
11
0 2
1 2
1 3
3 4
3 5
5 6
6 8
6 9
5 7
7 10
10 11
3
2
4
9

winning paths 4
total paths 6


TC3: (click image for full size if it's too small to read (800 px limit)):
Image
Code:
26
34
0 1
0 2
0 3
0 4
1 5
1 6
1 7
3 7
3 8
3 9
3 10
4 10
4 11
6 12
6 13
8 14
9 14
10 14
10 15
11 15
11 24
11 16
14 17
15 17
16 17
16 18
16 19
16 20
18 21
18 22
21 23
21 24
12 25
13 25
8
2
5
7
17
19
22
23
24

winning paths 17
total paths 20


I also tried cases where the starting node and the ending node are the same, such as:
Image
Code:
5 1
2 4
0
winning paths 0
total paths 4

Some of my submission errors were from me not being sure if total paths should be 4 or 1; tried both scenarios and nothing came out of it unfortunately :(. Any help appreciated!

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

All times are UTC - 8 hours [ DST ]


Who is online

Users browsing this forum: apetresc and 3 guests


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