massimo_biancal1 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 Thanks, that helped. (:
kent1ukr Thank You!! Thats the best test case to realize how it should work!
crackerplace Beautiful !
adk96r Thankyou! :)
anurag_vesangi Thanks,Helpful
feng12 [deleted]prat_degwekar still dont get it
feng12 [deleted]
DRedemption beauty !! this is
itsmedurgesh wow! this is beautiful.
uttariya_bandhu 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 hi bhai can you help me understanding this question
ZachPerkitny [deleted]
GabrielFilip Thank you! This example helped me to solve the problem.
cleverone Thanx a lot
rohitagr03 Thanks, this really helped a lot!!
Hitsa00 Thanks.enlighted me too,
MrAsimov thank you very much for this test case.
shu69bham 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 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 can you plz explain me in detail.
Litewhite Thanks! Beautiful sulotion lol
smileyrs 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 In permutation each number should appear only once. In Your output You are using '3' more than once.
Tandilashvili 3 and 4 appear more than once
lincolndu 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 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 can you please explain the logic.I didn't get the question well. Thanks in advance
thebick 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 Little flaw in your reasonning, 1 + k may accept 1 and 1 + 2*k as an image if 1 + 2*k < N.
vkokielov 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 Thanks man!
yashiagarwal1812 please explain must go down to [2, ,k]
ashishsinghrath1 explained it very well
vaibhavch9876 how did you reached upto the condition:: else if((n%(2*k))==0)
yashiagarwal1812 please tell how you came to know this test case ((n % (2*k)) == 0)
hmvaghasiya Thanks !!
KiddoK Beautiful :)
songzy12 Thanks!
amrithm98 Nailed it!! Thanks
jp30101995 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 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 Result after permutation should be SMALLEST. This is the point which u r missing.
shubhamj280 Genius!!!!!!
karthik_01 Thanks sir!!
akshaypandita201 yep it is!!!!!!!!!!
the_brogrammerr This one really helped me :) Thank you so much!!!
shashwatnavy123 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 = m-k 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 Thanks, really helpful!
Zyro9922 I don't feel so enlighted :/
duoduoxia 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 That Helped ,Thanks...
hariharakumar7 nice one helped me as well
roshni_koli Thank you. It was indeed enlightening :)
officialsoumalya this taste case is passing but still all the test cases are not passing
SecondThread I found it humorous that basically this entire problem is 1-indexed, and then I saw...
Test Case 0:
landonkoo0207 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 i-k. It always starts with i+k.
1.Put i+k to permutaion for k times
2.Switch to i-k 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(i-k) if i % k == 0: if add: add = False else: add = True print (*perm)
khtmmm Such a clever soulution! I implemented in Java passed all cases. Thanks
landonkoo0207 Glad I can help :)
akhilhello if (n / k) % 2 is not ZERO, print -1 (as this must be zero to be abolute permutation), how did you know this?
Kevinagin 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 thanks bro,u gave a clear sight of the solution.
niteshbegin kindly explain about k-i and k+i
abhinavtembulk 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 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 can you explain the last return statement plss..I dont understand it.
tung_nn83 [deleted]
chiragshah9696 Awesome solution!
1damketthuc Thanks a lot!
SidSam 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 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 -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 So... could we say that n%2k==0? ;>
h736478610 helpful！
wmosanttos n mod 2k = 0 and 2k <= n
amitkvikram 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_ how did you get those condition ?? can u explain..
15131A05K8_ how did u get those condtions?? can u explain??
bgreenfield 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 how did u derive the first conclusion?
pearsonn877 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 Here's an un-clever 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 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=i-k; 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 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 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 thanks!! This helped me For the ith number in the permutation, we can choose (-K + i), (K + i), or neither.
ramsiddarth I don't understand the problem. Can some one explaing for the input test case 1 please?.
ccordero 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 Ow I thought mine was fairly short, but you fill two elements per loop, that's smart.
parshu1990 Run time error in test case 12
manjunathb3103 if k != 0 and n % k != 0: print(-1) Make it n % 2*k != 0
mohitkumar448 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 Thank you for return([-1])
Mandar_Inamdar 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(cntr-k, end=" ") print ("") else: print (-1)
Sort 196 Discussions, By:
Please Login in order to post a comment