Ad
  • Default User Avatar

    @hobovsky

    Thanks for the suggestion. Its actually what I did and it helped me solve the problem. I read about the problem and the theory behind the solution, after looking at some different algorithms for that I wrote down one I particularly liked and after understanding how and why it worked I used it to solve the problem and was actually quite amazed at how inefficient I had been approaching the problem. My solution used to run at about 108. something ms on the basic tests, and the solution I submitted ran the same tests with a new one I made with 1 million cycles faster than that.
    Again, thanks for the suggestion and for future readers I really recommend reading up on this as it does make a lot of sense when it finally clicks

  • Custom User Avatar

    it seems you have more than one problem with your approach:

    • you use additional list to store visited nodes. While this is not that bad, this problem can be solved with O(1) additional memory, i.e. you do not need to store every visited node anywhere. You are right that you need to loop through all the nodes, but it does not mean that you need to remember every of them.
    • whats worse, you use a linear list as your container, and perform linear lookup on it. this is bad, and its the cause of your timeouts here. if you are going to use additional storage (which you don't have to), use something with more efficient lookup.
    • nodes indeed do not have any associated value, but its not necessary. reference equality is all whats needed.

    I suggest doing some more research (i.e. googling) and looking for some loop detection algorithms. you will definitely find something.

  • Default User Avatar

    C#

    Im stopping for now as obviously Im missing something. My tests pass but I get a time out at the actual attempt. I'm using a single linear loop to go through all of the nodes, adding them to a List and checking if the current node I am at is present in the list. If present, It means I have looped through all of them, so then I just return the count - the index of the current node.
    I guess it should have a simpler solution judging by some of the comments in the Discussion but Im stuck for now, will come back to it later. I dont really see how you can figure this out without looping through all the nodes, because you only have node.next, and nothing else to indicate what text or something this node has (Judging by the image, they should have some text in them), I tried using the node itself, text, Text, GetText, value, Value, but none seem to give me any values. I also tried using reflection to print out the properties and also got only .next.