CNTHEX - Editorial






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.


Can be found here.