Carlsdale Caverns - A Proposed New 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:

1. "the system is not completely connected"
2. "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.

Hi all, I have a solution which works for the small example (so I count reverse routes as well). Although the checker does not accept my solution for the large input. Number of the mapped caverns (second part of the answer) is the same but the number of routes differ. The expected answer for this is much larger than mine. I have checked whether it contains cycles but it does not. Do I miss something important?

Is explicit counting really required?

It is true that I count the routes one by one, even the algorithm is running about 1 second. I know that if a route exists between two different entrances/exits it is the only one -> I can make it even faster, but now this is not the issue. My problem is that I cannot imagine what the difference could be between the small and large examples. No cycles, that's for sure (at least in my observation regarding the large example). I even extended the smaller example with cycles and in that case my algorithm works well, too. And the difference between my answer and the expected number of routes is quite huge, a few hundreds. Is is possible to have another test case which is much similar to the large example but small enough to check it by pencil and paper? Or any hint on that in what direction should I investigate?

My short comment already contains quite a lot. I leave it to CSFPython as the problem author if he wants to add more hints.

Ok, I have done it. Thanks for the reply!