When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

Profesora's blog

By Profesora, history, 7 years ago, In English

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 !

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

| Write comment?
»
7 years ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

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