Starters 91 Solution Codechef | Maximum Sum Permutation

 Maximum Permutation Sum

Problem

You are given an array  of size . The array will be used to perform  queries, where each query is comprised of a pair of integers, denoted by  and .

Before the queries are executed, you are allowed to rearrange the elements in array  as desired.

Next, an integer variable  is initialized to 0. For each of the -th queries, calculate the sum of elements from  through  inclusive (i.e. ++1++), and add this sum to .

The objective of this problem is to find an arrangement of array  that maximizes the final value of  after all  queries have been processed.

If there are multiple possible arrangements of  which achieve this maximum value, you can output any.

Input Format

  • The first line of input will contain a single integer , denoting the number of test cases.
  • Each test case consists of multiple lines of input.
    • The first line of each test case contains two space-separated integers  and  — the length of array and number of queries, respectively.
    • The next line contains  space-separated integers denoting the elements of the array.
    • The next  lines describe the queries. The -th of these  lines contains two space-separated integers  and , describing the range for the -th query.

Output Format

For each test case, output on a new line the maximum possible value of . And in the next line, output the rearranged array , which achieves that maximum possible value.

Constraints

  • 110000
  • 1200000
  • 1200000
  • 1100000
  • 1
  • The sum of  over all test cases won't exceed 2105
  • The sum of  over all test cases won't exceed 2105




The solution will be updated Soon :


Chef ODD

Problem

You want to partition the set ={1,2,,} into  sets 1,2,,, such that 2, and the sum of elements in each  is odd.

Is it possible to do so?

Note 1: Partitioning the set ={1,2,,} into  sets 1,2,, means that every element of  should be in exactly one of the sets 1,2,,, and , for all 1.

Note 2:  denotes the number of elements in the set .

Input Format

  • The first line of input will contain a single integer , denoting the number of test cases.
  • The first line and only line of each test case contains two space-separated integers,  and .







Post a Comment

0 Comments