17
\$\begingroup\$

This is a problem that the Hacker Cup team made for the 2018 Facebook Hacker Cup, but we ended up not using it (though Ethan struggles through a variety of other challenges). Normally code size isn't a factor in the Hacker Cup, but we thought this would make for an interesting code golf challenge. We look forward to seeing how a different sort of competitive programmer tackles this problem!


Ethan Finds the Maximum Element

Ethan has been given quite the challenging programming assignment in school: given a list of \$N\ (1 <= N <= 50)\$ distinct integers \$A_{1..N}\ (1 <= A_i <= 100)\$, he must find the largest one!

Ethan has implemented an algorithm to solve this problem, described by the following pseudocode:

  1. Set \$m\$ to be equal to \$A_1\$.
  2. Iterate \$i\$ upwards from 2 to \$N\$ (inclusive), and for each \$i\$, if \$A_i > A_{i-1}\$, set \$m\$ to be equal to \$A_i\$.
  3. Output \$m\$.

Sometimes this algorithm will output the correct maximum value, but other times it sadly won't.

As Ethan's teaching assistant, you have some say in what input data his solution will be evaluated on. The professor has given you a list of \$N\$ distinct integers \$A_{1..N}\$ to work with, but you may shuffle them into any permutation you'd like before feeding them into Ethan's program. This is your opportunity to show some mercy!

For how many different permutations of \$A_{1..N}\$ would Ethan's algorithm produce the correct output?

Input Format:

Line 1: 1 integer, \$N\$
Line 2: \$N\$ space-separated integers, \$A_{1..N}\$

Output Format:

1 integer, the number of permutations of \$A\$ for which Ethan's algorithm would produce the correct output.

Sample Input 1:

1  
100

Sample Output 1:

1

Explanation:

Only one permutation of \$[100]\$ exists, and Ethan's program would correctly output 100 for it.

Sample Input 2:

3  
16 82 43

Sample Output 2:

5

Explanation:

Ethan's program would correctly output 82 for 5 of the 6 possible permutations of \$[16, 82, 43]\$. However, when \$A = [82, 16, 43]\$, it would incorrectly output 43 instead.

Sample Input 3:

10  
26 81 40 5 65 19 87 27 54 15

Sample Output 3:

986410

Rules

This is , so shortest answer (in bytes) wins!

\$\endgroup\$
  • 13
    \$\begingroup\$ Welcome to codegolf :) This is a well specified question but there are a few parts that mismatch the cultures of competitive programming. Particularly the section you labeled "input format" - generally golfing IO is uninteresting and so challenges here usually allow input in any convenient manner. We have a sandbox where you can post challenges for review before they go live. Good luck! \$\endgroup\$ – FryAmTheEggman Oct 24 at 17:03
  • 10
    \$\begingroup\$ For example, in the sandbox I would have asked why \$ A_{n} \$ needs to be specified. Since the integers are distinct, only \$ N \$ matters. \$\endgroup\$ – FryAmTheEggman Oct 24 at 17:07
  • 8
    \$\begingroup\$ While the %107 spec (and similar avoidances of overly large numbers) is typical on many other competitive programming sites, it's not really part of the culture here. Posters on this forum don't usually care whether an answer is too large to be reasonably displayed. \$\endgroup\$ – mypetlion Oct 24 at 17:41
  • 7
    \$\begingroup\$ The input you can definitely change without particularly impacting answers. The output may be more of a problem, and you could consider asking the people who answered about if they mind the change. Looking at them, most of them would simply remove a literal %107 from their code, so I would suspect that changing it is fine. If you do, make sure you leave a comment on each answer that hasn't updated it so they know to make the change. \$\endgroup\$ – FryAmTheEggman Oct 24 at 21:38
  • 4
    \$\begingroup\$ Thanks for posting this here! I have two comments. First, thanks for mentioning the problem source at the very start. When I read challenges here that sound like they are from programming contests, I start worrying that they are attempts at cheating or plagiarism. Second, I think less puzzley programming-contest style challenges that are about implementing code work better here. Please do post more if you have them. While this challenge still has room for golfing once you solve out the math "trick", our answers being open means that once someone solves the math, everyone just copies the idea. \$\endgroup\$ – xnor Oct 25 at 21:42

11 Answers 11

17
\$\begingroup\$

APL (Dyalog Unicode), 5 3 bytes

⍳⊥×

Try it online!

Adám gave me an inspiration to golf this further.

How it works

⍳⊥×  Monadic train. Input: n, the length of array A.
  ×  v: Signum, which always gives 1 because n ≥ 1
⍳    B: An array of 0..n-1
 ⊥   Scalar-expand v to get V, a length-n vector of ones,
       then mixed base conversion of V in base B

APL (Dyalog Unicode), 5 bytes

⍳⊥⍴∘1

Try it online!

Edited to remove modulo 107

Uses HyperNeutrino's formula, but optimized through the use of (mixed base conversion) directly. Uses ⎕IO←0.

How the code works

⍳⊥⍴∘1  Monadic train. Input: n, the length of array A.
  ⍴∘1  V: An array of 1's of length n
⍳      B: An array of 0..n-1
 ⊥     Mixed base conversion of V in base B

How the works

base:  0         1         2         .. n-3         n-2 n-1
digit: 1         1         1         .. 1           1   1
value: 1×..(n-1) 2×..(n-1) 3×..(n-1) .. (n-2)×(n-1) n-1 1
sum of all digit values is the answer.
\$\endgroup\$
  • 4
    \$\begingroup\$ This is now my all time favorite use of mixed base. \$\endgroup\$ – Jonah Oct 25 at 3:12
  • \$\begingroup\$ I've edited the problem to remove the mod 107 \$\endgroup\$ – Wesley May Oct 25 at 5:09
  • \$\begingroup\$ @Adám Uptack does scalar expansion too?! \$\endgroup\$ – Bubbler Oct 25 at 7:31
  • \$\begingroup\$ -2 bytes: ⍳⊥× Try it online! \$\endgroup\$ – Adám Oct 25 at 7:34
  • \$\begingroup\$ @Adám I noticed that too, after seeing your 4-byte comment :) \$\endgroup\$ – Bubbler Oct 25 at 7:36
19
\$\begingroup\$

Jelly, 6 bytes

RU×\S:

Try it online!

Let's analyze under which scenarios this algorithm works.

If the maximum element is at the end of the list, this obviously works, since \$A_N>A_{N-1}\$ and it is processed last. This gives \$(N-1)!\$ possibilities.

If the maximum element is at the second last position, then this obviously works, since \$A_N<A_{N-1}\$ so it is not processed, and \$A_{N-1}>A_{N-2}\$ and is processed last. This gives \$(N-1)!\$ possibilities. There is no overlap between this case and the above because the numbers are guaranteed unique.

If the maximum element is at the third last position, then it depends on the last two elements. If the last element is larger than the second last element, it is treated as the maximum, which fails. There are \$(N-1)!\$ cases, and we can match them by identical first \$(N-3)\$ elements with one case going \$\cdots,max,A,B\$ and the other going \$\cdots,max,B,A\$. Exactly one of these is valid and not the other, so there are \$\frac{(N-1)!}{2}\$ cases.

In general, if the maximum element has \$k\$ elements after it, then the rest of the list must be strictly descending. There is exactly one case for each set of last \$k\$ elements out of the \$k!\$ permutations.

Thus, the answer is \$\frac{(N-1)!}{0!}+\frac{(N-1)!}{1!}+\cdots+\frac{(N-1)!}{(N-1)!}\$. This is OEIS A000522.

This is equal to \$\frac{\frac{N!}{0!}+\frac{N!}{1!}+\cdots+\frac{N!}{(N-1)!}}{N}\$, which is \$\frac{(N\times(N-1)\times(N-2)\times\cdots\times 1+N\times(N-1)\times(N-2)\times\cdots\times 2+\cdots+N}{N}\$, which is the sum of the cumulative product of the list \$[N,N-1,\cdots,2,1]\$, divided by N.

RU×\S:
R       [1, 2, ..., N]
 U      reversed
   \    cumulative
  ×     product
    S   sum
     :  divided by (N)

Having MathJax is really nice :D

Note that the list literally does not matter. All we need to know is N.

\$\endgroup\$
  • \$\begingroup\$ I don't think this is right. For [1,2,3,4,5,6] your answer returns 5, but even by hand, I can find more than 5 permutations where Ethan's algorithm will work. 654321,564321,465321,365421,265431,165432,... \$\endgroup\$ – mypetlion Oct 24 at 17:37
  • \$\begingroup\$ @mypetlion mod 107 \$\endgroup\$ – HyperNeutrino Oct 24 at 17:38
  • 1
    \$\begingroup\$ It's pretty common on other competitive programming sites, but I think mostly out of necessity because answers get judged automatically. OP is new here, so may not be aware that that sort of thing isn't really done. I've left a comment for them. \$\endgroup\$ – mypetlion Oct 24 at 17:43
  • 1
    \$\begingroup\$ @user2357112 That's fair. In this specific case this works for reasonable input values until the output grows too large and that's not a matter of golfed or not, but in general, you have a point. \$\endgroup\$ – HyperNeutrino Oct 25 at 3:38
  • 1
    \$\begingroup\$ To be cheeky, you could take the second input via STDIN :P I don't believe it would affect the program in any way and would still be "taking" a second input \$\endgroup\$ – caird coinheringaahing Oct 25 at 6:42
5
\$\begingroup\$

Retina, 44 bytes

K`;
"$+"+`(.*);(.*)
$.(_$1*);$.(_$1*$2*
.*;

Try it online! Explanation:

K`;

Replace N with a counter and output (these should be decimal 0, but the empty string works here).

"$+"+`

Repeat N times...

(.*);(.*)
$.(_$1*);$.(_$1*$2*

... multiply the output by the counter and increment both.

.*;

Delete the loop counter.

Previous 47 bytes including modulo 107:

K`;
"$+"{`(i*);(j*)
i$1;j$.1*$2
)`(\w{107})*

j

Try it online! Explanation:

K`;

Replace N with a counter and output (both initially 0).

"$+"{`
)`

Repeat N times...

(i*);(j*)
i$1;j$.1*$2

... multiply the output by the counter and increment both...

(\w{107})*

... and reduce modulo 107.

j

Convert the output to decimal.

\$\endgroup\$
  • \$\begingroup\$ I've edited the problem to remove the mod 107 \$\endgroup\$ – Wesley May Oct 25 at 5:09
3
\$\begingroup\$

05AB1E, 8 5 4 bytes

-1 byte thanks to @KevinCruijssen

Implementation of @Neil's algorithm.

GNP>

Explanation:

G    for loop from 1 to input 
 N   push current iteration
  P  multiply the stack; in the first iteration there's only 1 element (1)
   > increment

Try it online!

\$\endgroup\$
  • \$\begingroup\$ I've edited the problem to remove the mod 107 \$\endgroup\$ – Wesley May Oct 25 at 5:10
  • 1
    \$\begingroup\$ In your current approach the P (product of stack) could be * (multiply). However, your P did give me the idea for -1 byte: simply remove the $. The first iteration will take the product of just the [N=0] on the stack, and every next iteration will take the product of [previousValue,N]: Try it online. \$\endgroup\$ – Kevin Cruijssen Oct 25 at 8:13
2
\$\begingroup\$

JavaScript (ES6),  19  18 bytes

A shorter version suggested by @Neil
Saved 1 byte thanks to @Jitse

f=n=>n&&--n*f(n)+1

Try it online!

Implements the following formula from A000522:

$$\cases{a_0=1\\ a_{n}=n\cdot a_{n-1} + 1,&n>0}$$

Turned into:

$$\cases{a_0=0\\ a_{n}=(n-1)\cdot a_{n-1} + 1,&n>0}$$


JavaScript (ES6), 35 bytes

This is a port of @HyperNeutrino's answer.

Takes only \$n\$ as input, as per this consensus.

n=>(g=n=>n&&(p*=n)+g(n-1))(n,p=1)/n

Try it online!

\$\endgroup\$
  • \$\begingroup\$ The OEIS gives a formula that's only 24 bytes: Try it online! \$\endgroup\$ – Neil Oct 24 at 19:21
  • \$\begingroup\$ I've edited the problem to remove the mod 107 \$\endgroup\$ – Wesley May Oct 25 at 5:08
  • 1
    \$\begingroup\$ @WesleyMay Thanks for the heads up. Updated. \$\endgroup\$ – Arnauld Oct 25 at 7:01
  • 1
    \$\begingroup\$ 18 bytes \$\endgroup\$ – Jitse Oct 25 at 8:23
1
\$\begingroup\$

Python 3, 28 bytes

f=lambda n:n and~-n*f(n-1)+1

Try it online!

Python port of Neil's algorithm.

\$\endgroup\$
1
\$\begingroup\$

R, 28 bytes

n=scan();sum(cumprod(n:1))/n

Try it online!

R port of @HyperNeutrino’s algorithm.

\$\endgroup\$
1
\$\begingroup\$

APL (Dyalog Unicode), 12 bytes

×\∘⌽∘⍳∘≢+.÷≢

Try it online!

-4 bytes thanks to the change in specifications;

-3 bytes thanks to @Adám

Train that implements @HyperNeutrino's formula, so go upvote their answer.

\$\endgroup\$
  • \$\begingroup\$ I've edited the problem to remove the mod 107 \$\endgroup\$ – Wesley May Oct 25 at 5:08
  • \$\begingroup\$ 107|×\∘⌽∘⍳∘≢+.÷≢ but you can remove the 107| now. \$\endgroup\$ – Adám Oct 25 at 7:31
1
\$\begingroup\$

C (gcc), 69 62 60 bytes

Following the consensus in C;

Updated to the most golfed solution thanks to contributions from Arnauld and FryAmTheEggman.

mod 107 has been removed from the rules, I was being too tricky. Thanks for the edit Arnauld.

c,o,d,e;f(n){for(e=n;n--;c+=o)for(d=e,o=1;d>n;)o*=d--;c/=e;}

Try it online!

\$\endgroup\$
  • 2
    \$\begingroup\$ Nice variable naming. ;-) \$\endgroup\$ – AdmBorkBork Oct 24 at 19:49
  • 2
    \$\begingroup\$ @Arnauld In fact, you can save another with more fors! \$\endgroup\$ – FryAmTheEggman Oct 24 at 21:45
  • 1
    \$\begingroup\$ @FryAmTheEggman Going a step further, that can now be written in 62 bytes. \$\endgroup\$ – Arnauld Oct 24 at 21:57
  • 1
    \$\begingroup\$ I've edited the problem to remove the mod 107 \$\endgroup\$ – Wesley May Oct 25 at 5:08
  • 2
    \$\begingroup\$ I didn't notice that you were taking twice the same input, which is not the same as ignoring one of the inputs described in the challenge. I don't think that's allowed. So, I would suggest this 60-byte version instead (without the mod 107). \$\endgroup\$ – Arnauld Oct 25 at 7:12
1
\$\begingroup\$

Japt -x, 6 bytes

ÆÉ /Xl

Try it

\$\endgroup\$
  • \$\begingroup\$ I've edited the problem to remove the mod 107 \$\endgroup\$ – Wesley May Oct 25 at 5:10
  • \$\begingroup\$ 107 can be #k \$\endgroup\$ – Shaggy Oct 25 at 7:10
0
\$\begingroup\$

Ruby, 24 bytes

f=->n{n<1?1:f[n-=1]*n+1}

Try it online!

Using the formula from OEIS A000522

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.