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

×

# Chef and his software - TSECJ05 - Editorial

Chef and his software

Author: Yogesh Malpani
Editorialist: Yogesh Malpani

MEDIUM.

# PREREQUISITES:

ArrayList, Binary Search, Heap

# PROBLEM:

Given the values of N transactions, the task is to insert these to records and print the value of Kth highest transaction in the records at each insertion.

# QUICK EXPLANATION:

Find the index for the each new transaction using efficient Sorting algorithms which work well on an almost sorted list. Next find the Kth highest transaction and print it.

# EXPLANATION:

How to process a new transaction of record, Ni?
For every Ni, check if it is smaller than current Kth largest element.
If yes, then ignore it. If no, then a modification of Binary Search can be used to find the index for the Ni. This can be done in O(LogN) time.
The transaction value is added at an index in the ArrayList which runs in amortized constant time, O(N) time.
So the Time complexity of processing a new transaction is O(N + LogN).
The Kth highest transaction is found in the ArrayList in constant time, O(1).

# ALTERNATIVE SOLUTION:

Another Solution is to use Min Heap of size N to store N largest transactions of records. The Kth highest transaction is always at root and can be found in O(1) time.
How to process a new transaction of record?
Compare the new transaction value, Ni, with root of heap. If Ni is smaller, then ignore it. Otherwise replace root with Ni and call heapify for the root of modified heap. Time complexity of finding the Kth highest transaction is O(LogN).

# AUTHOR'S SOLUTION:

Solution can be found here.

This question is marked "community wiki".

asked 02 Jul '17, 15:18

1
accept rate: 0%

 0 Java users kindly use "Fast I/O" else get ready to experience "NZEC". answered 23 Nov '17, 14:21 0 accept rate: 0%
 0 I used Two heaps. One min heap and one max heap. https://ideone.com/ATY9yH answered 09 Dec '17, 17:42 1●1 accept rate: 0%
 0 i have used 1 priority queue to get the answer to the question . My solution here answered 13 Feb, 11:05 1●2 accept rate: 0%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

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

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×15,182
×2,535
×992
×770
×138
×6
×3
×3

question asked: 02 Jul '17, 15:18

question was seen: 827 times

last updated: 13 Feb, 11:05