Placement of Bots Complete Solution

This article is part of the Scaler Topics Fortnightly Contest - 19

Transform Your Career

Choose from our industry-leading programs designed for career success

NSDC Certified

Modern Software and AI Engineering Program

Master full-stack development with AI integration

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Modern Data Science and ML with specialisation in AI

Advanced data science techniques with AI specialization

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Advanced AIML with Specialisation in Agentic AI

Deep dive into AIML with focus on Agentic systems

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

DevOps, Cloud & AI Platform Engineering

Build and manage AI-powered cloud infrastructure

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

AI Engineering Advanced Certification by IIT-Roorkee

Premier AI engineering certification from IIT-Roorkee

3 MonthsDuration

AI-LedCurriculum

Career SupportSupport

Go to Program

Solution Approach

Consider the following simulation of determining the positions of bots

• For every integer i between 1 and 109 (inclusive), perform the following operations. A) For every integer j such that A[j]=i, add j to “list of probable positions” B) Choose one position from “list of probable positions” calling it k. Put bot k into position i and remove bot k from the list. C) If a bot such that B[j]≤i remains in “list of probable positions,” then it is impossible to position all the bots.
• After repeating it up to i=109, if all the bots are in the positions, then that assignments of bots satisfy the conditions.
• Now, what is the optimal strategy of step (B) in the simulation?
• In fact, if we place the bot j with minimum B[j], we can always put the balls optimally. This is because the conditions in step (C) does not become stricter than when placing a bot whose B[j] is not minimum.
• The operation of “choosing a bot with minimum B[j]” can be fulfilled by data structures like priority_queue.
• Also, as we do not have to find the actual positions, it is sufficient to manage just the value of B[j] when placing a bot.
• Although doing the simulation described above naively will lead to TLE, it can be avoided by the improvement in which “once the list becomes empty, skip i to the next value that the list becomes non-empty by the operation (A).”
• To do so, one can use a set, or perform a binary search against the array of A sorted beforehand.
• Therefore, we could solve the problem in a total time complexity of O(NlogN).

Time Complexity - O(N*log(N)) Space Complexity - O(N)

C++ Implementation

Java Implementation

Hiring Partners:

GoogleAmazonMicrosoftFlipkartAdobe1200+ more

Python Implementation