We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Anyway, even without it, problem is solvable in O(n).
First we leave the idea of perms generation by toggling two options for each index :)
Starting from index 0, we do only +k, until earlier of two options happen: k is reached ( -k also possible) or (n-k) is reached ( array out of right boundary). Range is [0,min(k,n-k)).
Then in anology, starting from index n-1, we do only -k, until earlier of two options happen: n-k is reached ( below that +k is also possible) or k is reached ( below that array out of left boundary). Range is [max(k,n-k),n-1]. Doing this iteration we already check for used indices, as both ranges may cross depending on n and k.
Here middle part is left eventually, so we iterate over it, taking the range remaining after both above. For each index we check both possibilities against used indices and where one option is left, we use it and update used indices progressively. Where 2 options remain I mapped both by their index, so I can iterate the map after this mid section is finished ( more used indices eventually).
Here we go, after having first complete iteration over the whole range of indices 0...n-1, I iterated over the map with remaining dual posibilities to solve them checking against used indices. Guess what - it did not do the job, meaining some of them are not stright forward.
Might be some looping over the map (while(){} ) would drain it over? ...
No it also did not, still few of them remain dual optioned.
So ... I remembered what was written above - lexicographically smallest absolute permutation ... then it was time to do it the greedy way,
I iterated over the map choosing the lower option for each index ( while still updating the used indices and checking for cancelled second option ). That finally matched all test cases :)
P.s. I had a problem debugging my code - tried to pay 5 hackos and use the test cases input/output, but the browser window had it's slider fixed down, so I could not lift it up and get the test case input. Same happend both with Chrome and Firefox. Any hint how to overcome this issue? Or to get my 5 hackos back ... :)))
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Absolute Permutation
You are viewing a single comment's thread. Return to all comments →
This observation is very wise, respect for that!
Anyway, even without it, problem is solvable in O(n). First we leave the idea of perms generation by toggling two options for each index :)
Starting from index 0, we do only +k, until earlier of two options happen: k is reached ( -k also possible) or (n-k) is reached ( array out of right boundary). Range is [0,min(k,n-k)).
Then in anology, starting from index n-1, we do only -k, until earlier of two options happen: n-k is reached ( below that +k is also possible) or k is reached ( below that array out of left boundary). Range is [max(k,n-k),n-1]. Doing this iteration we already check for used indices, as both ranges may cross depending on n and k.
Here middle part is left eventually, so we iterate over it, taking the range remaining after both above. For each index we check both possibilities against used indices and where one option is left, we use it and update used indices progressively. Where 2 options remain I mapped both by their index, so I can iterate the map after this mid section is finished ( more used indices eventually).
Here we go, after having first complete iteration over the whole range of indices 0...n-1, I iterated over the map with remaining dual posibilities to solve them checking against used indices. Guess what - it did not do the job, meaining some of them are not stright forward. Might be some looping over the map (while(){} ) would drain it over? ... No it also did not, still few of them remain dual optioned.
So ... I remembered what was written above - lexicographically smallest absolute permutation ... then it was time to do it the greedy way, I iterated over the map choosing the lower option for each index ( while still updating the used indices and checking for cancelled second option ). That finally matched all test cases :)
P.s. I had a problem debugging my code - tried to pay 5 hackos and use the test cases input/output, but the browser window had it's slider fixed down, so I could not lift it up and get the test case input. Same happend both with Chrome and Firefox. Any hint how to overcome this issue? Or to get my 5 hackos back ... :)))