Positive Prefixes Codechef December long challenge solution | Codechef December long challeng editorial

Problem Statement -

this Problem Positive prefix taken from CodeChef December long challenge.Let's read Problem statement.

You are given two positive integers N$N$ and K$K$, where K≤N$K\le N$. Find a sequence A1,A2,…,AN$A_1,A_2,\dots ,A_N$ such that:

• for each valid i$i$, Ai$A_i$ is either i$i$ or −i$-i$
• there are exactly K$K$ values of i$i$ such that 1≤i≤N$1\le i\le N$ and A1+A2+…+Ai>0$A_1+A_2+\dots +A_i>0$

If there are multiple solutions, you may print any one of them. It can be proved that at least one solution always exists.

Input

• The first line of the input contains a single integer T$T$ denoting the number of test cases. The description of T$T$ test cases follows.
• The first and only line of each test case contains two space-separated integers N$N$ and K$K$.

Output

For each test case, print a single line containing N$N$ space-separated integers A1,A2,…,AN$A_1,A_2,\dots ,A_N$.

Constraints

• 1≤T≤1,000$1\le T\le 1,000$
• 1≤K≤N≤1,000$1\le K\le N\le 1,000$

Subtasks

Subtask #1 (10 points): N≤10$N\le 10$

Subtask #2 (90 points): original constraints

Example Input

1
3 3

Example Output

1 2 3

Solution-

Hint- learn Prefix array to solve this question.

This question is totally observation-based.You should  good observer to solve  this problem.

Solution since there can be multiple solution of this problem one of them is to print alternate +i and -i.

in my case what i am doing 

I have created an output array in which i am storing +i and -i alternatively.

then I iterate over the array and I calculate the prefix array.

Then I calculated total positive and negative number store in the output array.And i build the following logic 

if(k<=positive){

            int diff=positive-k;

            for(int i=n;i>0&&diff>0;i--){

                if(prefix[i]>0){

                    output[i]=-output[i];

                    diff--;

                }

                

            }

        }

        else{

           int diff=k-positive;

             for(int i=n;i>0&&diff>0;i--){

                if(prefix[i]<0){

                    output[i]=-output[i];

                    diff--;

                }

                

            }

        }

Here is my entire code.

Join Telegram Channel for solution. 

link -https://t.me/competitiveProgrammingDiscussion