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

×

Chef and his software - TSECJ05 - Editorial

PROBLEM LINK:

Chef and his software

Author: Yogesh Malpani
Editorialist: Yogesh Malpani

DIFFICULTY:

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, 15:18

crazdhacker101's gravatar image

3★crazdhacker101
1
accept rate: 0%

edited 02 Jul, 17:11


Java users kindly use "Fast I/O" else get ready to experience "NZEC".

link

answered 23 Nov, 14:21

bhagirathi08's gravatar image

3★bhagirathi08
0
accept rate: 0%

I used Two heaps. One min heap and one max heap. https://ideone.com/ATY9yH

link

answered 09 Dec, 17:42

mohdali231993's gravatar image

2★mohdali231993
11
accept rate: 0%

edited 09 Dec, 17:45

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
×1,934
×614
×592
×120
×6
×3
×3

question asked: 02 Jul, 15:18

question was seen: 363 times

last updated: 09 Dec, 17:45