0 like 0 dislike
1,786 views
in Competitive-Programming by Expert (19,470 points) | 1,786 views

2 Answers

0 like 0 dislike
Best answer

Complete RoadMap : 

Step-1 : Read : https://www.hackerearth.com/practice/algorithms/searching/binary-search/tutorial/   

Read : https://www.hackerrank.com/topics/binary-search   

(Grasp the STL concept in binary search , you should use it whenever you want to make things easy) 

Step-2 : Solve these : 

33. Search in Rotated Sorted Array

34. Find First and Last Position of Element in Sorted Array

35. Search Insert Position

69. Sqrt(x)

74. Search a 2D Matrix

https://www.youtube.com/watch?v=edJ19qIL8WQ&list=PLgUwDviBIf0qYbL4TBaEWgb-ljVdhkM7R   

Step-3 : Hope , you are getting the idea now! Read : https://www.topcoder.com/thrive/articles/Binary%20Search   

Step-4 : Solve : 

1)https://leetcode.com/problems/minimum-space-wasted-from-packaging 

2)https://leetcode.com/problems/closest-room/   

3)https://leetcode.com/problems/maximum-building-height/

4)Do utmost P operations . In each operation  ,select a subarray of size ‘k’ and add ‘1’s to it . Maximize the minimum element. 

5)https://leetcode.com/problems/max-sum-of-rectangle-no-larger-than-k/  

6)https://www.codechef.com/APRIL21C/problems/KAVGMAT

7)Partition array into k parts , such that the part with maximum sum is as small as possible. 

8)https://codeforces.com/contest/1486/problem/C2  

9)https://www.codechef.com/problems/GOTHAM   

10)https://atcoder.jp/contests/abc174/tasks/abc174_e  

11)https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27/0000000000209a9e (Involves binary bits concept , but still added)

12)https://codingcompetitions.withgoogle.com/kickstart/round/0000000000051066/0000000000051007

13)https://atcoder.jp/contests/abc155/tasks/abc155_d

Now , do these :

1)https://www.codechef.com/problems/ALIEN1

https://www.codechef.com/LTIME87A/problems/ALIENIN

https://codeforces.com/contest/1354/problem/C1

https://codeforces.com/contest/1354/problem/C2

2)https://www.codechef.com/RC122020/problems/RECNDROT

3)https://codingcompetitions.withgoogle.com/codejam/round/000000000019fef2/00000000002d5b63

4)https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc7/00000000001d3f5b

5)https://atcoder.jp/contests/abc138/tasks/abc138_e

Find the longest subarray whose cost is less than “s”.[Binary-Search]

(Cost of a subarray is :----> [i:j]-->[ a[i]+i*k + a[i+1]+(i+1)*k+....],where ‘k’ is length of the subarray)Solution:-https://ideone.com/xcpv66(Yes-code)

6)https://codeforces.com/contest/1295/problem/C

7)https://www.geeksforgeeks.org/queries-counts-array-elements-values-given-range/

8)https://www.hackerearth.com/practice/algorithms/searching/binary-search/practice-problems/algorithm/superior-substring-dec-circuits-e51b3c27/{Majority-Element-Concept}

https://www.geeksforgeeks.org/largest-subarray-having-sum-greater-than-k/

9)https://www.codechef.com/OCT18B/problems/HMAPPY

10)https://www.codechef.com/LTIME64B/problems/CHEFRES

12)https://binarysearch.com/problems/K-Distinct-Group 

13)https://codeforces.com/problemset/problem/68/B

14)https://binarysearch.com/room/Weekly-Contest-28-yJAzueUIWQ?questionsetIndex=1

15)https://codeforces.com/contest/1436/problem/C
16)https://www.hackerearth.com/challenges/competitive/april-circuits-20/algorithm/people-carrying-6dd467ed/editorial/

You are a master now , you know what to do now !!!

{https://codingcompetitions.withgoogle.com/codejam/round/000000000043580a/00000000006d1284}

by Expert (19,470 points)
0 like 0 dislike

Best Resources for Binary Search : 

https://codeforces.com/blog/entry/67509  

https://www.linkedin.com/posts/kumar-k-4ba3351a8_leetcode-binarysearch-activity-6808413725389852672-jiCf

https://www.hackerearth.com/practice/algorithms/searching/binary-search/tutorial/   

 

 

 

 

Best Problems : 

 

Good LeetCode Problems : 

1)https://leetcode.com/problems/minimum-space-wasted-from-packaging 

2)https://leetcode.com/problems/closest-room/   

3)https://leetcode.com/problems/minimum-number-of-days-to-make-m-bouquets/

 

(partition array into k parts , such that the part with maximum sum is minimized , find that maximum sum )

New Problem : https://codeforces.com/contest/1486/problem/C2

Best Problem : https://atcoder.jp/contests/abc174/tasks/abc174_e 

Another Best : https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27/0000000000209a9e  

 

-------------------------------------------------------------------------------------------------------------------------

1)

{Double Binary Search}

Best one : https://codingcompetitions.withgoogle.com/kickstart/round/0000000000051066/0000000000051007

(Asking for k’th highest number)

Solution : Sort the ranges w.r.p to start point one time. 

Another time w.r.p to end time.

(Descending Order)

Now you want to know how many numbers are greater than equal to 7.

Say ranges are : [100,90] ,[95,67],[30,7],[10,1],[9,2],[5,1]

[Start,End]

End points : [90,67,7,2,1,1]

Sum of all guys with end-points>=7=>x

(Don’t consider those ranges which start and end at 7 now,because they have been considered above already)

All ranges with start points greater than equal to 7 : [100,90] ,[95,67],[30,7],[10,1],[9,2].

And from them, only those guys with end-points smaller than 7(their sum)  : abs(10-1)+1 + abs(9-2)+1 = 18=y.

Answer is x + y . 

{Code Not written}

Similar to :

{Double Binary Search}

 https://atcoder.jp/contests/abc155/tasks/abc155_d

(Same logic for the kth smallest pair)

 (Yes-Code)

 

------------------------------------------------------------------------------------------------------------------


 

1)https://www.codechef.com/problems/ALIEN1(Yes Code)

https://www.codechef.com/LTIME87A/problems/ALIENIN(Yes Code)

https://codeforces.com/contest/1354/problem/C1(Geometry+Circles)(No-code)

https://codeforces.com/contest/1354/problem/C2(Geometry+Circles)(No-code)

2)https://www.codechef.com/RC122020/problems/RECNDROT(No-code)

3)https://codingcompetitions.withgoogle.com/codejam/round/000000000019fef2/00000000002d5b63(Based on circles+geometry)(No-code)

4)https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc7/00000000001d3f5b(Yes-code)

5)https://atcoder.jp/contests/abc138/tasks/abc138_e(Yes-code)

 

Find the longest subarray whose cost is less than “s”.[Binary-Search]

(Cost of a subarray is :----> [i:j]-->[ a[i]+i*k + a[i+1]+(i+1)*k+....],where ‘k’ is length of the subarray)Solution:-https://ideone.com/xcpv66(Yes-code)



 

6)https://codeforces.com/contest/1295/problem/C(Yes-code)

 

7)https://www.geeksforgeeks.org/queries-counts-array-elements-values-given-range/

(No-code)

 

8)https://www.hackerearth.com/practice/algorithms/searching/binary-search/practice-problems/algorithm/superior-substring-dec-circuits-e51b3c27/{Majority-Element-Concept}

 

Required : Longest Subarray with Sum greater than Equal to Zero

{Kadane’s algorithm}(Best method)

https://www.geeksforgeeks.org/largest-subarray-having-sum-greater-than-k/


 

(No-code)

 

9)https://www.codechef.com/OCT18B/problems/HMAPPY

(No-code)

 

10)https://www.codechef.com/LTIME64B/problems/CHEFRES

(Yes-code)



 

12)https://binarysearch.com/problems/K-Distinct-Groups(Wow)

 

13)https://codeforces.com/problemset/problem/68/B(Yes)

 

14)https://binarysearch.com/room/Weekly-Contest-28-yJAzueUIWQ?questionsetIndex=1(No)

 

15)https://codeforces.com/contest/1436/problem/C(Yes)


 

16)https://www.hackerearth.com/challenges/competitive/april-circuits-20/algorithm/people-carrying-6dd467ed/editorial/(Later){Great-Problem){No-code}

 

 

by Expert (19,470 points)

Get best answers to any doubt/query/question related to programming , jobs, gate, internships and tech-companies. Feel free to ask a question and you will receive the best advice/suggestion related to anything you ask about software-engineering , development and programming problems .