It is currently Wed Aug 23, 2017 5:00 am

All times are UTC - 8 hours [ DST ]




Post new topic Reply to topic  [ 9 posts ] 
Author Message
Offline
 Post subject: L19 Programming Problem Championship: Round 9
Post #1 Posted: Thu Aug 10, 2017 10:10 am 
Gosei
User avatar

Posts: 1828
Location: Bellevue, WA
Liked others: 89
Was liked: 817
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
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:

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 9
Post #2 Posted: Thu Aug 10, 2017 10:17 am 
Gosei
User avatar

Posts: 1828
Location: Bellevue, WA
Liked others: 89
Was liked: 817
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
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!

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 9
Post #3 Posted: Fri Aug 11, 2017 7:34 am 
Dies in gote

Posts: 46
Liked others: 5
Was liked: 7
Rank: 2d
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...

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 9
Post #4 Posted: Fri Aug 11, 2017 9:07 am 
Gosei
User avatar

Posts: 1828
Location: Bellevue, WA
Liked others: 89
Was liked: 817
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
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.

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 9
Post #5 Posted: Fri Aug 18, 2017 7:08 pm 
Dies in gote

Posts: 46
Liked others: 5
Was liked: 7
Rank: 2d
So now I'm curious how Ulrich solved problem D...

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 9
Post #6 Posted: Fri Aug 18, 2017 7:49 pm 
Tengen

Posts: 4003
Location: North Carolina
Liked others: 399
Was liked: 658
Rank: AGA 3k
GD Posts: 65
OGS: Hyperpape 4k
I thought D didn't actually look that hard.
For each index in your sub-array, you want to determine the maximum non-ascending and non-descending sub-arrays starting with that index. However, if I'm reasoning correctly, you can limit the actual cases where you have to search. If you have [n1, n2, n3...] then if n1 <= n2, the array starting with n1 dominates the one starting with n2 for the non-descending direction, and vice versa. So I believe that ends up being an O(n) search. I never actually tested this, so it may have a hole in the logic.

_________________
Occupy Babel!

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 9
Post #7 Posted: Fri Aug 18, 2017 10:21 pm 
Lives in sente
User avatar

Posts: 813
Liked others: 180
Was liked: 134
Rank: 2d
GD Posts: 422
KGS: quantumf/komi/balvenie/loads more
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.

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 9
Post #8 Posted: Sat Aug 19, 2017 8:10 am 
Dies in gote
User avatar

Posts: 59
Liked others: 0
Was liked: 38
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

_________________
u-go.net

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 9
Post #9 Posted: Sat Aug 19, 2017 9:58 am 
Dies in gote

Posts: 46
Liked others: 5
Was liked: 7
Rank: 2d
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.

Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 9 posts ] 

All times are UTC - 8 hours [ DST ]


Who is online

Users browsing this forum: Google [Bot] and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group