When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

viraj.jadhav20's blog

By viraj.jadhav20, history, 13 months ago, In English

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++)
  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?