2 years ago   Computer Science

Implement merge sort for a two-dimensional array. In case of odd dimension, the first division contains more number of elements than the second one. The complete execution of merge sort arranges the elements in increasing order either moving row-wise or column-wise.

For example, let there be a 4×44×4 two dimensional array. The complete process to be implemented is illustrated in Fig. 1. Similarly, Fig. 2 demonstrates the scenario for a 3×33×3 two dimensional array. One has to keep on dividing till a single element is remaining. During merging, first the row elements get sorted in increasing order followed by sorting of elements lying in the same column.

Mirror Center
Fig.1 - 2D Mergesort on a 4×44×4 two dimensional array.
Mirror Center
Fig.2 - 2D Mergesort on a 3×33×3 two dimensional array.

Input:

  • Line 1 contains two space separated integers MM and NN, i.e. the size of two dimensional array.
  • Line 2 contains MNM∗N unique integers separated by space. These are the contents of a two dimensional array in row-major order.

Output:

  • Line 1 is space separated MNM∗N integers sequence. These are the final contents of a two dimensional array in row-major order.

2 years ago

Imagine a pandemic situation that happened in the middle of a session and results in an immediate closure of offline education. In such a scenario universities have to come up with some solution so as to finish with the evaluation process of the current semester. They decided to end the semester not by giving grades based on marks, instead proposed to just declare if a student has passed the subject or not.

The process they adopted is as detailed here. As its mid of the running semester each subject has already finished with a few of the sessional components comprising of some marks out of the maximum marks in that subject. In addition, the maximum marks that can be scored in a subject may vary from one subject to another. Therefore, each subject has to decide the minimum marks, say MINMARKSMINMARKS, which should be greater than the total marks of the sessional components that are completed by now in offline mode for the subject. Every student has to score at least MINMARKSMINMARKS to pass that subject. Once decided, for each subject, inform students about the MINMARKSMINMARKS and also declare the marks obtained in the sessional finished so far.

One assignment per subject is given to students so that they can score the remaining marks. The pattern of the assignment remains same for all the subjects. An assignment consists of a set of questions and students are free to attempt as many questions as they want, i.e. all questions are not mandatory. Each assignment question has a maximum score and some number of sub-parts. The difficulty level of a question is based on the following criteria:

  • More is the number of sub-parts easier is the question irrespective of the maximum score of that question.
  • In case two or more questions have same number of sub-parts then difficulty level is decided via ratio of maximum score and number of sub-parts. Lesser is the ratio easier is the question.

Knowing the assignment pattern and the fact that one just has to score MINMARKSMINMARKS, students decided to score only the remaining marks by selecting the easiest assignment questions. You have to help these students in this selection by proposing the strategy to be followed.

Input:

  • Line 1 contains three space separated integers MINMARKSMINMARKSSS, and NN, i.e. minimum marks to pass the subject, total number of students, and total number of assignment questions, respectively.
  • Line 2 contains SS integers separated by space. These are the sessional marks of SS students.
  • Following NN lines contain space separated 2 integers, representing the maximum score and the number of sub-parts in a question.

Output:

  • There will be SS lines in the output. The first number in each line, say xx, represents the count of questions a student has to attempt to score at least MINMARKSMINMARKS. It is followed by space separated xx integers, sorted in increasing order, representing the question numbers to be attempted.
Karan Bhardwaj

2 years ago

Yash Rocky

3 years ago

© 2024 Zoylu. All Rights Reserved.