Hello!
After 3 days of coding and testing I feel feel like I finally have solved the problem. Using all test cases on website and about 20 additional test cases I created myself my program always returning me right answer. When I tried to submit the solution - "Wrong Answer". I am wondering if I really have wrong solution, perhaps bug in my program. So far for all test cases I tried it is returning correct answer.
I am confused and frustrated
Can anyone suggest me a test case on which my program may fail ??? Any other suggestions ?
Since nobody has gotten AC for this problem yet, I suggest you talk to the UVA staff (mail them at problemset@acm.uva.es) or that you contact the problemsetter.
Who knows, there might be a bug in the judge data. Stranger things have happened.
Amadeus wrote:Hello!
After 3 days of coding and testing I feel feel like I finally have solved the problem. Using all test cases on website and about 20 additional test cases I created myself my program always returning me right answer. When I tried to submit the solution - "Wrong Answer". I am wondering if I really have wrong solution, perhaps bug in my program. So far for all test cases I tried it is returning correct answer.
I am confused and frustrated
Can anyone suggest me a test case on which my program may fail ??? Any other suggestions ?
The problem to tell if a knot is the unknot is not an easy one. Which strategy did you adopt in your prog?
Here you get some inputs to play with:
Well my strategy is pretty simple, but it appears to have one flaw. I got some ideas from knots theory websites on the web. I am looking for 3 possible situations: first is a simple when I see sequence like "... -5 +5 ..." I call it a LOOP and it can be removed from sequence, second is when I see something like " ... -6 -11 ... +11 +6 ... " (BRIDGE) also removed. The third and most complicated one - "TRIANGLE" I devided into 4 cases: each one looks like "... +5 -6 ... +6 +9 ... -9 -5 ...", I do not remove TRIANGLES but trying to swap numbers simulating a SLIDE (swaping pairs +5 -6, +6+9 and -9 -5") so that I can possibly find BRIDGE or LOOP after such swap. If I don't have any other errors in my code then problem is in the way I try sliding for TRIANGLES - random. Random works well for some sequences but it does not work for others, so I am looking for another strategy to do slides, perhaps I should try to keep same direction...
Onother mistake I made was that I should have considered sequence as a circle. In your example sequence "-3 +6 -4 +2 +1 -7 -6 +4 -2 +3 +5 -1 +7 -5 0" solved easily by just eliminationg BRIDGES, but my program missed "-3...+3 +5...-5" I'll try again
hello, i had the same ideas about BRIDGES, and LOOPS.
I didnt have the TRIANGLES one, but had the "FREE EXTREMES"... well, if both extreme knot are positives or negatives they are unecessary (or not, hehe)
but im making some mistakes too...
lets trying again
lincolndavid wrote:how can i draw these examples?
i think the first knot must be 1, since we start "walking" from a extreme... dont?
It isn't easy to draw the examples because the notation used is underspecified. You need to know not only if you have an undercrossing or overcrossing but also the orientation of the crossing.
As for the numbering of the crossings, the problem statement says that you must number the crossings, but not that they are numbered in visit order, although the sample input induces to think so...
If you really want you may renumber the crossings while you read them
CDiMa wrote:
It isn't easy to draw the examples because the notation used is underspecified. You need to know not only if you have an undercrossing or overcrossing but also the orientation of the crossing.
As for the numbering of the crossings, the problem statement says that you must number the crossings, but not that they are numbered in visit order, although the sample input induces to think so...
If you really want you may renumber the crossings while you read them
Ciao!!!
Claudio
well, i did renumbered the crossings... and draw the first two examples (I stoped at the second because cant find the mathematical formula to simplyfing it, hehe). there is a walk under all the rope, that can be excluded, but i cant find the "formula" to identify it
I also dicovered another struct, a loop that can be simplifyed, it hapens a lot in your first example.
lincolndavid wrote:how can i draw these examples?
i think the first knot must be 1, since we start "walking" from a extreme... dont?
It isn't easy to draw the examples because the notation used is underspecified. You need to know not only if you have an undercrossing or overcrossing but also the orientation of the crossing.
As for the numbering of the crossings, the problem statement says that you must number the crossings, but not that they are numbered in visit order, although the sample input induces to think so...
If you really want you may renumber the crossings while you read them
Ciao!!!
Claudio
No, of course numbering make no difference, crossings can be numbered in any way. Well, I used to have a renumbering function, but I removed it because I found no use for it. Anyone who can do google search on the internet for "knots theory" can read about existing algirithms. Some webpages even saying that existing algorithms are so complex so that none of them was implemented in real program.
First of all sequence must be treated as circular list, so I rewrote my program completely and now I am using cicular list as data structure. I am able to remove twists, and simple crossings, no problem with that, but "third move" (http://www.freelearning.com/knots/intro.htm) almost always creates configuration where it is hard to gues direction of second, third and other slides. Picking one of possible slides at random toooo slow and not always produce right result.
I was working on other problems, and I am still looking for fresh ideas on this one.
Amadeus wrote:Some webpages even saying that existing algorithms are so complex so that none of them was implemented in real program.
There is an unknot-equivalence algorithm by Haken that is said to be unfeasible on a computer. I didn't even try to look at it and moved on other directions.
Amadeus wrote:I was working on other problems, and I am still looking for fresh ideas on this one.
I was thinking about calculating some knot invariant, but this seems still complicated and slooow. I found source code for two programs that take O(2^n) to calculate some invariants. One of them only works on prime knots and the other needs orientation information that I don't know jet how to extract from the input format.
So I'm still waiting for inspiration...
Amadeus wrote:First of all sequence must be treated as circular list, so I rewrote my program completely and now I am using cicular list as data structure. I am able to remove twists, and simple crossings, no problem with that, but "third move" (http://www.freelearning.com/knots/intro.htm) almost always creates configuration where it is hard to gues direction of second, third and other slides. Picking one of possible slides at random toooo slow and not always produce right result.
I further investigated knot theory and it came up that the last of my inputs is an example of a knot that needs its crossing number to be increased before Reidemeister moves can decrease it.
This leads to the conclusion that your approach needs to be implemented in a very smart way to avoid beeing knotted in a loop of unsuccesful tries of applying Reidemeister moves
Case 1: No
Case 2: Yes
Case 3: Yes
Case 4: No
Case 5: Yes
Case 6: Yes
I don't know why
but I got AC.
Hope this helps.
Der-Johng Sun
Well, I have some ideas about it...
Probably your prog doesn't handle some knot configurations but the sample input is too simple and doesn't contain them.
I didn't even try to submit a program knowing already that my solution wasn't correct...
Well my strategy is pretty simple, but it appears to have one flaw. I got some ideas from knots theory websites on the web. I am looking for 3 possible situations: first is a simple when I see sequence like "... -5 +5 ..." I call it a LOOP and it can be removed from sequence, second is when I see something like " ... -6 -11 ... +11 +6 ... " (BRIDGE) also removed. The third and most complicated one - "TRIANGLE" I devided into 4 cases: each one looks like "... +5 -6 ... +6 +9 ... -9 -5 ...", I do not remove TRIANGLES but trying to swap numbers simulating a SLIDE (swaping pairs +5 -6, +6+9 and -9 -5") so that I can possibly find BRIDGE or LOOP after such swap. If I don't have any other errors in my code then problem is in the way I try sliding for TRIANGLES - random. Random works well for some sequences but it does not work for others, so I am looking for another strategy to do slides, perhaps I should try to keep same direction...
Onother mistake I made was that I should have considered sequence as a circle. In your example sequence "-3 +6 -4 +2 +1 -7 -6 +4 -2 +3 +5 -1 +7 -5 0" solved easily by just eliminationg BRIDGES, but my program missed "-3...+3 +5...-5" I'll try again
"TRIANGLE" should be divided into 8 case, and include negative number in the middle (such as "... -5 +6 ... -6 -9 ... +9 +5 ..."), so should be 16 case.
Other 4 case, such as "... +5 -6 ... +6 +9 ... -5 -9 ..."
Every 2 cases in 8 cases will be roll back the sequence each other. So, I use TRIANGLES - random.
Well. I'll tell you one story about poblem much similar to this.
In year 1999 or 2000 or 2001 there was a problem about two enclosed polylines, given lists of their endpoints in 3D. It was offered at Russian ACM ICPC finals (World semi-finals). The questions was if they can be split apart. Noone got AC with this problem, and best teams didn't even try to submit it. Some team got -26 with it, but I think they just tried luck with rand() during last minutes of the contest (outputs were YES/NO).
Then I thought of own method to project both polylines onto some plane and track one over another (write + or - if it goes above or under). Some off-the-wall plane like (pi, e, sin(17), 0) would eliminate any degenerate cases within test data. Then delete ++ or -- whenever they appear (the list is curcular). Resulting circular list of +-+-+-+- will tell the number of times the first line goes around the other. If it's empty, then they can be separated. Well, I didn't submit this anywhere, and it was just a guess of a possible algorithm.
One year ago I offered this problem for training of best Russian teams. Such trainings are held twice each year in my city. One of primary coaches (Nikolay Durov) took a look at my problem (actually not my at all) and said "you don't know how to solve it". Well, he is one of only two ACM ICPC Double World Champions (another one is his teammate Andrew Lopatin), and AFAIK he is also World Champion in math/physics/informatics as sole player. So, of course, I believed him that my algorithm is wrong. Meanwhile, knowing at 99.9999999(9)% probability that my algorithm is wrong, it was easier to find counter-example for it since I knew it exists. I found it. This counter-example showed that ++ or -- do not always eliminate each other.
Now about this thread. I don't think this problem is actually very different. And information given in the input is somewhat like my +- signs (goes over or under). So I doubt it has any solution. All you have to do is to guess some reasonable heuristics used by judge solution. Nothing more it. This problem isn't about correct algorithm, but only about extrapolating author's mind on whatever heuristics or invariant he used to "solve" it.
Also I wonder how are you going to apply knots theory here (steps 1/2/3) when you don't even know how many crossings and where and of which sign will appear when you connect line's endpoints. I didn't see in problem description that both endpoints rest outside knot projection.
Even if we assume this, the problem is gretely exponential. We need to apply step3 whenever we can until we don't face any new state. For such a problem it would be nice to have some upper limit for given number of intersections.
and moved on other directions.
