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:

• Round 3 (May 12 2017)

• Round 2 (May 6 2017)

• Round 1 (April 28 2017)

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.

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.

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.

_________________
be immersed

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.

_________________
be immersed

At the very least, good for interviews.

Indeed

_________________
be immersed

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.

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.

_________________
be immersed

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

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.

_________________
be immersed

Yes, I also saw that effect, and I'm not terribly interested in that sort of competition. "Mickey Mouse time limits" comes to mind
Didn't know such things exist.

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.

_________________
be immersed

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.

_________________
be immersed

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

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

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.

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


TC2:



TC3: (click image for full size if it's too small to read (800 px limit)):



I also tried cases where the starting node and the ending node are the same, such as:


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!