You are not logged in. Please login at www.codechef.com to post your questions!

×

CNTHEX - Editorial

PROBLEM LINKS

Practice
Contest

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.

This question is marked "community wiki".

asked 23 Nov '12, 14:08

admin's gravatar image

0★admin ♦♦
14.3k347483501
accept rate: 36%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Tags:

×9,893
×701
×6
×1

Asked: 23 Nov '12, 14:08

Seen: 1,590 times

Last updated: 23 Nov '12, 14:08