-->

12/5/20

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 and K, where KN. Find a sequence A1,A2,,AN such that:

  • for each valid iAi is either i or i
  • there are exactly K values of i such that 1iN and A1+A2++Ai>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 denoting the number of test cases. The description of T test cases follows.
  • The first and only line of each test case contains two space-separated integers N and K.

Output

For each test case, print a single line containing N space-separated integers A1,A2,,AN.

Constraints

  • 1T1,000
  • 1KN1,000

Subtasks

Subtask #1 (10 points): N10

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. 


Advertiser

all right reserved @technicalkeeda.in. Powered by Blogger.