Max Avatar Time

Правка en2, от viraj.jadhav20, 2023-02-04 13:16:45

Problem Link:

Contest
Question

Author: rajpate77725

DIFFICULTY:

MEDIUM

PREREQUISITES:

ARRAY ,SLIDING WINDOW

PROBLEM:

On the lush alien world of Pandora live the Na'vi beings who appear primitive but are highly evolved.Doctor Grace runs a project which allows humans to transform in Avatar. Jake a paralyzed former Marine becomes mobile again through one such Avatar. Jake has been given a mission to become friends with the Na'vi people by transforming into Avatar.

The project runs for N days where on each day Jake can transform into Avatar for a specific amount of time. Through her experience, Doctor Grace can predict the transformation time of Jake for maximum K days. After each prediction, the next prediction occurs after F days.

Find the maximum Avatar time in each prediction.

EXPLANATION:

Observations: - Checkup is happening after every F days. - Out of f days trasformation can be predicted for max k days.

Approach: - We can use sliding window approach such that window slides after every F days and first k days of every F days can be choosen for a search of max element.

  • We used the deque to store the required index of max element after every iteration.
  • Whenever the max element comes we pop_back the element less than that element from the deque such that only the maximum element left at the back of the deque.
  • Corner case is there for the elements after the every possible window size.
  • After that we have the array of max element in every k interval.
  • Then we print the element in the interval of f elements.

TIME COMPLEXITY:

O(N) per test case.

CODE:

Editorialist's Code(C++)

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский viraj.jadhav20 2023-02-04 13:16:45 30 Tiny change: 'Author**: [Raj Pate]<br/>\n\n*' -> 'Author**: @rajpate7774<br/>\n\n*'
en1 Английский viraj.jadhav20 2023-02-04 13:12:01 3417 Initial revision (published)