Google Code Jam 2011

[Li Kao]

Problem 1 reminded me of that SoS/SoSoS stuff we have in go tournaments. Where did your big solution go wrong?

Problem 2 was much easier than problem 3 IMO.
Once I realized that I can change into a moving frame, i.e. a vendor either stands or moves with 2m/s to the right it became much easier. Contained a trap in form of a 32 bit int overflow, luckily I was careful with the requirements and thus realized that 10^6*10^6 > 2^32 and used long instead. And I also tried with checked arithmetic to be really sure.

Problem 3 was evil. I think I got the room division code correct, but I couldn't think of a nice to implement coloring algorithm. Was planning to do some divide&conquer based stuff, but ran out of time.

[Kirby]

I have not qualified, yet. The first problem from 1B was easy, I think, but I could not figure out the second one (with the hot dog vendors).

I did not even move on to the third one. I didn't end up even making a submission for the hot dog vendor one, either, because I really couldn't figure it out.

[Kirby]

I guess this means I'll be getting up at 5am tomorrow :-p...

[Li Kao]

Kirby what's your language of choice?

And lavalamp have a look at my helper methods. Those speed up coding the parsing a lot. Perhaps you should write similar methods for go.

[Kirby]

My language of choice is C, Li Kao.

[hyperpape]

Can I turn that same question on you, Li Kao and daniel_the_smith?

[Li Kao]

Pure c? wow
How do you manage with all those built in collections, strings,...

I use C# and daniel uses google go/golang.

[daniel_the_smith]

...Perhaps you should write similar methods for go.

Lol, ok I broke down and wrote another helper

Can I turn that same question on you, Li Kao and daniel_the_smith?

Yeah, I've been using Go (golang.org). These problems don't really take advantage of Go's main strengths (concurrency), but I find it very quick to write Go code. Honestly I could probably be just as fast in C++ if I wrote a bunch of string parsing functions ahead of time. But I hate dealing with strings in C++. I don't think choice of language really matters for this, as long as you know it well. Though I'm not sure how Kirby manages without STL. I think even most interpreted languages would be fast enough if you have the right algorithm.

Sigh, for 1C I did exactly the same thing wrong as 1B: try problem C, give up with 20 minutes remaining, start B, finish seconds after the contest ended (although it didn't work).

C small was easy, I did that first. A was easy, too, though somehow I failed A large. I'm certain I could have done B if I had tried it instead of C large (I had an hour and a half left when I started writing C large). So, strategy fail. Again. I guess part of the problem was me underestimating the number of primes < 10e16, causing my "faster" algorithm to also be too slow.

I did get up at 3:40 am, but I don't think that was too much of a factor as I went to bed way early last night. For round 1A, me being tired was a factor in not solving anything--it was at 8pm my time, I'd programmed all day at work and not gotten much sleep the night before. None of the problems even made sense to me, hehe.

I'm really not used to solving these sorts of problems with time pressure. Maybe I'll actually practice before attempting it next year.

I thought problem C from round 1B was the most interesting (catnip flavors)-- but my recursive room dividing algorithm didn't work and I didn't have time to fix it.

[daniel_the_smith]

Problem 1 reminded me of that SoS/SoSoS stuff we have in go tournaments. Where did your big solution go wrong?

Gah, I should have been more curious and figured it out, it's the same thing that killed my A large solution for 1C-- golang's buffer.ReadLine returns a slice of its buffer, so for datasets larger than the buffer I need to make a copy, not store it directly (facepalm). The irritating thing is I knew this and figured I'd change it when it caused a problem. But the small data fit in the buffer completely, and the large output wasn't obviously wrong... grrr So... I'm dumb, in an irritatingly stupid way...

Well, it wouldn't have been enough to get me in the top 1000 for either one, I think. But at least I would have been in the middle of the pack and not the bottom!

[Kirby]

Well, I valued sleep more than getting up this morning to participate in 1C. So I'm out, now. Good luck to you guys as you advance.

[Kirby]

Pure c? wow
How do you manage with all those built in collections, strings,...

I use C# and daniel uses google go/golang.

I've never used go, but I use C# at work. I do think that C# is a lot easier when it comes to data structures. I like using C, though, because that's what I'm used to for recreational programming (i.e. when I'm not at work).

Maybe I'll try to mix it up a little bit next year.

[Kirby]

I was just looking at the scoreboard for 1C, and it looks like if I had participated, I would have had to get at least 40 points. A lot of people seemed to do this by turning in a solution for each problem. It looks like a lot of people failed with the large inputs for the second and third problems in round C, around 1000th place.

[daniel_the_smith]

... So I'm out, now. ...

Me too, we can play go while Li Kao stresses out doing round 2...

[daniel_the_smith]

I was just looking at the scoreboard for 1C, and it looks like if I had participated, I would have had to get at least 40 points. A lot of people seemed to do this by turning in a solution for each problem. It looks like a lot of people failed with the large inputs for the second and third problems in round C, around 1000th place.

Yeah, if I hadn't had the stupid problem with A large and had focused on B instead of C large, I probably would have been right around place 1000. I wasted over an hour on C large.

C small really was easy:

Code: Select all

func DoCase(t int) {
   params := ReadInt64s(3)
   N, L, H := params[0], params[1], params[2]
   Freq := ReadInt64s(int(N))
   
   //does a number between L and H evenly divide (or is evenly divided by) every Freq?
   F := int64(-1)
   for f := L; f <= H; f++ {
      F = f
      for _, o := range Freq {
         if o > f {
            if o % f != 0 {
               F = -1
               break
            }
         } else if f % o != 0 {
            F = -1
            break
         }
      }
      if F != -1 {break}
   }
   
   if F == -1 {
      fmt.Printf("Case #%d: NOn", t)
   } else {
      fmt.Printf("Case #%d: %dn", t, F)
   }
}

hm, "o" isn't a good name for a variable... I shouldn't do that... (it looks totally different from "0" in my font, honest!)

...but doing anything 10e16 times is not really feasible, so C large was a different story completely...

[Li Kao]

Fail. Solved Problem A and B. But that wasn't enough
Rank 790 with 38 points. And needed Top500 to get to the next round. Rank 500 had 48points in 1h55.