Expected Candies

1

How to solve expected candies tht was asked in ICPC Amirtapuri replay contest. Can someone explain its logic.

2 Likes
2

Here is the problem link : CodeChef: Practical coding for everyone

I was able to solve the coloring intervals problem, but maybe due to bad in maths.
i was not able get correct solution to expected candies.

Can anyone tell whats wrong in this approach? or whats the correct approach?

My Approach:

As we can take only first and last element with equal probabilities, i was doing as follows
for i from 0 to i < n/2: ans += 1/2*(a[i] + a[n - i -1]);
and if the elements are odd, i would add the middle element with probability 1,
i.e ans += 1* a[n/2]

My solution : CodeChef: Practical coding for everyone

Thank you :slight_smile:

1 Like
3

My approach was to have two 2-d dp tables. One is dp1[i][j] which denotes expected value that first player gets when the starting array is A[i...j] and dp2[i][j] which is the same but for the second player. We can derive relations between the two easily and after that we can do dp + memoization.
Be careful to use setprecision or you may get a WA.
My submission (AC) : CodeChef: Practical coding for everyone

2 Likes
4

define ans(l, r) = expected sweetness value for range [l, r] for Alice if it’s his turn
and ans2(l,r) = expected sweetness value for range [l, r] for Alice is it’s Bob’s turn. Now,
ans(l,r) = \frac12((a[l] + ans2(l+1, r)) + (a[r]+ans2(l, r-1))
and
ans2(l,r) = \frac12(ans(l+1, r) + ans(l, r-1))

In ans2(l, r) we don’t add a[l] and a[r] because these values contribute to sweetness for Bob not for Alice. So we can think it as 0 contribution for Alice.

2 Likes
5

The probability is not exactly half. For instance with probability 0.5 alice (the first player) chooses the left end value. But with probability 0.5*0.5 she chooses it in second turn etc etc.
So you must use dp to get the probabilities if you do this way.

1 Like
6

Wow, i saw that you solved that root tree one and Polygon one.

Great buddy!
HOWRUSOGOOD?

Thanks for the explanation though.

2 Likes
7

Thanks @anon25504910 @anon2040365

2 Likes
8

Hey, @anon25504910, @vichitr
Can you guys explain the logic behind this problem : CodeChef: Practical coding for everyone

I think we have take maximum degree node as the root node and than write the recursive function and to it’s the children the one having maximum degrees until all nodes are not finished.

Can you guys share your approach?

1 Like
9

The idea we used is: Build the original tree from the ancestor graph. Then check if it’s a valid tree and it produces the same ancestor graph or not. If yes then output the tree in given format. To build the original tree T from ancestor graph G -> The node with maximum degree in G must be the root of T. (Why? Because root will have edge to each node in G. It’s ancestor of all the nodes.) Decrease the degrees of all the nodes connected to root. Now if we have root, find it’s direct childs. The nodes with highest degree connected to root in G are direct childs of root. Keep doing this recursively. This can be done using recursion or a simple while loop.

1 Like
10

Ohh so my thinking was in right direction.
Thanks again bro :slight_smile:

11

Yeah man! Don’t forget to check the validity. Idea was the same.

1 Like
12

My approach : Make the node with max degree as root and mark it. After this, decrease degree of neighbors not marked yet by 1. Go through the neighbors in decreasing order of degree and repeat, marking them and (skipping them if they’re marked) continuing the dfs. Also, the dfs func returns degree (which change as when a node is marked its unmarked neighbors’ degree reduces by 1)
check that every node’s degree = sum(1 + degree of child) over all children. If not then fail; else you have the tree.

1 Like