Placement of Bots Complete Solution

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

Build an AI-First Career, Master the Complete Skillset

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

NSDC Certified

AI Forward Deployed Engineer Program

Full-stack engineering, production AI and client-facing consulting

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

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)