tom's blog

By tom, history, 8 years ago, In English

Hello Codeforces community,

Here is a problem: http://www.spoj.com/problems/SOLVING/

How would you solve it? I don't want to skew your view, so I just leave the question without mentioning my (apparently too slow) solution.

Thanks, tom

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +12 Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Did you try using A-Star algorithm? I think search space is too big even for this algorithm but you can give it a try. Since optimal solution is not required you may use non-consistent heuristic to speed up the search.

  • »
    »
    8 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Yes. My algorithm looks as follows:

    for every tile i from 1 to n*n-1
      go to tile i
      "bring" tile i near (manhattan distance <= 2) to the place it should be at
      run A* to put it there
    

    My heuristic is simple sum of manhattan distances between current point and destination point for tiles <= i.

    It works well except two last rows. Sometimes it takes a lot of time to finish them.

»
8 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

My bad XDDDD, ignore, its stupid

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Look at the constraints, board can be up to 10x10