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}+\cdots +{�}_{{�}_{�}}$), 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

• $1\le �\le 10000$
• $1\le �\le 200000$
• $1\le �\le 200000$
• $1\le {�}_{�}\le 100000$
• $1\le {�}_{�}\le {�}_{�}\le �$
• The sum of $�$ over all test cases won't exceed $2\cdot 10^5$
• The sum of $�$ over all test cases won't exceed $2\cdot 10^5$

The solution will be updated Soon :

Chef ODD

Problem

You want to partition the set $�=\{1,2,\dots ,�\}$ into $�$ sets ${�}_1,{�}_2,\dots ,{�}_{�}$, such that $\mathrm{\mid }{�}_{�}\mathrm{\mid }\ge 2$, and the sum of elements in each ${�}_{�}$ is odd.

Is it possible to do so?

Note 1: Partitioning the set $�=\{1,2,\dots ,�\}$ into $�$ sets ${�}_1,{�}_2,\dots ,{�}_{�}$ means that every element of $�$ should be in exactly one of the sets ${�}_1,{�}_2,\dots ,{�}_{�}$, and ${�}_{�}\subseteq �$, for all $1\le �\le �$.

Note 2: $\mathrm{\mid }�\mathrm{\mid }$ 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 $�$.