405621: GYM102012 K Rikka with Ants

Every time when Rikka faces to a great nature sight, she will recall a line of ants moving in a hurry. Rikka loves ants and keeps two large colonies of ants in her drawer. Observing ants hurrying in moving has controlled her life.

That is why she prepares $$$n$$$ different nests in her drawer, and $$$n$$$ undirected channels between these nests form a circular orbit. All nests are numbered by $$$1$$$ to $$$n$$$ in order, and the lengths of channels are known. The first colony of ants is living in the $$$s_1$$$-th nest, and the second colony is living in the $$$s_2$$$-th nest.

Now, ants decide to move to new nests together. The new home for these two colonies of ants will be the $$$e_1$$$-th nest and the $$$e_2$$$-th nest respectively.

For each colony, all ants should queue up one by one to crawl from the origin to the destination along a path. They cannot be split into several groups crawling moving along different paths. Then, they can measure the complexity of their plan moving to new nest using the total length of channels in the path selected.

If these two colonies of ants select paths sharing some common channels, they will walk through these channels slowly for security. Specifically, for each common channel, we can consider equivalently that its measured length will be tripled.

Ants are highly intelligent and they all want to minimize the complexities of their plan. They will choose the best strategies for themselves respectively without negotiation. All they know are the lengths of channels, and the nests where their colony and the other one will start and end respectively.

Rikka wants you to calculate the expected complexities of plans for each colony of ants. For more details about the best strategy, please refer to note.

The input contains several test cases, and the first line contains a single integer $$$T$$$ ($$$1 \le T \le 5000$$$), the number of test cases.

For each test case, the first line contains a single integer $$$n$$$ ($$$2 \le n \le 50$$$), the number of nests and also the number of channels between them.

The second line contains $$$n$$$ integers $$$a_1, a_2, \cdots, a_n$$$ ($$$1 \le a_i \le 50$$$), where the $$$i$$$-th one, $$$a_i$$$, represents the length of the undirected channel between the $$$i$$$-th nest and the $$$((i \bmod n) + 1)$$$-th nest. It is guaranteed that the total length of the $$$n$$$ channels is odd.

The third line contains four integers $$$s_1, e_1, s_2$$$ and $$$e_2$$$ ($$$1 \le s_1, s_2, e_1, e_2 \le n$$$, $$$s_1 \ne e_1$$$, $$$s_2 \ne e_2$$$), representing the original nests where these ants live and their new nests.

For each test case, output a line with two space-separated numbers, representing the expected complexity for the first colony of ant and the expected complexity for the second colony respectively. Your answer is considered correct if the absolute or relative error between each number in your output and the corresponding one in Rikka's answer does not exceed $$$10^{-9}$$$. Formally, let a number of your answer be $$$a$$$, and the corresponding number of Rikka's answer be $$$b$$$. Your answer is considered correct if $$$\frac{|a - b|}{\max(1, |b|)} \le 10^{-9}$$$.

2
5
1 5 2 4 3
1 2 3 4
5
1 5 2 4 3
1 3 2 4

1.000000000000000 2.000000000000000
14.666666666666667 14.666666666666667

What we are talking about including strategies, best strategies and expectations are actually what about Nash Equilibrium and mixed strategies.

In the theory of games, a player is said to use a mixed strategy whenever the player chooses to randomize over the set of available actions. Formally, a mixed strategy is a probability distribution that assigns to each available action a likelihood of being selected. If only one action has a positive probability of being selected, the player is said to use a pure strategy. In the first sample case, the best strategies for both colonies are pure strategies.

A mixed strategy profile is a list of strategies, one for each player in the game. A mixed strategy profile induces a probability distribution or lottery over the possible outcomes of the game. In this problem, the profiles are those plans that we discussed before.

A Nash equilibrium (mixed strategy) is a strategy profile with the property that no single player can, by deviating unilaterally to another strategy, induce a lottery that he or she finds strictly preferable. In $$$1950$$$, the mathematician John Nash proved that every game with a finite set of players and actions has at least one equilibrium.

In this problem, a Nash equilibrium is what you need to find. You may find out several different equilibriums. If some of them have the same unilateral strategy, their earnings must be constant.

We still need to discuss when several different equilibriums without fixed unilateral strategy exist. Notice that in this case, we have a unique equilibrium with mixed, impure strategies. Since ants like to show-off their intelligence, this equilibrium is exactly their final choices.

In the second test case, though we have three different equilibriums whose earnings are $$$(8,10)$$$, $$$(13,11)$$$ and $$$(14.666 \cdots,14.666 \cdots)$$$, the last one is the earnings for the only equilibrium with mixed, impure strategies and thus is what we need.