Блог пользователя Profesora

Автор Profesora, история, 7 лет назад, По-английски

Hello, Problem:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=646&page=show_problem&problem=1401 Code:https://ideone.com/YKNCzG Time complexity For the previous Code IS O(n!) n<=26 which gives me TLE every time i submit it it's seems to be madness to write such a backtracking code to solve this problem with such a big complexity,but sadly i don't know what should i do ! So would you please Help me !

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
7 лет назад, # |
Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

You need to actually generate the answer adding letter by letter.

  • Consider the length of the string is N, and you go adding letter one by one, from the left. When you're adding the pth letter (counting from 1), for each position you add current letter (there are p such positions), it will contain permutations. You need to add the current letter to position of the current string and perform the assignment . Be careful with overflow though by checking if that multiplication will exceed the current value of K first.

It can be kind of hard to understand just by reading, so I'll leave the code.

C++ Code