31–40 of 43 posts
Earlier quoted context omitted.
The social graph need not be planar, say if the world is a donut.
I'd consider that a minor adjustment as it would still essentially be a planar graph (with periodic boundary conditions). Locally both of the cases look identical. Just checked wiki while writing this and toroidal embeddings are a subclass of planar graphs.
Earlier quoted context omitted.
I'd consider that a minor adjustment as it would still essentially be a planar graph (with periodic boundary conditions). Locally both of the cases look identical. Just checked wiki while writing this and toroidal embeddings are a subclass of planar graphs.
I'm sorry, the puzzle is asking for a global property. The new text has the adjustments.
We are looking for a graph with highest possible minimum vertice count for any single node. The answer is 6. This graph comes from simply making a hexagonal tiling with node on center and vertices going trough edges. Any tiling with more angles does not produce a planar graph and we'd have to insert polygons with less vertices and thus less neighbours and therefore lowering the smallest edge count.
Earlier quoted context omitted.
I'm sorry, the puzzle is asking for a global property. The new text has the adjustments.
I think I got it now. Don't read this if you are afraid of possible spoiling. We are looking for a graph with highest possible minimum vertice count for any single node. The answer is 6. This graph comes from simply making a hexagonal tiling with node on center and vertices going trough edges. Any tiling with more angles does not produce a planar graph and we'd have to insert polygons with less vertices and thus less…
Earlier quoted context omitted.
I think I got it now. Don't read this if you are afraid of possible spoiling. We are looking for a graph with highest possible minimum vertice count for any single node. The answer is 6. This graph comes from simply making a hexagonal tiling with node on center and vertices going trough edges. Any tiling with more angles does not produce a planar graph and we'd have to insert polygons with less vertices and thus less…
I don't think it's possible to tile a sphere with hexagons. You have to throw a couple of pentagons in. http://en.wikipedia.org/wiki/Geodesic_dome
Earlier quoted context omitted.
Doesn't seem like there is. Also, is my count wrong, or does that only produce 31 white balls? It's still more than the 29, though.
We have 5 from the start. Start producing 4 more (2 jars) at timestep 1. Start producing 4 more at timestep 6. Start producing 22 more at timestep 12. 22 + 4 + 4 + 5 = 35
I wonder how efficient people can make this. I've envisioned all kinds of test cases that crank up the branching factor, require that you find solutions even if you have to trade away white balls for them and other such things.
Just because he made them positive integers doesn't mean that there are no ways to punish solutions that won't scale or those that don't always find optimal solutions.
So how is this "challenge" more interesting than thousands of problems on SPOJ, UVA, topcoder or project Euler?
I challenge you to create a more interesting problem.
a) a known fail percentage - 40% of the time the Jar fails and produces nothing. Maximize expected win.
b) an unknown fail percentage, evenly distributed between 0 and 100%. Find a strategy that maximizes expected win over many runs (each run has new fail probabilities), by perfectly balancing between exploration of jars and exploitation. If you can find an optimal (and practical) strategy for this one I applaud you!
Also, I solved your example with a simple Python brute-forcer with < 1s run time. I don't know if I care enough to write a parser of your file format just to mail it in ;).
Earlier quoted context omitted.
I challenge you to create a more interesting problem.
How about the same problem, but with each Jar having: a) a known fail percentage - 40% of the time the Jar fails and produces nothing. Maximize expected win. b) an unknown fail percentage, evenly distributed between 0 and 100%. Find a strategy that maximizes expected win over many runs (each run has new fail probabilities), by perfectly balancing between exploration of jars and exploitation. If you can find an optima…
Earlier quoted context omitted.
I challenge you to create a more interesting problem.
How about the same problem, but with each Jar having: a) a known fail percentage - 40% of the time the Jar fails and produces nothing. Maximize expected win. b) an unknown fail percentage, evenly distributed between 0 and 100%. Find a strategy that maximizes expected win over many runs (each run has new fail probabilities), by perfectly balancing between exploration of jars and exploitation. If you can find an optima…