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

×

Hackenbush

2
1

please somebody help me to understand how game value is calculated in game like hackenbush(for reference question CHEFGM asked in november long challenge can be taken)

asked 12 Nov '13, 18:30

zealf's gravatar image

4★zealf
1.1k61126
accept rate: 3%


The game given in the problem CHEFGM can be reduced to blue-red Hackenbush game. There are two types of hackenbush games: hackenbush stalk and hackenbush trees(there may be more). For the problem we are concerned with Hackenbush stalks since all piles are independent of each other. First we assign sign to the two possible moves, say even is taken as positive and odd as negative. The piles are arranged in such a way that removing any element would mean removing all elements that are placed above it in the same pile. For this, we sort the piles and remove duplicates.

Consider an example: This is the pile for which we want to calculate the value

10

7

5

4

2

We start from the lowest level and go up. The first number will get the value +1 or -1 depending upon whether it is even or odd. Here 2 gets +1. Now as we go up we assign +1 to every number till we encounter an odd number ie. all consecutive even numbers starting from the ground will be assigned +1. So 4 also gets +1. Now when the first odd number is reached, every number will be assigned half the value that was assigned to the number just below(along with the sign). So 5 gets -1/2 , 7 gets -1/4 , 10 gets +1/8.

10.......+1/8

7........-1/4

5........-1/2

4........+1

2........+1

So the total value of the pile becomes +1+1-1/2-1/4+1/8 = 11/8.

Another example:

10....+1/16

9.....-1/8

8.....+1/4

6.....+1/2

5.....-1

3.....-1

1.....-1

Total value is -1-1-1+1/2+1/4-1/8+1/16 = -37/16.

This way we calculate the value of all piles and add them. Now if the total sum comes out to be positive, then it means that if the first player chose even, he/she will always win the game. If this sum is negative, then it means odd is winning choice. And if it is 0 then it means the first player can never win. You can refer to my solution http://www.codechef.com/viewsolution/2974201

link

answered 12 Nov '13, 19:47

sikander_nsit's gravatar image

5★sikander_nsit
1.5k82130
accept rate: 0%

1

@sikander_nsit the place where i am getting confused is how we can assign such values to these numbers

(12 Nov '13, 21:33) zealf4★

See the link put up by @nitinj.

(12 Nov '13, 22:21) wittyceaser2★
1

@sikander_nsit approach to solve for hackenbush trees??

(13 Nov '13, 00:34) zealf4★

I didn't read much about hackenbush trees. But I think it is an NP-Hard problem.

(13 Nov '13, 05:01) sikander_nsit5★

Hey, Check out this link. Has beautiful description of both partisan and non partisan games including hackenbush

http://is.muni.cz/th/325040/fi_b/Combinatorial_games.pdf

link

answered 12 Nov '13, 19:26

nitinj's gravatar image

5★nitinj
2.2k112027
accept rate: 5%

I exactly had the same problem when I started reading Hackenbush. Have a look at this question http://math.stackexchange.com/questions/556014/what-is-worth-of-a-stalk-in-red-blue-hackenbush

link

answered 13 Nov '13, 03:54

technophyle's gravatar image

2★technophyle
66115
accept rate: 0%

edited 13 Nov '13, 03:56

Thank you! @sikander_nsit and @nitinj

link

answered 12 Nov '13, 21:25

wittyceaser's gravatar image

2★wittyceaser
3.4k194377
accept rate: 16%

1

@wittyceaser Please accept the answer if it solves your doubt

(13 Nov '13, 00:48) kcahdog3★

Hare on this http://www.essayhell.org/ link is the great discussion about Hackenbush that would be really interesting and useful. The number of professionals is having great programming skills and they also help others to give the solution of the problem. Hope the above answers are useful and help a lot to make things correct.

link

answered 23 Apr '17, 20:23

gloriah100's gravatar image

0★gloriah100
-1
accept rate: 0%

toggle preview
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

Question tags:

×140
×33

question asked: 12 Nov '13, 18:30

question was seen: 5,763 times

last updated: 23 Apr '17, 20:23