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

×

KRYP6 - Editorial

Contest
Practice

Author: Shivam Garg
Tester: Shiv Dhingra

DIFFICULTY

EASY

PREREQUISITES

Basic Knowledge of Sets (STL)

PROBLEM

Given a list of integers, for each of them find the maximum number less than the given number preceding it.

EXPLANATION

The brute approach will turn out to be of complexity $O(N ^2)$, and hence is bound to time out.

We can maintain a sorted set of numbers by iterating over the array. In other words, if we have a set of numbers preceding the given number, we can easily find out the largest number smaller than the given number.

We can simply perform binary search in this set to find the number just less than the given number.
This can be done by using lower_bound command of the set in C++, or equivalent in other languages.

set<long long>::iterator it = s.lower_bound(val);
it--;
return (*it);

This will fulfill our task. The complexity of accessing/inserting elements in the set is $O(Log(N))$.
So, the overall complexity turns out to be $O(N \hspace{1 mm} Log(N))$.

SOLUTION

Setter's Solution - Code

asked 13 Feb '18, 23:58

shivamg_isc's gravatar image

5★shivamg_isc
6211210
accept rate: 0%

edited 19 Feb '18, 14:59


your explanation is not clear bro(#no offence)

if u can then add little more details for the approach

thx in advance : )

link

answered 31 May '18, 00:22

rajput1999's gravatar image

4★rajput1999
3586
accept rate: 0%

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:

×15,682
×3,766
×1,038
×278
×160
×15

question asked: 13 Feb '18, 23:58

question was seen: 457 times

last updated: 31 May '18, 00:22