PROBLEM LINKS
DIFFICULTY
HARD
EXPLANATION
This problem looks quite mathematical and most of the accepted solutions were mathematical too. But the time limit was quite relaxed to allow DP solutions too. I am going to explain a DP approach which does not involve any kind of math.
Fix the biggest edge, say ‘M’. First calculate all the 5-tuples maintaining the “good” condition (hexagon or not hexagon). This is the easy part, you can just use backtrack to calculate that.
Now calculate all the 5-tuples which are not a hexagon and subtract those from the first to get the count of valid hexagons. This is the hard part.
A DP on digits with some precalculations can be used for that. Place the numbers in non-increasing order. So you are counting the number of ways to place 5 non-increasing integers such that the first integer is <=’X’ and their sum is <=’M’. The DP goes from left to right digit by digit of ‘M’.
The states of DP are: ( position, prefixX, prefixM, carry, an encoding of digits ( say S) )
position = position of the current digit of ‘M’ from left ( 0 ~ length of ‘M’)
prefixX = whether the first number currently is a prefix of ‘X’ or less than ‘X’ ( 0 or 1)
prefixM = whether the summed number currently is a prefix of ‘M’ or less than ‘M’ ( 0 or 1)
carry = the carry after placing the digits at this position ( 0 ~ 4)
S = a state encoding the relative orders of the partially filled numbers.
For example, say you are at position=3. And the partially formed numbers are: { 123,120,120,085,085 }.
Now this can be encoded as : { 9, 8, 8, 7, 7} [ The second and third number currently are equal and also the fourth and fifth and the numbers are placed in non-increasing order]. There are 16 different such encodings for five numbers.
Some precalculations can help in the DP part.
cnt1[ a] [b] [c1] [S] [c2] [T] [ z] = Number of ways to go( ways by placing 5 digits) from state S, carry c1 to state T, carry c2 such that the first digit is = ‘a’ and the digit after summing is= ‘b’.
cnt2[ a] [b] [c1] [S] [c2] [T] [z] = … first digit <= ‘a’ and the digit after summing is = ‘b’
cnt3[ a] [b] [c1] [S] [c2] [T] [z] = … first digit = ‘a’ and the digit after summing is <= ‘b’
cnt4[ a] [b] [c1] [S] [c2] [T] [z] = … first digit <= ‘a’ and the digit after summing is <=‘b’
For all the above arrays, z = 1 counts where last digit is zero and z=0 counts with any last digit.
All these can be precomputed by backtracking.
SETTER’S SOLUTION
Can be found here.