JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
<< PREV    [ 1 2 3 4 5 6 7 ]    NEXT >
Re: ICPC 2007 results??? (response to post by dgarthur) | Reply
You missed:
- Problem D, "don't forget to remove unnecessary input"
- Problem G, "don't miss an important single word in the middle of the statement"
Having said that, the difficulty level seemed good - it just seemed there were many 'really-annoying-to-code' questions. I thought C was a good non-geometry geometry question.
Re: ICPC 2007 results??? (response to post by sql_lall) | Reply
I believe the only "geometry" problem is Problem H, while the others seem geometry but do not involve geometry or only some basic geometry :)
Re: ICPC 2007 results??? (response to post by dgarthur) | Reply
Could you please write down at least some sketch of a proof, because it is really interesting. This seems the only problem on this finals which is REALLY difficult algorithmically.
Re: ICPC 2007 results??? (response to post by sql_lall) | Reply
When we read problem G, we said: "Easy"; But it took about 2:30 hours to get Accepted for it! We missed many things and we wasted lots of valuable time. We solved only 4, but I think we could solve at least 5 if we didn't do bad at problem G.
Re: ICPC 2007 results??? (response to post by sql_lall) | Reply
I don't really love ACM when the problems are more about paying attention to the smallest detail in the statement than about making an optimized algorithm for an interesting problem.
Re: ICPC 2007 results??? (response to post by dgarthur) | Reply
Initialize X_i = mincut(i, 0) for all i.

Was that choice of initialization necessary for correctness? Could you have chosen any upper bound on X_i? (e.g. n?).
Re: ICPC 2007 results??? (response to post by Minilek) | Reply
You cannot use any upper bound. If you set all vertices to have a value of 1000, you'd remove them all in the first iteration of the loop. I believe you could use an initial value being the degree of each vertex, but I haven't thought it through yet.
Re: ICPC 2007 results??? (response to post by dgarthur) | Reply

- Problem E is basically shortest path on the plane with a polygon removed. This has been asked on an ACM before.


Can you give a hint or link of how to solve this? If the no of points are small i can do a dijikstra, but the complexity will be O(E*log(E)). Here generating the right edges is a challenge, i guess.

Also can anyone give hints on how to solve the other problems as well ... (like I) ...

Congrats to the Warsaw team for their win! Please share your approaches for the problems.
Re: ICPC 2007 results??? (response to post by myprasanna) | Reply
For E, you create the visibility graph as follows:

- A vertex for each vertex of the polygon and for the starting point
- Add an edge between every two points if they only intersect segments
of the polygon at end points and the midpoint is outside the polygon.
- Weight the edge by the time it would take the person to walk that distance.

Now we binary search on the time (we can do this since we are guaranteed to walk faster than the bag moves). Place the bag where it will end up at a given time and add it to the visibility graph and run Djisktra's to answer yes/no on binary search.

One of my coaches came up with a very cute solution to C using convex hull. The other 4 'easy' problems are pretty straight forward.
Re: ICPC 2007 results??? (response to post by sql_lall) | Reply
Discovering that single word in G was fun. Not getting B accepted until I took the time to do a complete rewrite (hey, a rewrite is a rewrite, even if it's just 10 lines...), which was after 4 hours, was not so fun.

At least I managed to get a component review done in the Cybercafe :-)
Re: ICPC 2007 results??? (response to post by dgarthur) | Reply
My only complaint was having a problem that required knowing Pick's Theorem. I dislike programming problems that require knowing an obscure math formula.

I agree with the rest of what you said as well, but maybe not as strongly.
Re: ICPC 2007 results??? (response to post by cep21) | Reply
This particular obscure formula is very famous and appears in programming in math contests all the time.
Re: ICPC 2007 results??? (response to post by cep21) | Reply
I think only knowing that such a formula exists is enough. You can always draw 10-15 triangles and then try to construct a formula.
Re: ICPC 2007 results??? (response to post by cnettel) | Reply
I'm curious, what exactly was the single word?
Re: ICPC 2007 results??? (response to post by NeverMore) | Reply
Yeah, I want to know what the word was too. I solved the problem during the competition, but only after one of my teammates had tried solving it, and then must have 'seen the word'. He explained the problem to me, and I completely rewrote a solution without even reading the problem :) Got it accepted first time, too.
<< PREV    [ 1 2 3 4 5 6 7 ]    NEXT >

RSS