I believe it is because they are asking you to place fishes such that a random net has the highest expected value. In the given example, the expected value is 2 because there are 4 possible net positions and those net positions capture 8 fish --> Expected value = (total fish) / (net positions) = 8/4 = 2.

If you place the fish like you said at (1,1) (2,1) (2,2) it is true that the first net position (top left) will contain three fish. However, you will see that because of this the other net positions will contain 1, 2, and 1 fish. Then total fish = 3 + 1 + 2 + 1 = 7. Expected value = 7/4 which is less than 2 so this placement is not maximizing the expected value.

The problem statement says you are not allowed to put more than one fish per cell.

Am I getting this logic right for Problem B?

1. Realize that we can find the numbers divisible by x in [l, r] by using the formula r/x — (l — 1)/x. Its (l — 1) to prevent an off by one error when l % x == 0.
2. Sort the array (in ascending order).
3. Iterate through the array and take a[i] to be the left bound. Since we are given a left bound we can find the lowest and highest indices that still satisfy the eq given in step 1. (use binary search at this step?)
4. Knowing the indices we can calculate the actual number of valid right bounds for every left bound and we have our answer.

Is this logic correct? I think I am still getting TLE because I am not using Binary Search. I got a bit lost in the editorial starting at step 3.

Thanks, your explanation was very clear. I'm still having trouble with the "Every component will be a connected group" part. How do you represent these groups? For example if 1 is friends with 2 3 4, then my adjacency lists look like:

• 1 : [2, 3, 4]
• 2 : [1]
• 3 : [1]
• 4 : [1]

But if I DFS starting with every node, I will find the minimum, but I will be quadruple counting this one group. Sorry if this seems silly, I am pretty new to graph problems.

Can someone elaborate on solving Problem C. I understand that if we find the minimum of each group, it will give us the minimum gold in order to spread the rumor. However, how can we turn the list of pairings we are given as inputs into groups?

whups, what a silly mistake, thanks!

For Problem B:

I have read and understood the editorials and I am trying to implement the solution but am getting the wrong answer, can someone assist me. Here is my logic:

• if k is -1 and parity is different, the answer is 0
• if either n or m is 1 then the answer is 1
• otherwise, we can calculate the number of unique boards using 2 ^ [(n-1) * (m-1)] since the nth row and mth column will be determined by the rest of the board

Is there something wrong with this logic? edge cases? I have been trying for a few hours now and I can't figure out whats wrong.