Connection Status:
Competition Arena > Prominence

Prominence

SRM 780 · 2020-03-06 · by misof

SRM 780 · 2020-03-06 · by misof · Simple Math, Simple Search, Iteration, Sorting
Class Name: Prominence
Return Type: long
Method Name: sumOfProminences
Arg Types: (int, vector<int>, vector<int>, vector<int>)
Problem Statement

Problem Statement

In topography, the prominence of a mountain is defined as its height relative to the lowest contour line encircling it but containing no higher summit within it. In other words:

  • The prominence of each tallest mountain is equal to its height.
  • For any non-tallest mountain M of height h, its prominence is the largest x with the following property: If you start at the top of mountain M and never reach the altitude h-x, you cannot walk to the top of any mountain that is strictly taller than M.

In this problem we have a 2-dimensional mountain range: a polyline that goes from the left to the right. The range is described by the int[] H. The vertices of the polyline are the points (i, H[i]) for i = 0 to N-1. We assume that these are the only mountains in the world.

A peak in the mountain range is any point such that from that point we go strictly downwards in each possible direction. (Thus, peaks correspond to strict local maxima of H.)

For each peak, calculate its prominence. Return the sum of all those prominences.

Due to the limitations of our current platform, please use the pseudocode below to generate the array H. The symbol % represents the modulo operator. 

for i = 0 .. N-1:
    parity = i % 2
    a = coef[3*parity]
    b = coef[3*parity+1]
    c = coef[3*parity+2]
    H[i] = (((a*i + b) % 1000000007)*i + c) % 1000000007

for j = 0 .. idx.length-1:
    H[ idx[j] ] = val[j]

Notes

  • The reference solution can efficiently solve any array of the given size.
  • Please use 64-bit integers in the code that generates H to avoid integer overflow.

Constraints

  • N will be between 2 and 1,000,000, inclusive.
  • coef will contain exactly 6 elements.
  • Each element of coef will be between 0 and 1,000,000,006, inclusive.
  • idx will contain between 0 and 100 elements, inclusive.
  • Each element of idx will be between 0 and N-1, inclusive.
  • Elements of idx will be distinct.
  • val will contain the same number of elements as idx.
  • Each element of val will be between 0 and 1,000,000,006, inclusive.
Examples
0)
7
{0, 0, 47, 0, 0, 47}
{}
{}
Returns: 0

H = {47, 47, 47, 47, 47, 47, 47} There are no peaks. The sum of an empty set is zero.

1)
8
{0, 0, 47, 0, 0, 42}
{}
{}
Returns: 188

H = {47, 42, 47, 42, 47, 42, 47, 42} There are four peaks. Each of them has prominence 47.

2)
10
{0, 0, 0, 0, 0, 0}
{0, 1, 2, 3, 4, 5, 6, 7, 9, 8}
{500, 300, 400, 200, 400, 700, 100, 300, 300, 100}
Returns: 1500

H = {500, 300, 400, 200, 400, 700, 100, 300, 100, 300} Peaks correspond to indices 0, 2, 5, 7, and 9. Their prominences are 300, 100, 700, 200, and 200.

3)
16
{123456789, 234567890, 345678901, 456789012, 567890123, 678901234}
{7}
{890123456}
Returns: 4543586810

H = {345678901, 703580362, 308641830, 493672669, 259259064, 938077051, 197530603, 890123456, 123456447, 789822019, 37036596, 197162605, 938271057, 258815266, 827159816, 974780002}. The peaks in this mountain range, going left to right, have prominences 444321298, 185030839, 901040455, 692592853, 666365572, 679455791, and 974780002.

4)
1000000
{0, 1, 10000000, 0, 1000000006, 9000000}
{0}
{20000000}
Returns: 1000017500001

Submissions are judged against all 83 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Prominence with a public method long long sumOfProminences(int N, vector<int> coef, vector<int> idx, vector<int> val) · 83 test cases · 2 s / 256 MB per case

Submitting as anonymous