JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Marathon Matches Marathon Match 23 Post your approach << PREV    [ 1 2 3 4 ]    NEXT >
 Re: Post your approach (response to post by gsais) | Reply That's an interesting approach to finding the polygon. That's an area I probably should have concentrated on more, as I just use a pattern I thought up the first day. I fail to find the polygon at all in 22/30000 cases.I wrote a one-off tool to optimize the parameter values. I first wrote a general multiple linear regression routine, but it was minimizing delta^2 while I wanted to minimize delta.
 Re: Post your approach (response to post by jdmetz) | Reply My basic algorithm is the same as jdmetz's.I was actually thinking this is what most people in the top 20 were doing, so I am surprised to see so many convex-hull based algorithms.Of course my basic implementation of this only scored ~2475, so I'll briefly describe some optimizations.1) When binary searching 'beyond' a side I would aim towards a probable vertex (the intersection of neighboring sides when viewed as lines).2) After enough checking it becomes possible to estimate the maximum-possible convex polygon, by summing the maximum possible 'cap' outside of each side that hasn't been examined. So I modified my algorithm to return (maximum_possible + current_estimate) / 23) In my last submission I made a modification that would decrease the number of steps allowed in binary searches as M got smaller IF the error term described in 2) was large (>0.01). Overall my average difference is about 0.022 over 8000 test-cases.That is an average score of 4.978. Personally I think there is a case in the 500 systests that my solution is very lucky on, which gives me an extra ~0.5-1 points. But we will see...
 Re: Post your approach (response to post by gsais) | Reply As gsais I had little time (mostly after hours so I'm exhausted), and didn't finish my approach, mainly by the thousands of bugs I entered in my code. In the end I've submitted a solution similar to venco's (keep inside and outside points and choose a point that reduces the unknown area) but my choice of the point was not adecuate. After exhausting the querys I produced 500 convex polygons that fitted in the unknown area and returned the mean area. I expected this to behave much better than it finally did, so, when there was a large number of trials, I simply returned the area of one of them but constructed in a more restrictive way.The polygons were constructed in the following way: 1) pick one main outside point, 2) look for the nearest point in the perimeter of the inside polygon and pick a point in the segment joining them 3) compute two maximal lines through it (ie if the point is in the real polygon the line segment through it will be within the two), 4) look forward and backward for other main outside points reducing the angles between the lines. 5) pick randomly one of the resulting lines and save it. Look for a main outside point not covered in the previous steps and repeat the process with it. Finally construct the proposed polygon using the picked lines and (if needed to complete it) the sides of the square. I never finished my main idea, which was to construct a convex polygon as before in every trial, pick the edge the polygon constructed with more variability and choose the point which reduces more the variability of that edge then start again, I wonder how it would have worked, but it was too complicated.
 Re: Post your approach (response to post by Psyho) | Reply how did you "mutate" your polygons to match new constraints?I mutate the polygons by moving their vertices (but the "source" polygon already satisfies the constraints). Basic pseudo-code:```while (population.size < 1000) { src = pick a random polygon in population // src already satisfies the constraints tgt = src.clone() for each vertex v in tgt do // in random order { repeat up to k times { move vertex v to a random near location if p still satisfies the constraints then break loop undo move } } if tgt != src then add tgt to population } ```The problem with this technique is that each mutation reduces the real randomness of the total population, which is vital for estimating the probability of a point being inside or not.