Facebook Hacker Cup 2016 Round 2.1

LiveCode is the premier environment for creating multi-platform solutions for all major operating systems - Windows, Mac OS X, Linux, the Web, Server environments and Mobile platforms. Brand new to LiveCode? Welcome!

Moderators: Klaus, FourthWorld, heatherlaine, kevinmiller, robinmiller

Post Reply
Posts: 1577
Joined: Tue May 28, 2013 2:20 pm
Location: Italy

Facebook Hacker Cup 2016 Round 2.1

Post by MaxV » Thu Jan 28, 2016 2:42 pm

Coding Contest Creation (difficulty 15/100)

You've been put in charge of creating the problems for a certain high-profile programming contest series.

The series will consist of one or more contests of exactly 4 problems each. Every problem has a difficulty rating (an integer between 1 and 100, inclusive), and the ratings of the 4 problems in each contest must be strictly increasing, but with a difference of no more than 10 between consecutive problems. In other words, if the problems in a contest have difficulties a, b, c, and d (in order), then the inequalities a < b < c < d, b - a ≤ 10, c - b ≤ 10, d - c ≤ 10 must all hold.

You've been given an ordered list of N problems to use. Being an experienced problemsetter, you may also write some new problems to insert at any positions in the list, each with an integer difficulty between 1 and 100, inclusive. The final list of problems must still include the original N problems in their original order, though (with your new problems optionally mixed in).

Once the problem list is finalized, the first 4 problems (in order) will form a contest, the next 4 problems will form another contest, and so on. Note that the number of problems in the list must be divisible by 4, and that each of the contests formed must feature a valid ordered set of 4 problems. What's the minimum number of additional problems you must write in order to create a set of valid contests?

Input begins with an integer T, the number of contest series you need to create. For each series, there is first a line containing the integer N, then a line containing N space-separated integers, the ith of which is Di, the difficulty rating of the ith existing problem.


For the ith series, print a line containing "Case #i: " followed by the minimum number of additional problems you'll need to write.

1 ≤ T ≤ 50
1 ≤ N ≤ 100,000
1 ≤ Di ≤ 100

Explanation of Sample
In the first series, the four problems given are already a valid contest, so no new problems need to be written. In the second series, the four existing problems most certainly do not form a valid contest, due to the gap between the third and fourth ones - one possible way to salvage the situation is to add three new problems with difficulties 30, 29, and 30 after the third problem, as well as a problem with difficulty 42 at the end, creating two valid contests: [15, 20, 25, 30] and [29, 30, 40, 42].

Input sample:

Code: Select all

10 15 25 30
15 20 25 40
3 3 3
60 90 61 62 63 91 92 93
5 14 30 32 39 46 47 47 30 58 47
Output sample:

Code: Select all

Case #1: 0
Case #2: 4
Case #3: 9
Case #4: 4
Case #5: 9
Livecode Wiki: http://livecode.wikia.com
My blog: https://livecode-blogger.blogspot.com
To post code use this: http://tinyurl.com/ogp6d5w

Post Reply

Return to “Getting Started with LiveCode - Experienced Developers”