Connection Status:
Competition Arena > LongJump2

LongJump2

TCO19 SRM 758 · 2019-05-09 · by misof

TCO19 SRM 758 · 2019-05-09 · by misof · Simple Math, Simple Search, Iteration
Class Name: LongJump2
Return Type: int
Method Name: countNewLeaders
Arg Types: (int, vector<int>)
Problem Statement

Problem Statement

You are watching the finals of a long jump competition. There are N contestants with bib numbers 1 through N. There will be three rounds of jumps. In each round, the contestants jump in the order from 1 to N.

At the beginning, there is no leader. After each jump, if the jump is strictly longer than each of the previous jumps and the contestant who made the jump isn't the current leader, the contestant becomes the leader.

You are given the int N. You are also given the int[] jumpLengths that contains the lengths of all 3N jumps in the competition, in the order in which they were performed. Compute how many times some contestant became the leader during the competition.

Constraints

  • N will be between 1 and 50, inclusive.
  • jumpLengths will contain exactly 3*N elements.
  • Each element of jumpLengths will be between 0 and 1000, inclusive.
Examples
0)
1
{812, 780, 815}
Returns: 1

There is a single contestant. When they made their first jump, they became the leader. As there was nobody else to overtake them, the only contestant then remained the leader for the rest of the competition. Note that the last jump did not change the leader, even though it was longer than the first one.

1)
2
{0, 0, 0, 0, 0, 0}
Returns: 1

The first jump of length 0 is enough to become the leader. The subsequent jumps of length 0 are not enough to overtake the leader.

2)
2
{810, 811, 812, 813, 814, 815}
Returns: 6
3)
3
{800, 10, 20, 810, 30, 40, 50, 830, 830}
Returns: 2

Round 1, jump 1: contestant #1 jumps 800 and becomes the leader. Round 2, jump 1: contestant #1 jumps 810, but she is already the leader, so the leader does not change. Round 3, jump 2: contestant #2 jumps 830 and overtakes contestant #1 to become the new leader. Round 3, jump 3: contestant #3 also jumps 830, but contestant #2 remains the leader - you need to jump strictly more than the previous leader in order to overtake them.

4)
47
{1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 2, 3, 2, 1, 0, 1, 3, 3, 2, 1, 3, 0, 1, 0, 0, 2, 3, 3, 2, 0, 2, 3, 2, 0, 1, 1, 2, 3, 1, 1, 3, 1, 1, 0, 1, 2, 3, 0, 2, 3, 0, 0, 3, 0, 2, 0, 2, 0, 1, 1, 5, 4, 3, 1, 3, 4, 3, 4, 4, 0, 5, 0, 1, 1, 4, 2, 5, 0, 4, 1, 5, 0, 3, 0, 0, 0, 2, 0, 4, 2, 1, 4, 5, 4, 1, 4, 4, 2, 4, 4, 0, 4, 3, 2}
Returns: 3

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

Coding Area

Language: C++17 · define a public class LongJump2 with a public method int countNewLeaders(int N, vector<int> jumpLengths) · 122 test cases · 2 s / 256 MB per case

Submitting as anonymous