You are not logged in. Please login at www.codechef.com to post your questions!

×

MRGSRT - EDITORIAL

Difficulty:Medium

Pre-requisites: Divide and conquer

Problem link:

Contest problem link

Practice problem link

Problem: To find the stack image when merge sort is called.

Explanation:

This problem can be solved in two ways:

  1. By simulating merge sort and printng the calls made.
  2. Using binary search:

    In this approach the given size is divided into 2 parts using

    mid=(L+R)/2;
    if(mid>=N)      //N is the index to be found
        R=mid;      //Shift the right pointer to middle i.e. index lies between middle and left
    else
        L=mid+1;    //Shift the left pointer to middle+1 i.e. index lies between middle and right
    

Using the second one is more preferable.

Problem setter's solution: SOLUTION

asked 31 May '15, 01:01

preetam's gravatar image

1★preetam
62
accept rate: 0%

edited 04 Jun '15, 17:33

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×12,340
×102

question asked: 31 May '15, 01:01

question was seen: 714 times

last updated: 04 Jun '15, 17:33