PROBLEM LINKSDIFFICULTYHARD EXPLANATIONThis 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 5tuples 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 5tuples 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 nonincreasing order. So you are counting the number of ways to place 5 nonincreasing 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) ) 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 nonincreasing 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' SETTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 23 Nov '12, 14:08
