Carlsdale Caverns - A Proposed New Problem
Back to General discussions forum
This problem is about a cave system with up to 2000 caverns in it. The need to provide all of the data with the problem has limited the size of the system. I had initially thought of a maximum of around 100000 caverns. Unfortunately I couldn't come up with a simple way of generating the required data using the Linear Congruential Generator, so that a good quality problem would be generated each time. This would have allowed the person solving the problem to generate their own data. The limit of 2000 caverns is probably a reasonable limit on the amount of data which can be supplied with the problem.
Dear Clive and Friends, I'm very sorry for delaying this wonderful problem for the whole week, just found it today. (I guess there was some glitch and notification failed - for now I checked and it works as usual)
Now it's here and let's give it a try! Perhaps this may enlighten some of us about random data generation idea mentioned by Clive.
Clive: thanks for a nice problem!
I do think it's possible to generate the input data via LCG. Say, you declare the (constant) number of caverns - say, C = 10k - and a constant number of cave passages - say, P = 1M - and then provide the LCG seed to generate 2 * P values between 1 and C for the start and end of each cave passage. Then all you need to stipulate is that redundant passages (A connects to B if we already connected these two) and self-connections (A connects to A) should be ignored. Finally, specify that every cave with the number evenly divisible by N (say, N = 20) connects to the surface. Obviously, you might have to play with the values of C, P, and N to get a nice distribution of data.
I think the challenge with this approach will be to guarantee the following two characteristics of the problem:
- "the system is not completely connected"
- "If it is possible to travel between the two caverns by a route which is entirely underground then there will be only one route between the two caverns"
While I don't have good idea for generating the data for this problem with LCG, just wanted to suggest that we, probably can have some amendment for situations when large generated inputs are needed.
Main issue with current approach is probably that large amount of data won't be greacefully handled by the browser in the "input box" on the problem's page - and also can cause issues with copy-paste on some systems - that is something difficult to predict as we can't tell what software users use to browse the site.
However we probably can have it different way - for specific problems there could be link with words "click to open input data" - which leads to the new page, opening in new tab with data in plain-text, so there could be kilotons of them, user will only need to click "save page" and download them. Or perhaps the link should be just "download large input data"... Well, I don't know whichever is less user-friendly :) but still this could help.
So if you think this may be useful for this or some later problem - just tell me to try implementing something like this. Probably there still could be some minor hidden obstacles, but hopefully we'll be able to manage them.