It is currently Fri Feb 23, 2018 11:30 am

All times are UTC - 8 hours [ DST ]




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

Posts: 1833
Location: Bellevue, WA
Liked others: 89
Was liked: 821
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
Contest Link: https://open.kattis.com/contests/niy786

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

Past Rounds:

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 10
Post #2 Posted: Wed Aug 30, 2017 10:41 am 
Dies with sente

Posts: 75
Liked others: 29
Was liked: 8
Rank: SDK
IGS: 8k
Ooh, I just discovered this. Might be fun.

But the problems seem quite easy, what is the catch?

And before I spend too much time:
How are contestants that have solved all problems ranked against each other? Execution time?

(Read: how do I win? ;-) )

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 10
Post #3 Posted: Wed Aug 30, 2017 11:23 am 
Gosei
User avatar

Posts: 1833
Location: Bellevue, WA
Liked others: 89
Was liked: 821
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
Tapani wrote:
Ooh, I just discovered this. Might be fun.

But the problems seem quite easy, what is the catch?

And before I spend too much time:
How are contestants that have solved all problems ranked against each other? Execution time?

(Read: how do I win? ;-) )

You have to solve them the fastest, although the contest is intentionally spread out over a week so people (like myself hah) can relax and do the problems slowly. I try to be consistent in when these start (Friday 10am PST), so you'd want to try to start right around then. Also, if you make a mistake in a submission, there is a time penalty as well (I think it's a function of the contest length; in a 2-hour contest, it's usually several minutes).

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 10
Post #4 Posted: Fri Sep 01, 2017 2:13 pm 
Gosei
User avatar

Posts: 1833
Location: Bellevue, WA
Liked others: 89
Was liked: 821
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
Congratulations to Ulrich for not only getting all 6, but for getting 5/6 in 1 try! I would be even more impressed if he passed all the test cases with Python :).


This post by Solomon was liked by: gamesorry
Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 10
Post #5 Posted: Fri Sep 01, 2017 11:43 pm 
Dies with sente

Posts: 75
Liked others: 29
Was liked: 8
Rank: SDK
IGS: 8k
This was one of my first competitions of this style, and not sure what I think of it.

These are my thoughts:

First impression: these are not really programming problems. These problems are to programming akin what tesuji puzzles are to playing go. But fair enough.

In this contest, the technique to solve most problems were pretty straightforward (A: sorting, B: set covering+exhaustive search, C: greedy+dfs, D: packing+DP, E: loops - all "tesujis" familiar to me). Hacking down the code for those took only a few minutes each.

Instead the challenges are in other areas. The lessons I learnt here are:
  • Check all "silly" corner cases - the test problems seem to be geared to trip you up if you don't
  • Read the spec carefully (failed D a few times because I did not print out the solution in the right order)
  • Rewrite - don't debug. All of the problems I solved took less than 15-20 mins to hack down, while debugging some corner case can take significantly longer. Delete. Rewrite. That is more time efficient.
Unfortunately those are not really the "fun" part of programming.


One problem was really challenging though. F, the XOR sum. I liked it.
My initial gut feel was that this is a quite hard problem, maybe not even polynomial?
Considering the input sizes used to test, there must be a pseudo-linearish time trick to it. Tried something potentially computationally heavier, but it failed a test problem in the latter half. Tried to revisit it in the last two hours before deadline, but not sure I would have been able to solve it given a full day. Any hints? :-)

Also giving an advantage to whoever submits first is not ideal. Better would be to judge the solution quality (like problem C - make it print a solution with as few pubs as possible (or smth) - and the fewer the better your tie-break) or give better tie break by execution time / memory usage (the faster solver the better).

Since I am in Asia, these contests start like 2am my time - which means by the time I wake up people should have solved most of the puzzles already. In 7-8h I would have solved 4 or 5 of the puzzles in this round, and I would expect nothing less from you ;-)

Let's see if I do this again.

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 10
Post #6 Posted: Sat Sep 02, 2017 4:25 am 
Dies in gote
User avatar

Posts: 62
Liked others: 0
Was liked: 40
Solomon wrote:
Congratulations to Ulrich for not only getting all 6, but for getting 5/6 in 1 try! I would be even more impressed if he passed all the test cases with Python :).


Thanks, Solomon, and thanks for setting up the contest! Yes, I did all of it in Python - the problems this time had a sufficiently relaxed time limit, and I am still much faster at writing code in Python than in C++.

Here is a spoiler for Problem F: My solution is based on the following two observations.

First, if all numbers have different bit length (i.e. number of bits necessary to write out the binary expression, or in other words the position of the leading 1 in the binary expression), then the xor-maximum is very easy to compute. Just sort the numbers and then, starting with the largest one, go through the list downwards and at each step compare the maximum so far with the maximum xor the next number and proceed with the larger of the two.

Second, if numbers a and b are in the list, then replacing b by a^b in the list does not change the set of numbers that can be produced by xor-ing a subset, and in particular does not change the xor-maximum. So to obtain the simple situation described above we process the numbers from the input as follows: If we haven't seen a number of the same bit length before, store the number; if we have seen a number of the same bit length before, xor the new one with the stored one, obtaining something of smaller bit length, and continue with the result.

All in all, it is just 20 lines of code in Python.


Best, Ulrich

_________________
u-go.net


This post by ugoertz was liked by 2 people: gamesorry, Tapani
Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 10
Post #7 Posted: Sat Sep 02, 2017 5:46 am 
Dies with sente

Posts: 75
Liked others: 29
Was liked: 8
Rank: SDK
IGS: 8k
Thanks Ulrich for the clear explanation of your insights into problem F.

Your second observation never occured to me. Instead I went down the murky road of having pools of numbers with constraints that only an odd number can be selected out of some pools, and an even out of some others.

Thanks.

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 10
Post #8 Posted: Fri Sep 08, 2017 7:37 am 
Gosei
User avatar

Posts: 1833
Location: Bellevue, WA
Liked others: 89
Was liked: 821
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
This week I'll be a bit busy to set up the contest, so look forward to Round 11 next week!

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

All times are UTC - 8 hours [ DST ]


Who is online

Users browsing this forum: No registered users and 4 guests


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