Hello. I gathered some questions about older (2006-2008) problems. As commonly agreed, if you possibly plan to ever use these problemsets for training then please do not read this blog in order not to spoil valuable problemsets. But if you know these problems/solved them or whatever then maybe you can answer some of them.
Link to past problems is here: https://icpc.baylor.edu/worldfinals/problems
Problem C 2006 "Ars Longa"
How to solve it? We have an idea how to determine which of these 2 conditions hold: 1) non-static, 2) unstable or stable, however we do not know how to distinguish unstable and stable. Since every rod affects two balls on its ends with opposite forces (parallel to rod) we can create a variable on coefficient how this rod affects balls and create equations for every coordinate of every not glued to floor ball stating that resulting force is 0 and use Gauss to check whether such system has solution. If it has then construction is static. It seems that in order to check stability we should try using force on every ball (in 3 different directions) and check whether system still has solution, but if we are not mistaken this reasoning fails for a case of a cube (with one side lying on floor) with 4 main diagonals. It is stable, but I think there are no good coefficients for rods if we want to neutralize horizontal force applied to one ball. Did we assume wrong physics model? Or did we simply make some silly mistake along the way?Problem H 2006 "Pockets"
I think this is algorithmically relatively simple problem, I coded it, but I keep getting WA/RTE and I came to the point when I suspect the test data is wrong. If I get RTE this is because of various asserts I put in my code. I deduced that my code thinks that resulting sheet has width 6 or 7 on test it fails on ejudge (thanks to asserts), but computing that width alone is relatively simple. I stress-tested my solution on many tests and that gave 0 errors, I have read that simple part many times and I see no errors. Is there anyone that got this problem accepted?Problem H 2007 "Raising the roof"
I don't how to solve it faster than O(T3) (with significant constant) what clearly would get TLE. Solution in such complexity is pretty straightforward algorithmically, so I won't go into details. I have an idea that might result in faster program, but I don't know if it really does. For every pair of triangles we might compute whether one of them covers another one and in such case create a directed edge between them. Such graph is acyclic, so we can process these triangles in topological order, starting from highest ones. When considering some fixed trinalge in order to compute its visible part it suffices to look at this triangle from above and substract regions that are covered by already processed triangles. When done naively that is too slow, but if we store sum of already processed triangles as some set of boundaries maybe that will speed it up. If it would be allowed to give us many thin triangles such boundary will be of quadratic size, so no improvement is done, but maybe since those triangles have small amount of different vertices (at most V<=300) it is possible to give better bound? Or maybe there is a different approach?Problem C 2008 "Conveyor Belt"
I coded simplest possible approach (backtrack considering all possibilities in every step) with some time-heuristics and got OK on my first submission. Then I removed all heuristics and it still gets OK. I can't bound running time by something better than O(n!) (n is up to 20), but I can't also construct a case when it needs a lot of work (worst I came up with was
and I think higher constant may be achieved). Both proving better complexity bound than O(n!) and constructing cases worse than O(cn) for some constant c both seem to be challenging problems. Is someone able of doing either of these? Or maybe there is a completely different approach in better complexity (I doubt that)? Or did judges simply pose a problem that they have some solution for that simply empirically runs fast enough on their test data?
