Life In 19x19

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.

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.

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.

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

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.

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.

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

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.

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.

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.

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

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.

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

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.

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.