Absolute Permutation
Absolute Permutation
massimo_biancal1 + 38 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 + 1 comment 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 + 4 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
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 !!
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 + 0 comments 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; }
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
SecondThread + 0 comments I found it humorous that basically this entire problem is 1indexed, and then I saw...
Test Case 0:
landonkoo0207 + 6 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.
SL170040869 + 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.
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.
ramsiddarth + 0 comments I don't understand the problem. Can some one explaing for the input test case 1 please?.
ccordero + 3 comments Pretty simple implementation in Python3
#!/bin/python3 for _ in range(int(input().strip())): n, k = [int(x) for x in input().strip().split(' ')] if k != 0 and n % k != 0: print(1) continue arr = [None] * (n+1) # initialize iterable for i in range(1,len(arr)): if arr[i] is None: arr[i] = i + k arr[i+k] = i print(' '.join([str(j) for j in arr[1:]]))
mark_verleg + 0 comments Ow I thought mine was fairly short, but you fill two elements per loop, that's smart.
parshu1990 + 1 comment Run time error in test case 12
manjunathb3103 + 0 comments if k != 0 and n % k != 0: print(1) Make it n % 2*k != 0
mohitkumar448 + 1 comment Python 3 
def absolutePermutation(n, k): a = list(i+1 for i in range(n)) i=0 if k==0: return(a) if n%2 != 0: return([1]) if n % (k*2) == 0: while(i<len(a)): for _ in range(k): a[i], a[i+k] = a[i+k], a[i] i+=1 i = i+k else: return([1]) return(a)
aliona_putilova + 0 comments Thank you for return([1])
Mandar_Inamdar + 0 comments My Simple Pythonic solution: complexity O(N) also no array is used. Make k equal parts of N. for alternate parts add or subtract k value for (1..N) and print.
for a0 in range(t): n,k = input().strip().split(' ') n,k = [int(n),int(k)] if k==0 or (n%k ==0 and (n/k) % 2 ==0) : if k==0 : print(*range(1,n+1)) else: cntr=0 for i in range (1 , int(n/k)+1): for j in range (1 , k+1): cntr +=1 if i%2 != 0: print(cntr+k, end=" ") else: print(cntrk, end=" ") print ("") else: print (1)
maowtm + 0 comments
Sort 196 Discussions, By:
Please Login in order to post a comment