Game Of Sticks REN2013I

general
1

i participated in codex and tried solving this problem my solution gave WA .
could someone explain me approach , or provide an editorial to the problem .

2

For this question what we need is basically the maximum area triangle for each and every possible selection of these sticks. Total number of such selections is 2^N where N is number of sticks. Now to get maximum possible area for each selection we have a DP solution. Here we can consider bitmasks to represent each selection and then for each selection calculate the maximum area using the following algorithm

for each stick i in set:

	for each stick j in set:
		for each stick k in set:
			if making a triangle with sticks i,j k is possible and current mask uses i,j,k then
				ans[mask]=max(ans[mask],ans[mask^((1<<i)+(1<<j)+(1<<k))]+area(i,j,k))
		end
	end
end

In the above procedure the array ans[i] will represent maximum ans for ith bitmask. Also ans[mask^((1<<i)+(1<<j)+(1<<k))]+area(i,j,k) represents sum of maximum answer without using sticks i,j,k and area of triangle formed using i,j,k.
repeat above procedure for each bitmask staring from 0. Now if alice gives any area that is not obtained after applying above procedure then AREA NOT POSSIBLE verdict is generated, if global maximum is selected by alice then DRAW other wise BOB WINS.

1 Like
3

The precision issues in this problem were harder to resolve than to come up with an algorithm for the question. :slight_smile:
That was my experience to say the least.

4

for each stick i in set:

for each stick j in set:
    for each stick k in set:
        if making a triangle with sticks i,j k is possible and current mask uses i,j,k then
            ans[mask]=max(ans[mask],ans[mask^((1<<i)+(1<<j)+(1<<k))]+area(i,j,k))
    end
end

end