Absolute Permutation
Absolute Permutation
massimo_biancal1 + 45 comments A test case enlighted me
Input:1 100 2
Output:
3 4 1 2 7 8 5 6 11 12 9 10 15 16 13 14 19 20 17 18 23 24 21 22 27 28 25 26 31 32 29 30 35 36 33 34 39 40 37 38 43 44 41 42 47 48 45 46 51 52 49 50 55 56 53 54 59 60 57 58 63 64 61 62 67 68 65 66 71 72 69 70 75 76 73 74 79 80 77 78 83 84 81 82 87 88 85 86 91 92 89 90 95 96 93 94 99 100 97 98
EpsilonAlpha + 0 comments Thanks, that helped. (:
kent1ukr + 0 comments Thank You!! Thats the best test case to realize how it should work!
crackerplace + 0 comments Beautiful !
adk96r + 0 comments Thankyou! :)
anurag_vesangi + 0 comments Thanks,Helpful
feng12 + 1 comment [deleted]prat_degwekar + 1 comment still dont get it
feng12 + 0 comments [deleted]
DRedemption + 0 comments beauty !! this is
itsmedurgesh + 0 comments wow! this is beautiful.
uttariya_bandhu + 1 comment This was brilliant! wouldn't have understood the pattern without this testcase.I Would really like to know the process by which you found this pattern.
shubhambhatt8055 + 0 comments hi bhai can you help me understanding this question
ZachPerkitny + 0 comments [deleted]GabrielFilip + 0 comments Thank you! This example helped me to solve the problem.
cleverone + 0 comments Thanx a lot
rohitagr03 + 0 comments Thanks, this really helped a lot!!
Hitsa00 + 0 comments Thanks.enlighted me too,
MrAsimov + 0 comments thank you very much for this test case.
shu69bham + 0 comments brilliant \m/
I was using naive recursive approach and was getting timout after test case#3,but then saw the series in your test case.
Thank You :)
brooom + 0 comments u r doing wrong and hindering growth of others. please dont post such things . people need hint not whole answers and if they are searching for solutions without giving much time then definitely it is not going to help
sdzakir99 + 0 comments can you plz explain me in detail.
Litewhite + 0 comments Thanks! Beautiful sulotion lol
smileyrs + 1 comment dont understand why this cant be the answer
3 4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98
krzys716 + 1 comment In permutation each number should appear only once. In Your output You are using '3' more than once.
Tandilashvili + 0 comments 3 and 4 appear more than once
lincolndu + 2 comments PHP Solution
<?php $handle = fopen ("php://stdin","r"); fscanf($handle,"%d",$t); for($a0 = 0; $a0 < $t; $a0++){ fscanf($handle,"%d %d",$n,$k); $check=($k != 0) ? fmod($n,$k) == 0 && fmod($n/$k,2) ==0: true; if(!$check){ echo "1\n"; }else{ $arr=[]; for($i=1;$i<=$n;$i++){ if(empty($arr[$i])){ $arr[$i]=$i+$k; $arr[$i+$k]=$i; } } ksort($arr); foreach($arr as $k => $val){ echo $val . ' '; } echo "\n"; } }
lokeshwaran100 + 4 comments C++ Solution:
int main(){ int t; cin >> t; for(int a0 = 0; a0 < t; a0++){ int n; int k; cin >> n >> k; int temp = k; if(k == 0){ for(int i = 1; i <= n; i++){ cout << i << " "; } }else if((n % (2*k)) == 0){ for(int i = 1; i <= n; i++){ cout << i + temp << " "; if(i % k == 0){ temp = temp * 1; } } }else{ cout << 1; } cout << endl; } return 0; }
Drogo + 1 comment can you please explain the logic.I didn't get the question well. Thanks in advance
thebick + 6 comments Logic of the question: how can I permute [1,...,n] so that each number is exactly +k from its original position?
If k == 0, then just leave everything alone.
If k > 0, then obviously 1 goes to 1+k; so ask: "What must go to 1?" Since there is no smaller # to go up to 1, the answer is 1+k, which can go down to 1.
This begs the question: what about numbers between 1 and 1+k, i.e., [2,...,k]? They must go up to [2+k,...,k+k] (note k+k == 2*k), which in turn must go down to [2,...,k].
This results in the crux: n must be a multiple of 2*k, so ((n % (2*k)) == 0). Then you just take it in 2*k chunks.
If those test fail, then you can't do it.
Now just put the algorithm into source code.
hamza_keurti + 1 comment Little flaw in your reasonning, 1 + k may accept 1 and 1 + 2*k as an image if 1 + 2*k < N.
vkokielov + 0 comments It's not a flaw. The constraint is the beginning. Every x has to go somewhere. 1 can go to 1  k or 1 + k. Since 1  k is not a real image, only 1 + k is left. The problem folds very quickly after that, leaving only one of two possibilities for each number.
When I have some time I will try to solve this problem in a general way by applying constraint logic.
miguel_hughes + 0 comments Thanks man!
yashiagarwal1812 + 0 comments please explain must go down to [2, ,k]
ashishsinghrath1 + 0 comments explained it very well
ash_winpr25 + 0 comments [deleted]abhiaps12345 + 0 comments good logic
vaibhavch9876 + 0 comments how did you reached upto the condition:: else if((n%(2*k))==0)
yashiagarwal1812 + 0 comments please tell how you came to know this test case ((n % (2*k)) == 0)
hmvaghasiya + 0 comments Thanks !!
mohamedelsayed0 + 0 comments nice solution
KiddoK + 0 comments Beautiful :)
songzy12 + 0 comments Thanks!
amrithm98 + 0 comments Nailed it!! Thanks
jp30101995 + 2 comments For the same test case I am geting this output :
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 97 98
Tell me if there is any error in my understanding. Thanks.
thebick + 0 comments You have 97 and 98 twice, and omit 1 and 2.
If the difference value is > 0, you must think swapped positions  and whether that will work.
zakiralig184 + 0 comments Result after permutation should be SMALLEST. This is the point which u r missing.
shubhamj280 + 0 comments Genius!!!!!!
karthik_01 + 0 comments Thanks sir!!
akshaypandita201 + 0 comments yep it is!!!!!!!!!!
the_brogrammerr + 0 comments This one really helped me :) Thank you so much!!!
shashwatnavy123 + 0 comments I am getting this output but still all my test cases are not able to pass for eg. n = 92 k = 14 My goes like this in python 3
cases = int(input()) for i in range(cases): n,k = map(int,input().split()) res = str() arr =[] for j in range(n+1): if (j == 0): arr.append(0) else : arr.append(j) check = [0] for m in range(1,len(arr)): add = m + k sub = mk if sub > 0 and sub not in check: check.append(sub) continue elif add < n+1 : check.append(add) continue for j in range(1,len(check)): if abs(check[j]j)==k : res = res + str(check[j]) + " " else : res = str(1) break print(res.rstrip())
Your help will be highly oblidged
mayshmaz + 0 comments Thanks, really helpful!
Zyro9922 + 0 comments I don't feel so enlighted :/
duoduoxia + 1 comment static int[] absolutePermutation(int n, int k) { int[] per = new int[n]; int d = 1; for (int i = 0, j = 0; i < n; i++, j++) { if (j == k) { d *= 1; j = 0; } int value = i + 1 + k * d; if (value < 1  value > n) return new int[]{1}; per[i] = value; } return per; }
arsen_budumyan + 0 comments Thank you, was very helpful.
sudo_s + 0 comments That Helped ,Thanks...
hariharakumar7 + 0 comments nice one helped me as well
roshni_koli + 0 comments Thank you. It was indeed enlightening :)
officialsoumalya + 0 comments this taste case is passing but still all the test cases are not passing
yashtazor + 0 comments Very helpful. Thank you very much.
wagh1sushil + 0 comments I think this problem has 73% solving rate because of your comment.Thanks man your explanation really helped.Keep up the good work.
shashank_mehul02 + 0 comments thanks a lot,helped me correct some minor errors.
deniska_roms + 0 comments Thank you!!
koceto1973 + 0 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 (nk) is reached ( array out of right boundary). Range is [0,min(k,nk)).
Then in anology, starting from index n1, we do only k, until earlier of two options happen: nk is reached ( below that +k is also possible) or k is reached ( below that array out of left boundary). Range is [max(k,nk),n1]. 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...n1, 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 ... :)))
kris_tobiasson + 0 comments Here's my straightforward approach in JS:
let results = []; if(k === 0){ for(let i = 0; i < n; i++){ results.push(i+1); } return results; } if((n/k)%2 === 0){ let j = 1+k; while(results.length < n){ for(let i = 0; i < k; i++){ results.push(results.length+j); } j = (j === 1+k) ? 1k : 1+k; } return results; } return [1];
patiltanmay12 + 0 comments Thanks, that helped. (:
SecondThread + 0 comments I found it humorous that basically this entire problem is 1indexed, and then I saw...
Test Case 0:
landonkoo0207 + 10 comments There are many clever solutions in the discussion, but they aren't exactly straightfoward to me, so I've worked out myself.
First, there are two exception cases, like below:
1.k == 0: print all the numbers from 1 to N
2.if (n / k) % 2 is not ZERO, print 1 (as this must be zero to be abolute permutation)
Otherwise, follow the pattern below:
if we go from 1 to N (i),
Permutation is either i+k or ik. It always starts with i+k.
1.Put i+k to permutaion for k times
2.Switch to ik for k times
 repeat 1 & 2 until the end.
my python3 solution is below:
t = int(input().strip()) for a0 in range(t): n,k = map(int, input().split(" ")) if k == 0: print (*list(range(1, n+1))) elif (n/k) % 2 != 0: print ("1") else: add = True perm = [] for i in range(1, n+1): if add: perm.append(i+k) else: perm.append(ik) if i % k == 0: if add: add = False else: add = True print (*perm)
khtmmm + 1 comment Such a clever soulution! I implemented in Java passed all cases. Thanks
landonkoo0207 + 1 comment Glad I can help :)
akhilhello + 1 comment if (n / k) % 2 is not ZERO, print 1 (as this must be zero to be abolute permutation), how did you know this?
Kevinagin + 1 comment Another way to look at it is if n % (2*k) is not ZERO, print 1. That's because you'll need to "shuffle" groups of 2*k elements.
For example, when n = 8 and k = 2, you'll start off with [1,2,3,4,5,6,7,8] and shuffle groups of 4 like this:
1 and 3
2 and 4

5 and 7
6 and 8
...
The approach works in this case because 8 is divisible by 4. Or more generally, it will work when n is divisble by 2*k.
Thota__Bhargav + 0 comments thanks bro,u gave a clear sight of the solution.
niteshbegin + 1 comment kindly explain about ki and k+i
abhinavtembulk + 0 comments on removing absolute modulus from eqn .you get:
pos[i]  i =k if pos[i] > i
or i  pos[i] =k if pos[i] < i
which is otherwise: pos[i]i=k or k if you ignore the conditions.
r2munjal + 1 comment Nice! I was thinking, in the case where a permutation exists, since we always add/subtract k, the only thing you have to determine is the sign, so we can do:
def absolutePermutation(n, k): if k == 0: return [i+1 for i in range(n)] elif n % (2*k) != 0 or 2*k > n: return [1] return [(i+1)+(1 if (i//k)%2==0 else 1)*k for i in range(n)]
srivaishnavi_ga1 + 1 comment can you explain the last return statement plss..I dont understand it.
tung_nn83 + 0 comments [deleted]
chiragshah9696 + 0 comments Awesome solution!
1damketthuc + 0 comments Thanks a lot!
SidSam + 0 comments Why doesn't this solution work in Python2? Only 4 out of the 13 test cases pass. As far as I know, the only difference in this code for the two versions of Python would be how division works, but that doesn't ultimately matter since we're taking the modulo of the answer.
prasanshasureka + 0 comments [deleted]krishrahul98 + 0 comments I implemented without any condition but it still works
def absolutePermutation(n, k): res = list() for i in range(1,n+1): if 1<=i+k<=n: res.append(i+k) if k!=0 and i%k==0: k*=1 if len(res)!=n: return [1] return res
abhi_telukunta + 0 comments [deleted]abhi_telukunta + 0 comments Wow!Awesome logic
Zettahuat + 7 comments Here are 3 things you may want to know if you are stuck:
If n is an even number (n%k == 0) lets you know if there is a valid permutation or you should just print 1
If k=0 just print 1... n
If n is an odd number and it also is greater than 0, print 1
pocomaxa + 1 comment If n is an odd number and it also is greater than 0, print 1
To go even further, (n/k) should also be even, provided that n%k==0.
marcelj + 1 comment So... could we say that n%2k==0? ;>
h736478610 + 0 comments helpful！
wmosanttos + 0 comments n mod 2k = 0 and 2k <= n
amitkvikram + 0 comments I did the same thing. But I want to know how did you approach to this solution. I did by looking at patterns and then thinkin for hours.
15131A05K8_ + 0 comments how did you get those condition ?? can u explain..
15131A05K8_ + 1 comment how did u get those condtions?? can u explain??
bgreenfield + 0 comments if order for i  k to be at least 1 i needs be bigger then k. but if i = k you cant subtract k you need to add it and get k + k this must be <= n. in order for the permutation to be the mowest you should subtract k at the bery first chance. but the first k you need to add or go negative. this leasts to a pattern of add then subtract that repeats with a period of 2k
anonymous1998 + 0 comments how did u derive the first conclusion?
pearsonn877 + 0 comments Odd that there are so many upvotes for this comment that is incorrect. When n=6 and k=2 there is still no valid permutation even though it passes the first condition. There are other comments that suggest the right answer, that is (n % 2k == 0).
RocketshipToastr + 3 comments Here's an unclever solution. It's still linear time but comes at the cost of an extra linear amount of overhead.
The gist is that we're going to be constructing our permutation one number at a time.
For the ith number in the permutation, we can choose (K + i), (K + i), or neither. The value we choose has to be between 1 and N, as well as not already used in our permutation. Moreover, we should choose (K + i) over (K + i) if both work*. If we ever encounter an iteration where neither choice is possible, we can stop as no such permutation is possible. If we can choose a number in each iteration, we'll end up with the required permutation.
*We should choose (K + i) over (K + i) because we won't be seeing this value C = (K + i) ever again in the coming iterations. Since K is given to be positive, (K + i) <= (K + i). As we look at the choices for future numbers in the permutation, i increases. In turn, (K + i) and (K + i) will increase further and further away from C. So if we don't choose C = (K + i), our "permutation" will be missing that value and won't actually be a permutation of the correct set of 1 to N.
If you think about it, this means we don't have to worry about computing the lexicographically smallest permutation. There's only ever one correct choice to be made at each iteration.
DattuGaade + 1 comment I also implemented in the same way. Here is my solution in java which is O(n).
import java.io.; import java.util.; import java.text.; import java.math.; import java.util.regex.*;
public class Solution {
public static void main(String[] args) { Scanner in = new Scanner(System.in); int t = in.nextInt(); for(int a0 = 0; a0 < t; a0++){ int n = in.nextInt(); int k = in.nextInt(); TreeMap<Integer,Integer> map=new TreeMap<>(); for(int i=1;i<=n;i++){ boolean flag=false; int pos=ik; if(pos>=1 && pos<=n && map.get(pos)==null){ map.put(pos,i); flag=true; } else{ pos=i+k; if(pos>=1 && pos<=n && map.get(pos)==null){ map.put(pos,i); flag=true; } } if(!flag) break; } if(map.size()!=n){ System.out.println("1"); } else{ for(int val :map.values()) System.out.print(val+" "); System.out.println(); } } }
}
tikhomirovpa + 0 comments Unfortunately, your solution is not clear O(n). In your solution you use TreeMap. Complexity of insertion into a tree map is O(logn) (get is O(logn) too). So algorithm complexity is O(nlogn), because on each number your invokes get from and put into a tree. You can change data structure to array, for instance.
mujeeb68022 + 0 comments I am implementing same approach but it gives TLE
import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); int t = in.nextInt(); for(int a0 = 0; a0 < t; a0++){ int n = in.nextInt(); int k = in.nextInt(); boolean flag = false; boolean[] b = new boolean[n+1]; String ans = ""; for(int i = 1; i <= n; i++){ int x = i + k; int y = i  k; if(y > 0 && y <= n && b[y] == false){ ans += y + " "; b[y] = true; }else if(x > 0 && x <= n && b[x] == false){ ans += x + " "; b[x] = true; }else{ flag = true; break; } } if(!flag){ System.out.println(ans); }else{ System.out.println(1); } } } }
karthik_01 + 0 comments thanks!! This helped me For the ith number in the permutation, we can choose (K + i), (K + i), or neither.
Sort 259 Discussions, By:
Please Login in order to post a comment