Hometown Newspaper

Concepts Used

Sorting

Difficulty Level

Medium

Problem Statement (Simplified):

Print the Strings according to their priority and category. If string belongs to hometown, it will have a priority higher than other towns irrespective of their priority value. String belonging to the same category is printed according to its priority value. More the priority value more will be their priority. Priority values are distinct.

Test Case

Input:
1
3
News1 1 1
News2 2 0
News3 4 1

Output:
News3 
News1
News2

Explanation:
News3 and News1 are originated in the hometown so they will be printed first and News3 is more popular than News1 and then News2 will be printed.

See original problem statement here

Solving Approach :

1) As we know, if D is 1, i.e. new belongs to hometown they’ll have the highest priority.
2) So we’ll print news from hometown first then news from other towns.
3) News will be printed, in their priority order, news with priority value more will be printed first.
4) As we know all priority values are distinct, so we can save the index of news strings associated with priority value in a separate Index Array.
5) We learn programming languages online and create two separate two arrays to save priority values from hometown news and other towns.
6) When we read news from every line, we save the priority value in its respective array, depending on the value provided in D, where if D is 1, the news is from home town, else news is from another town.
7) We can sort news priority wise by sorting the arrays containing priorities of both towns, hence the news with the highest priority will be on the last index, and news with the least priority will be on the first index.
8) Hence we print news according to priority. We print news from hometown first and then from rest towns.

Example



Solutions

#include <stdio.h>

void merge(int arr[], int start, int mid, int end){
    int left[mid-start+1];
    int right[end-mid];
    for(int i=start; i<mid+1; i++){
        left[i-start] =  arr[i];
    }
    for(int i=mid+1; i<=end; i++){
        right[i-(mid+1)] = arr[i];
    }
    int leftIndex=0, rightIndex=0, arrIndex=start;
    for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
        if(left[leftIndex]<right[rightIndex]){
            arr[arrIndex] = left[leftIndex++];
        }
        else{
            arr[arrIndex] = right[rightIndex++];
        }
    }

    while(leftIndex<=mid-start){
        arr[arrIndex++] = left[leftIndex++];
    }

    while(rightIndex<end-mid){
        arr[arrIndex++] = right[rightIndex++];
    }

}

void mergeSort(int arr[], int start, int end){
    if(end==start)
        return;
    mergeSort(arr,start,(start+end)/2);
    mergeSort(arr,((start+end)/2)+1,end);
    merge(arr,start,(start+end)/2,end);
}

int main()
{
  int test;
  scanf("%d", &test);

  while(test--){

    int n;
    scanf("%d", &n);

    char news[n][99999];
    int popularityAway[99999];
    int popularityHome[99999];
    int indexing[999999] = {0};

    int home=0, away=0, temp;

    for(int i=0; i<n; i++){
      int val;
      scanf("%s%d%d", news[i],&temp,&val);
      if(val==1)
        popularityHome[home++] = temp;
      else
        popularityAway[away++] = temp;
      indexing[temp] = i;
    }

    if(away>0)
      mergeSort(popularityAway, 0, away-1);
    if(home>0)
      mergeSort(popularityHome, 0, home-1);

    if(home>0){
      for(int i=home-1 ;i>=0; i--)
        printf("%s\n",news[indexing[popularityHome[i]]]);
    }
    if(away>0){
      for(int i=away-1; i>=0; i--)
        printf("%s\n",news[indexing[popularityAway[i]]]);
    }
  }
}
#include <bits/stdc++.h>
using namespace std;

void merge(int arr[], int start, int mid, int end){
    int left[mid-start+1]={0};
    int right[end-mid]={0};
    for(int i=start; i<mid+1; i++){
        left[i-start] =  arr[i];
    }
    for(int i=mid+1; i<=end; i++){
        right[i-(mid+1)] = arr[i];
    }
    int leftIndex=0, rightIndex=0, arrIndex=start;
    for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
        if(left[leftIndex]<right[rightIndex]){
            arr[arrIndex] = left[leftIndex++];
        }
        else{
            arr[arrIndex] = right[rightIndex++];
        }
    }

    while(leftIndex<=mid-start){
        arr[arrIndex++] = left[leftIndex++];
    }

    while(rightIndex<end-mid){
        arr[arrIndex++] = right[rightIndex++];
    }

}

void mergeSort(int arr[], int start, int end){
    if(end==start)
        return;
    mergeSort(arr,start,(start+end)/2);
    mergeSort(arr,((start+end)/2)+1,end);
    merge(arr,start,(start+end)/2,end);
}

int main()
{
  int test;
  cin>>test;

  while(test--){

    int n;
    cin>>n; 

    char news[n][99999];
    int popularityAway[99999];
    int popularityHome[99999];
    int indexing[999999] = {0};

    int home=0, away=0, temp;

    for(int i=0; i<n; i++){
      int val;
      cin>>news[i]>>temp>>val;
      if(val==1)
        popularityHome[home++] = temp;
      else
        popularityAway[away++] = temp;
      indexing[temp] = i;
    }
    if(away>0)
      mergeSort(popularityAway, 0, away-1);
    if(home>0)
      mergeSort(popularityHome, 0, home-1);

    if(home>0){
      for(int i=home-1 ;i>=0; i--)
        cout<<news[indexing[popularityHome[i]]]<<endl;
    }
    if(away>0){
      for(int i=away-1; i>=0; i--)
        cout<<news[indexing[popularityAway[i]]]<<endl;
    }
  }
}
import java.util.*;
import java.io.*;

public class Main {
  static void merge(int arr[], int start, int mid, int end){
    int left[] = new int[mid-start+1];
    int right[] = new int[end-mid];
    for(int i=start; i<mid+1; i++){
        left[i-start] =  arr[i];
    }
    for(int i=mid+1; i<=end; i++){
        right[i-(mid+1)] = arr[i];
    }
    int leftIndex=0, rightIndex=0, arrIndex=start;
    for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
        if(left[leftIndex]<right[rightIndex]){
            arr[arrIndex] = left[leftIndex++];
        }
        else{
            arr[arrIndex] = right[rightIndex++];
        }
    }

    while(leftIndex<=mid-start){
        arr[arrIndex++] = left[leftIndex++];
    }

    while(rightIndex<end-mid){
        arr[arrIndex++] = right[rightIndex++];
    }

  }

  static void mergeSort(int arr[], int start, int end){
      if(end==start)
          return;
      mergeSort(arr,start,(start+end)/2);
      mergeSort(arr,((start+end)/2)+1,end);
      merge(arr,start,(start+end)/2,end);
  }

  public static void main(String args[]) throws IOException {

    Scanner sc = new Scanner(System.in);
    int test = sc.nextInt();

    while(test--!=0){

      int n = sc.nextInt();

      String news[] = new String[n];
      int popularityAway[] = new int[99999];
      int popularityHome[] = new int[99999];
      int indexing[] = new int[999999];

      int home=0, away=0;

      for(int i=0; i<n; i++){
        news[i] = sc.next();
        int temp = sc.nextInt(),val = sc.nextInt();
        if(val==1)
          popularityHome[home++] = temp;
        else
          popularityAway[away++] = temp;
        indexing[temp] = i;
      }

      if(away>0)
        mergeSort(popularityAway, 0, away-1);
      if(home>0)
        mergeSort(popularityHome, 0, home-1);

      if(home>0){
        for(int i=home-1 ;i>=0; i--)
          System.out.println(news[indexing[popularityHome[i]]]);
      }
      if(away>0){
        for(int i=away-1; i>=0; i--)
          System.out.println(news[indexing[popularityAway[i]]]);
      }
    }

  }
}

Space Complexity

O( max(n) ) space is taken to store indexes.

Previous post Minimum Dissatisfaction
Next post Minus Minus is Plus

Leave a Reply

Your email address will not be published. Required fields are marked *