Life In 19x19

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

Start Time: 2017-08-11 17:00:00 UTC (Fri August 11 2017 10am PST, 19:00 CEST)
Duration: 168 hours
Problems: 6
Theme: Mixed

Past Rounds:

• Round 8 (August 4 2017)
• Round 7 (June 16 2017)
• Round 6 (June 9 2017)
• Round 5 (June 2 2017)
• Round 4 (May 19 2017)
• Round 3 (May 12 2017)
• Round 2 (May 6 2017)
• Round 1 (April 28 2017)

Doing things a little differently this time:

* Problems are mixed and come from a past contest, rather than a certain problem subtype (since we covered pretty much all the major subtypes at this point).

* Time to finish contest increased from 2 days to 7 days (24 * 7 = 168 hours). I think it would be more productive if we had a contest every other week, so we have 1 week to do the contest, and 1 week to discuss the contest. This would also be more flexible for anyone interested in joining a contest as it's ongoing, since one could certainly do all the problems in a day or less. At the same time, anyone joining when the contest starts could spread the problems out to focusing on just one problem a day and still get all the problems done, which is more leisurely.

Hope to see you there!

Solomon wrote:Time to finish contest increased from 2 days to 7 days (24 * 7 = 168 hours). I think it would be more productive if we had a contest every other week, so we have 1 week to do the contest, and 1 week to discuss the contest

Seems like a good idea. I also wonder whether the overall leaderboard is helpful if we want new people to join. Maybe it's better not to think of it as an ongoing contest, but just a method to have fun and maybe learn a thing or two?

Also, tell us more about those competitive programming meetups you mentioned in the last thread...

bernds wrote:

Solomon wrote:Time to finish contest increased from 2 days to 7 days (24 * 7 = 168 hours). I think it would be more productive if we had a contest every other week, so we have 1 week to do the contest, and 1 week to discuss the contest

Seems like a good idea. I also wonder whether the overall leaderboard is helpful if we want new people to join. Maybe it's better not to think of it as an ongoing contest, but just a method to have fun and maybe learn a thing or two?

Also, tell us more about those competitive programming meetups you mentioned in the last thread...

Good point bernds, I'll drop the leaderboard for now then.

Regarding the competitive programming meetups, it's been something that I and a fellow Go player from my local Go meetup have been going to for the past several weeks on Saturday's. Usually around 6 - 10 people with laptops show up at a meetup location, and we participate in Leetcode's weekly contest that starts at 6:30pm and ends around 8. Afterwards we discuss our solutions and get food afterwards. Coincidentally, a couple of weeks ago we were invited to a house party nearby that had a BBQ going, and there was a Go set there! This was a great way to introduce some of the competitive programming meetup people how to play Go, and I just ran into one of them at the Seattle Go Center this week, so that was pretty cool.

So now I'm curious how Ulrich solved problem D...

I thought D didn't actually look that hard.

Appreciate the new 7 day format. I like not having to set aside most of a weekend day to it, and this way also allows one to ponder a thorny problem for a while ("sleep on it"), which I enjoy. Admittedly the data suggests that I do less this way (only got round to looking at one problem), but it was a bad week. Hopefully next time I'll have a little opportunity to think about it.

Thanks, Solomon, for taking up the contests again. I agree the week-long format is a good idea.

bernds wrote:So now I'm curious how Ulrich solved problem D...

The basic idea was the following: Assume for simplicity that all numbers in the given sequence are different. Then given a query, i.e., an interval, the global maximum of the interval cannot lie in the interior of a magical subinterval. So we can split the interval at the index of its global maximum, and look for maximal magical subintervals in each of the two parts individually. Likewise for the global minimum. Also, the interval with end points the global maximum and the global minimum is always a magical subsequence. Using recursion along these lines turned out to work.

Of course, we are not allowed to assume that the given numbers are unique, so the global maximum (minimum) might be reached at several indices. In principle the same idea can still be applied, but it is a little more involved (and I suspect that one could improve my solution by handling this more cleverly). What I did was looking at the left-most and the right-most index in a given interval where its global maximum (minimum) is achieved, and splitting the interval accordingly: a magical subsequence is contained either in the subinterval to the right of the left-most maximum, or in the subinterval to the left of the right-most maximum, etc.

To quickly find these maxima/minima in each given subinterval, in the first step I computed this information for all subintervals with indices j * 2^i, ..., (j+1)*2^i, for all j and i. From this one can relatively easily obtain the desired information for arbitrary intervals.


What is the "right" way to do problem E? (For some time I was hoping to solve it in Python, by hard-coding much of the required information (for each 1 <= i, j <= 150, those x where the interval [x, x+i] contains exactly j primes). This was still not fast enough, but I was getting tired of this problem so my C++ solution just used that hard-coded data which I already had produced ...)


Best, Ulrich

ugoertz wrote:What is the "right" way to do problem E? (For some time I was hoping to solve it in Python, by hard-coding much of the required information (for each 1 <= i, j <= 150, those x where the interval [x, x+i] contains exactly j primes). This was still not fast enough, but I was getting tired of this problem so my C++ solution just used that hard-coded data which I already had produced ...)

That's what I did. Manually check the first 150 numbers or so where K can have an effect, and if that fails then look up the solution in a precomputed table. If you do it in C, you can compute the information on the fly and still be fast enough, but the table is small enough that you can embed it in the program and then I imagine even Python should work.