Life In 19x19 http://www.lifein19x19.com/ |
|
L19 Programming Problem Championship: Round 5 (I/O) http://www.lifein19x19.com/viewtopic.php?f=8&t=14278 |
Page 1 of 1 |
Author: | Solomon [ Wed May 31, 2017 1:55 pm ] |
Post subject: | L19 Programming Problem Championship: Round 5 (I/O) |
Leaderboard
Contest Link: https://open.kattis.com/contests/u2cf55 Start Time: 2017-06-02 17:00:00 UTC (Fri June 2 2017 10am PST, 19:00 CEST) Duration: 60 hours Problems: 6 Theme: I/O Past Rounds: |
Author: | peti29 [ Thu Jun 01, 2017 7:53 am ] |
Post subject: | Re: L19 Programming Problem Championship: Round 5 |
Oh, I just saw this. Joined... |
Author: | Solomon [ Thu Jun 01, 2017 9:53 am ] |
Post subject: | Re: L19 Programming Problem Championship: Round 5 |
To clarify on what "I/O" theme means, the ways of solving the problems can vary like last week, but solving also involves processing the input and output beyond just outputting a line or an integer (and usually you can tell what the problem is just by looking at the input and output, which in most cases you normally cannot do). For an example of what this means, take a look at this problem. |
Author: | bernds [ Sat Jun 03, 2017 8:44 am ] |
Post subject: | Re: L19 Programming Problem Championship: Round 5 |
Some people appear to be missing from the standings page, so I'm giving the thread a little bump in case they haven't seen it. |
Author: | Solomon [ Sun Jun 04, 2017 7:50 pm ] |
Post subject: | Re: L19 Programming Problem Championship: Round 5 |
Been trying to do everything in Python this time, since it seems much easier for dealing with string manipulations instead of C++. Unfortunately I haven't had much time to warm up to it, and feeling sluggish on the problems as a result having only gotten 3 and hopefully a 4th in by the deadline. Also, as an aside, I burned 4 attempts on Jetpack for something quite silly... |
Author: | gamesorry [ Sun Jun 04, 2017 10:09 pm ] |
Post subject: | Re: L19 Programming Problem Championship: Round 5 |
Congratulations to Bernd! Couldn't pass the last test case for Multi-Touch Gesture Classification. Wondering what I'm missing here ... @Solomon: Thank you for the interesting contest. As for the recursion, now I always avoid it unless I'm doing exhaustive searching ![]() |
Author: | Solomon [ Sun Jun 04, 2017 10:12 pm ] |
Post subject: | Re: L19 Programming Problem Championship: Round 5 |
Ah...pretty disappointed with my performance in this round. Despite not having a good chunk of time during the weekend to work on these, as well as wasting time deciding between using C++ and Python and eventually forcing myself to use Python, I should have still done better than just 3. Really it was just a combination of getting distracted and not thinking long enough ![]() I think for next round we'll go back to focusing on problem solving techniques (maybe a return on DP problems?). |
Author: | ugoertz [ Mon Jun 05, 2017 1:29 am ] |
Post subject: | Re: L19 Programming Problem Championship: Round 5 |
Thanks, Solomon, for setting up the contest! This time, I found A, B, C pretty much straightforward. With D I had some problems to meet the time restrictions. (Would you mind posting your solution, Solomon? Since it is more than twice as fast as mine it would be interesting to compare. Form hindsight I am guessing that with my current solution I am storing too much of the paths which turn out to be failures, making the data management slower than necessary.) For F I have a partial solution in the sense that it passes the first two tests, but fails the third one with "Memory limit exceeded" - the reason being that I use Python's own parser which can be accessed via the ast module, to parse the arithmetic expression. Unfortunately, this parser is quite inefficient ... Best, Ulrich |
Author: | bernds [ Mon Jun 05, 2017 4:24 am ] |
Post subject: | Re: L19 Programming Problem Championship: Round 5 |
Thanks for organizing the contest. Solomon wrote: If you have time, I'd love to hear your thoughts on how you did E and F. On the whole I thought this was the easiest round so far, with nothing requiring too much thought. Problem F was a lot of fun though and possibly even gave me quite a useful tool.As for D, I'm puzzled that people are using recursion. If you think of the grid as a graph, with each node having two successors (except for the final column), you can make a backwards path computing nodes which can reach the end (marking as 'X' anything whose successors are both 'X' already). Then you just make one forwards pass where we can tell at each point whether one or both of the successors can reach the end. In the case where both do, the example seems to favour releasing the button, so that's what I did. E is really just a "simple matter of programming". It pretty much tells you all the steps and you just have to write them down (with a little flood-fill-ish first step to identify the touch points). To gamesorry: Not sure what the problem is, but the only difficulty I encountered was computing the correct angles. I ended up using atan2 (y2, x2) - atan2 (y1, x1) and normalizing that into the correct range. It helps to build modified testcases, swapping the two pictures, to verify it's doing the right thing. Maybe compare the numbers you compute to those from my solution: |
Author: | Solomon [ Mon Jun 05, 2017 10:50 am ] |
Post subject: | Re: L19 Programming Problem Championship: Round 5 |
ugoertz wrote: (Would you mind posting your solution, Solomon? Since it is more than twice as fast as mine it would be interesting to compare. Form hindsight I am guessing that with my current solution I am storing too much of the paths which turn out to be failures, making the data management slower than necessary.) |
Author: | gamesorry [ Mon Jun 05, 2017 11:28 am ] |
Post subject: | Re: L19 Programming Problem Championship: Round 5 |
Thank you bernds, after going through your code I found the part I was missing: Description in the problem: Quote: The correspondence is chosen such that the sum of squared distances between corresponding touch points is minimized. However, I took it for granted and used the sum of distances instead: Code: delta = math.sqrt((ax[k]-bx[i])*(ax[k]-bx[i])+(ay[k]-by[i])*(ay[k]-by[i])) Changing it to Code: delta = (ax[k]-bx[i])*(ax[k]-bx[i])+(ay[k]-by[i])*(ay[k]-by[i]) solves the problem. |
Author: | peti29 [ Tue Jun 06, 2017 8:14 am ] |
Post subject: | Re: L19 Programming Problem Championship: Round 5 |
Thanks for organizing the round! Unfortunately this time I had next to no time / energy to program. |
Author: | ugoertz [ Tue Jun 06, 2017 10:39 am ] |
Post subject: | Re: L19 Programming Problem Championship: Round 5 |
Solomon wrote: ugoertz wrote: (Would you mind posting your solution, Solomon? Code: from sys import ... Thanks! That's interesting, and I can see some points where this is faster than my solution ... but I guess I would have to create a large test case in order to see which of the differences really matters. (E.g., it is not clear to me whether printing out each raise move individually with duration 1 is faster than adding things up first.) If I get around to it, I will try to do some profiling. Best, Ulrich |
Page 1 of 1 | All times are UTC - 8 hours [ DST ] |
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |