## Coding Challenge 4!

The Partridge Family were neither partridges nor a family. Discuss.
chili
Posts: 3939
Joined: December 31st, 2011, 4:53 pm
Location: Japan
Contact:

### Coding Challenge 4!

Maximum Difference 1

Challenge Page: https://patdash.planetchili.net/challenges/1
Announcement Video: https://youtu.be/nwJ7NDkFSJ8
Guide Video: https://youtu.be/63uc34wNSdk
Ultimate Solution: https://patdash.planetchili.net/series/4

Problem Statement

You are given a std::vector v of n integral values. Return the maximum value of v[j] - v where j > i and v[j] > v. If no such value exists, return -1.

Start Code
Available on the challenge page (see link above). Also see the guide video (link above).

Problem Conditions
8 <= n <= 80,000,000
n is a multiple of 8
0 <= v <= 65535

Code Conditions
Write your solution in Solution.cpp (follow the directions in that file). Code will be compiled/evaluated using VS2017 C++ compiler in x64 configuration. You may use the stdlib + visual studio compiler intrinsics, but no other libraries. If code is suspected of potentially trying to subvert the test or the test system, it will be rejected (so do not obfuscate).

Test Conditions
Test will run on Intel i7 4770k (Haswell) CPU. You may not consume more than 1 GB ram in total. Algorithm must complete within 1000ms.

Submission
Submit on the challenge page (link above). See challenge page for submission deadline. Submit only your Solution.cpp file as a zip archive. The name of the zip archive itself does not matter, but must have the .zip extension. Zipped solution must be less than 20kb in size. See the guide video (link above) for a walk-through on submission.

Scoring
Full points given for passing all tests. Part points given for passing all low-n tests but timing out on high-n. Mono bounties for fastest algorithm and earliest submission that passes all tests. Poly bounty for beating Chili in speed performance. See challenge page for details on the number of algos awarded.

Notes
• See announcement video for additional explanation. Discussion / questions should happen here rather than in the comments on the announcement video (I will not answer clarification questions in the comments).
• As the first run with the new system, this is somewhat of a beta test. Expect that there might be some bumps in the road.
Chili

Pindrought
Posts: 432
Joined: September 26th, 2013, 4:57 pm
Location: Kentucky
Contact:

### Re: Coding Challenge 4!

Looks fun. When do you think the links will be up?
PM me if you need to contact me. Thanks to all the helpful people on this forum especially to Chili.

chili
Posts: 3939
Joined: December 31st, 2011, 4:53 pm
Location: Japan
Contact:

### Re: Coding Challenge 4!

Links are up my friend, happy coding
Chili

Pindrought
Posts: 432
Joined: September 26th, 2013, 4:57 pm
Location: Kentucky
Contact:

### Re: Coding Challenge 4!

Something doesn't seem right here.
https://i.imgur.com/GtQGIle.png

Or am I just blind?
PM me if you need to contact me. Thanks to all the helpful people on this forum especially to Chili.

chili
Posts: 3939
Joined: December 31st, 2011, 4:53 pm
Location: Japan
Contact:

### Re: Coding Challenge 4!

Nah, thanks for that. There was a command I needed to run on the production server to add the new account records to existing patron accounts. It should be working now.

Chili

Pindrought
Posts: 432
Joined: September 26th, 2013, 4:57 pm
Location: Kentucky
Contact:

### Re: Coding Challenge 4!

Nice it works now.

I submitted a mess of code. We'll see if it works.
PM me if you need to contact me. Thanks to all the helpful people on this forum especially to Chili.

Pindrought
Posts: 432
Joined: September 26th, 2013, 4:57 pm
Location: Kentucky
Contact:

### Re: Coding Challenge 4!

Question - When judging off the speed is it determined off large data sets, small data sets or both?
PM me if you need to contact me. Thanks to all the helpful people on this forum especially to Chili.

chili
Posts: 3939
Joined: December 31st, 2011, 4:53 pm
Location: Japan
Contact:

### Re: Coding Challenge 4!

Both, but it is additive, so the contribution of small data sets to the final result will be negligible.
Chili

Pindrought
Posts: 432
Joined: September 26th, 2013, 4:57 pm
Location: Kentucky
Contact:

### Re: Coding Challenge 4!

chili wrote:Both, but it is additive, so the contribution of small data sets to the final result will be negligible.
Good stuff.
PM me if you need to contact me. Thanks to all the helpful people on this forum especially to Chili.

Yumtard
Posts: 571
Joined: January 19th, 2017, 10:28 pm
Location: Idiot from northern Europe

### Re: Coding Challenge 4!

Submitted a very simple algorithm (maybe too simple, might've missed something in the instructions)

looking forward to having my mind blown by your optimizations