Last year, a lot of L19'ers were interested and participated in the Google Code Jam. If anyone's interested this year, the qualifiers are coming up (April 6/7).

See: https://code.google.com/codejam/

I'll be participating

Good luck, Herman, and good luck to all!

_________________
The Adkins Principle:
At some point, doesn't thinking have to go on?
— Winona Adkins

Visualize whirled peas.

Everything with love. Stay safe.

I'm going to try, though, I'll be in the airport for Korea this Friday when the qualification round starts. Given that it's for 24 hours, maybe I'll have the chance to get some points.

_________________
be immersed

After last year, I was a little annoyed with not solving more. I wanted to practice and be ready for this year. None of that happened.

Right now, I'm pretty excited about a separate project, and have been working on it every time I get a chance. I think I might try to do the Code Jam, but I can't decide what to spend time on.

_________________
Occupy Babel!

Well, in Korea now. A bit jet lagged, but saw that there is still time to work on the qualification round.

I did the first two problems. I can't seem to see how many you need to solve to advance to Round 1. Is it similar to last year?

_________________
be immersed

I see it now - 25 points. Cool.

_________________
be immersed

And note the score displayed on the standings page is "optimistic", i.e. it assumes you get full points when the hidden results are revealed.

Yeah, I get it. That part is the same as last year IIRC.

_________________
be immersed

I don't have time to participate this year, but I'm looking forward to the inevitable discussion that crop up around here! I learned a lot last year.

Well, that was quick - I'm out already. I only attempted the first two problems, and while they passed the small set on the first attempt, the large dataset gave TLE for both. I didn't do any sort of special optimization for either - just breadth first search for the first problem, and pretty much a straightforward implementation of the second.

Oh well. I guess I should have tried the other two problems, too (or thought about perf more, maybe).

_________________
be immersed

What do you mean by "breadth first search" in this case? The trick to the first one is that there is always one highest possible value swap. We can disregard all trailing Cs, then there is an irrelevant prefix followed by a number of S characters. Swapping the first of those S with the previous C will give you the maximum reduction. Example: SCSCSSS -> SCSSCSS.

In the second one, one has to not implement the quadractic bubble sort. The thing to realize here is that each swap leaves the middle element unchanged, so essentially it ends up sorting two arrays which are interleaved. So, put your input elements into two separate arrays as they come in, run quicksort on each, then look for mismatched elements when interleaving them again.

The one I didn't attempt was the two-rotations case for the cube. Played around with wxmaxima but couldn't really find an equation to give me the angle for a given area. I suppose a binary search could easily have found the right spot but at that point I felt I'd done enough.

I didn't try to do any trick. For any given string, I swap each pair of consecutive characters to generate a bunch of new strings (each one representing a possible hack). I add these to a queue for the breadth first search I'm doing. Every time I pop something off of the queue, I check to see the damage. Also, whenever I add to the queue, I'm actually adding a pair to also indicate how many hacks I did to get that string. The unmodified string has 0 hacks, the first set of hacked strings all have 1 hack, the next iteration has 2 hacks, etc.

Anyway, I didn't try to think of any particular properties of swapping - I just generated all possibilities and explored them all. That's what I meant by BFS.



I implemented the quadratic bubble sort, literally taking the pseudocode from the problem description.

I guess I should have been trying to think of ways to optimize and make things fast, but I pretty much wrote things up literally to solve the problems, which I guess wasn't enough for the large datasets.

That being said, I still feel I've improved since last year, even though I didn't make it as far. Last year, I think you were able to tell when you got TLE, since it was manual upload of the output file, so I would have caught the fact that my implementations were too slow. And I wrote things up much faster than last year - in around 20 minutes for each problem, which is faster than last year.

So I'll mark it up as a success, even if I'm out so early this year.

_________________
be immersed

That must have been... innefficient

My code for the two first problems (in C#) :

Problem 1 :


Problem 2 :



Note that in my first problem, I completly abstracted the sequence : I don't swap anything,

Well, I didn't make it.

For problem 1 my code only solved the small set. I haven't looked at what went wrong with the large but I suspect something like an off by one error or perhaps a floating point inaccuracy from Math.log on large numbers.

For problem 2 I only wrote a quick brute force implementation which solves the small but not the large set.

For problem 3 I still have no idea what went wrong. My solution was quite efficient (equivalent to the more efficient solution mentioned in the analysis) and solved all test cases locally (using the provided test script, adjusted to give all sorts of test cases), but when I submitted it, it reported a failure with "Runtime Error" and I had no real way to debug. Very frustrating

I didn't start problem 4. After trying various ways to debug problem 3 I didn't feel like continuing, especially not on the math heavy problem 4, so I quit and went to do something more fun

Which language were you using? Perhaps something turned out not quite as portable between systems as one would hope.

Ruby. My code was:



I don't think I'm using any special features here which haven't been present in ruby since forever.

The code simple creates a 3*X rectangle large enough that it covers sufficient area for the given test, then it keeps finding the 3x3 subrectangle with the most empty cells and outputs the middle cell thereof until the rectangle is filled.

When I try to run it from the script, I get:

Your code exited early, in the middle of Case #1.
Your code finishes with exit status 1.
The stderr output of your code is:
herman3.ruby:11:in `block (3 levels) in <main>': undefined method `sum' for [0, 0, 0]:Array (NoMethodError)
from herman3.ruby:8:in `each'
from herman3.ruby:8:in `map'
from herman3.ruby:8:in `block (2 levels) in <main>'
from herman3.ruby:7:in `upto'
from herman3.ruby:7:in `each'
from herman3.ruby:7:in `min_by'
from herman3.ruby:7:in `block in <main>'
from herman3.ruby:2:in `upto'
from herman3.ruby:2:in `<main>'

Damn. https://blog.bigbinary.com/2016/11/02/r ... e-sum.html

$ ruby -v
ruby 2.4.2p198 (2017-09-14 revision 59899) [x86_64-linux]

But the contest is 2.3.3

I've been using sum since forever, because it's been in ActiveSupport since forever, so I never realized it wasn't bog standard :/

Sorry to hear that. I knew Python was incompatible with itself, but I didn't know anything about Ruby. I'd kind of like to make a case for using industrial strength languages like C rather than these newfangled shiny but fragile things. Why handicap yourself in a contest?

Ruby is over 20 years old, and (speaking as someone who has written more C++ than any other language) I think that when it comes to overall fragility, including how easy it is to introduce subtle bugs, C and C++ are much worse than languages like Ruby and Python.

It is true that you have to be a little careful about making sure that your versions match, which is true for any language with a rich standard library. The current version of Ruby is actually 2.5.1, and the latest version of Ruby 2.3 is 2.3.7, so if you ask me Google is the one who dropped the ball here if they only support 2.3.3.