Chi's blog

By Chi, history, 5 years ago, In English

It's the same knight's tour problem (since the problem is in Vietnamese i wont put a link to the original one):

We have a chessboard of size a*a, the knight's coordinate is x, y. We have to find the longest path of the knight (the maximum number of squares the knight can go through), without having the knight going through a same square twice. Note that it does not have to be a close tour. I used the recursion method (i do considered breaking the operation when there exist a path that covers all a*a squares, too) and finds out that it only works well for a <= 50 (however, occasionally is passes the time limit).

But the limit is fairly larger (a <= 500), which — of course, got me 3 TLEs (here)

So instead i just tried printing a*a, and the 3 tests that i got TLE verdict before now return AC, but its wrong for the other 7 tests. (here)

So lastly i tried this

if(a>50)
{
    cout<<a*a;
    return 0;
}

and it got all AC for the 3 TLE tests but WA for 2 of the initially right ones (here)

Here's the code of the submission that got 70 points

Appreciate all helps.

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

:)

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

    Im here for the optimal solution, not to simply get an AC...

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