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 has been given quite the challenging programming assignment in school: given a list of \$N\ (1 \le N \le 50)\$ distinct integers \$A_{1..N}\ (1 \le A_i \le 100)\$, he must find the largest one!
Ethan has implemented an algorithm to solve this problem, described by the following pseudocode:
- Set \$m\$ to be equal to \$A_1\$.
- 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\$.
- 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 code-golf, so shortest answer (in bytes) wins!
%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\$%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\$