Page 1 of 10

Coding Challenge 4!

Posted: September 21st, 2018, 3:18 pm
by chili
               Maximum Difference 1

Challenge Page: https://patdash.planetchili.net/challenges/1
Announcement Video: https://youtu.be/nwJ7NDkFSJ8
Guide Video: https://youtu.be/63uc34wNSdk
Results/Solution: https://www.youtube.com/watch?v=ebH_-ShTv0A
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. ;)

Re: Coding Challenge 4!

Posted: September 22nd, 2018, 4:07 am
by Pindrought
Looks fun. When do you think the links will be up?

Re: Coding Challenge 4!

Posted: September 22nd, 2018, 7:22 am
by chili
Links are up my friend, happy coding ;)

Re: Coding Challenge 4!

Posted: September 22nd, 2018, 8:02 am
by Pindrought
Something doesn't seem right here.
https://i.imgur.com/GtQGIle.png

Or am I just blind?

Re: Coding Challenge 4!

Posted: September 22nd, 2018, 8:21 am
by chili
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.

Thanks for the heads up :D

Re: Coding Challenge 4!

Posted: September 22nd, 2018, 9:02 am
by Pindrought
Nice it works now.

I submitted a mess of code. We'll see if it works.

Re: Coding Challenge 4!

Posted: September 22nd, 2018, 4:17 pm
by Pindrought
Question - When judging off the speed is it determined off large data sets, small data sets or both?

Re: Coding Challenge 4!

Posted: September 22nd, 2018, 4:48 pm
by chili
Both, but it is additive, so the contribution of small data sets to the final result will be negligible.

Re: Coding Challenge 4!

Posted: September 22nd, 2018, 5:13 pm
by Pindrought
chili wrote:Both, but it is additive, so the contribution of small data sets to the final result will be negligible.
Good stuff.

Re: Coding Challenge 4!

Posted: September 22nd, 2018, 5:15 pm
by Yumtard
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 :)