Thanks, that helped. (:

Thank You!! Thats the best test case to realize how it should work!

Beautiful !

Thankyou! :)

Thanks,Helpful

beauty !! this is

wow! this is beautiful.

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.

Thank you! This example helped me to solve the problem.

Thanx a lot

Thanks, this really helped a lot!!

Thanks.enlighted me too,

thank you very much for this test case.

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 :)

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

can you plz explain me in detail.

Thanks! Beautiful sulotion lol

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

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";
    }
    
    
}

excellent

Beautiful :)

Thanks!

Nailed it!! Thanks

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.

Genius!!!!!!

Thanks sir!!

yep it is!!!!!!!!!!

This one really helped me :) Thank you so much!!!

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

Thanks, really helpful!

I don't feel so enlighted :/

That Helped ,Thanks...

nice one helped me as well

Thank you. It was indeed enlightening :)

this taste case is passing but still all the test cases are not passing

Very helpful. Thank you very much.

I think this problem has 73% solving rate because of your comment.Thanks man your explanation really helped.Keep up the good work.

thanks a lot,helped me correct some minor errors.

Thank you!!

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 ... :)))

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) ? 1-k : 1+k;
        }
        return results;
    }
    return [-1];

Thanks, that helped. (:

Such a clever soulution! I implemented in Java passed all cases. Thanks

kindly explain about k-i and k+i

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)]

Awesome solution!

Thanks a lot!

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.

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

Wow!Awesome logic

-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.

n mod 2k = 0 and 2k <= n

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.

how did you get those condition ?? can u explain..

how did u get those condtions?? can u explain??

how did u derive the first conclusion?

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).

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();
        }
    }
}

}

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);
            }
        }
    }
}

thanks!! This helped me For the ith number in the permutation, we can choose (-K + i), (K + i), or neither.