CNDLSTKS - Editorial

PROBLEM LINK:

Pair Of CandleSticks
Practice
Div-2 Contest

Author: John Nixon
Tester: John Nixon
Editorialist: John Nixon

DIFFICULTY:

Easy

PREREQUISITES:

None

PROBLEM:

A candlestick is a type of price chart used in technical analysis
that displays the high, low, open and closing prices of
Candlesticks reflect the impact of investor sentiment on security
prices and are used by technical analysts to determine
when to enter and exit trades.
We have been given an array of distinct positive integers called as
prices. Each integer in the array denoted by prices[i]
represents the high price in the candlestick.

You have to connect two candlesticks in such a way that
all the candlesticks between them have a height smaller
than the minimum height of the two.
The task is to find the total number of pairs of such
candlesticks.

QUICK EXPLANATION:

For the given array of High Prices of candlesticks we need to find pairs of prices such a way that the other prices between them are smaller than the pair of prices we picked and count how many such pairs exists in given prices array.

EXPLANATION:

For solving the giving problem we need to make certain observations

  1. Every adjacent pair satisfies our conditions, if n is our size of the Price's array there will be minimum of (n-1) pairs satisfying

  2. To find other than adjacent pairs we need to pick two numbers u,v such that the other numbers between u&v in the given array are lesser than u&v

To go ahead with our second observation we loop through all the elements in the prices array and set a sub-max value to the next price from where we are starting the loop .
We check if the price we started is greater than the next price in the list if yes , we start a new loop from where we saw a price less than the start price and continue this loop while updating our sub-max value if necessary and keeping a res variable to keep a track of such pairs whichever satisfy our conditions.

finally we add (n-1) to our res value to include our adjacent pairs too.

SOLUTIONS:

Setter's Solution
import sys
import os

def totalPairs(n, values):
    res = 0
    for i in range(n-2):
        sub_max = values[i+1]
        if values[i] > values[i+1]:
            for j in range(i+2, n):
                if values[i] > sub_max and values[j] > sub_max:
                    res += 1
                sub_max = max(sub_max, values[j])

    return res


if __name__ == "__main__":
    n = int(input())
    values = list(map(int, input().split()))
    start_time = time.time()
    answer = totalPairs(n, values)
    print(answer+(n-1))

Feel free to share your approach here. Suggestions are always welcomed. :slight_smile:

@jbn_6972 there’s no submit button?
I even tried :- To Submit

Check it out now