10657 - Prince Frog II

[little joey]

From what Der-Johng Sun writes about getting wrong answers for CDiMa's cases with his AC program, one can conclude that either the judges input contains only the most trivial of cases, or the problemsetter used the wrong algo. I fear it's the last alternative.
From what you say, it looks like there is no easy way to fix the problem (it will either become way too complex or get much too low limiting values to be interesting) so I think we should declare it a non-problem.
It happened before (the (in)famous 10402 comes to mind). And it's like you say: if you want to get accepted, you should use the same (probably wrong) heuristic as the problemsetter (like 10402 which you can get AC by making the same mistake as the problemsetter). But I lost my interest for this problem.
But maybe you can find a way out and fix it?

[Destination Goa]

little joey,

Do you ask me to find a way out? You said about heuristics and olny I said word "heuristics", so I think you addressed your message to me.

If so here are my thoughts. If we limit number of intersections to 8 or may be 6, there shouldn't be too many states, but the problem will still remain quite big for precalculation by hand.

Storing each state achievable via step3 from the one in question in some hash can solve the problem. Then we just BFS through them until we face one where step1 or step2 is applicable, so we can reduce N.

It is possible to apply some basic invariants, so we reduce number of stored states. These are: cyclic shift, orientation change and flip.

Cyclic shift and running backwards over circular list are obvious. Flipping is changing all + to - and vice versa. So, for each start node and given orientation (forwards/backwards) we will always have 1st intersection labelled +1 or -1. Using flipping we make it always +1.

Then, before adding a node to hash, we try all these 4N vairations and select lexicographically smallest one (call it canonical form) which will be actually stored and propagated using step3 until step1/2 is applicable for some reachable state.

I can try this, but my hands write too messy code without suitable tests. So probably you will need to repeat my errors in code rather then repeat someone's errors in algo. I don't know which way is easier

Also, problem statement should change to reflect:
1) Rope ends can always be connected without presenting any new intersections.
2) Give explicit limit for number of intersections.

[little joey]

Destination Goa,

Yes, I was addressing you

Well, what I meant to say is, if you have a good idea to fix the problem and like to do it, you might consider fixing it. From what you write it seems you gave the problem more thought than I ever did.

My initial thoughts (during the contest this problem appeared in) were that there might be some easy way to split state space into knots and non-knots, something like calculating the parity for the fifteen puzzle, or the 'flippancy' for the Rubicks Cube, but I never went further to think it through. I still have the hope that this problem is easier than the 3 steps method, but that might not be the case.

After all, we're still not sure the problem is broken...

[Destination Goa]

little joey,

I remember that contest. As soon as I saw this problem during the contest, I marked it as "wrong" due to the story above. So, actually I didn't think more of it. My thoughts began again when I read the thread, and the method I offered is rather common, so there is no bright idea in it.

What makes me thinking that the problem is incorrect (i.e. it's not about steps 1/2/3) - is its AC percentage. I think it would be 5-15% in this case.

I will try to write solution using steps 1/2/3. But most probably it will get TLE. First I will use run-time-error dichotomy to find actual limits