We were awaiting confirmation from a couple places, hence the delay. The prizes will soon be updated in the blog now

Nice PFP

Hey! If you have any doubts about the questions, you can message me or any of the writers. We will assist you directly. If you feel a more general discussion would be better, you can comment your idea or doubt under this blog :)

Which problem?

For E, you can maintain two sorted multisets $$$m_1$$$ and $$$m_2$$$: $$$m_1$$$ holds all the current elements of $$$a$$$, and $$$m_2$$$ stores the differences between consecutive elements of $$$m_1$$$. Now to make an update:

• Find the elements before and after $$$a[i]$$$ in the $$$m_1$$$, let them be $$$l$$$ and $$$r$$$
• Erase $$$a[i] - l$$$ and $$$r - a[i]$$$ from $$$m_2$$$, insert $$$r - l$$$
• Erase $$$a[i]$$$ from $$$m_1$$$ and insert $$$val$$$ into $$$m_1$$$.
• Now similarly to the first part find the neighboring elements of $$$val$$$ and update $$$m_2$$$ accordingly
• Return the smallest element in $$$m_2$$$

For F, you can maintain a 2D DP array where $$$dp_{i, x}$$$ stores the maximum coop value among the first $$$i$$$ groups only at most $$$x$$$ people can be used from group $$$i$$$. To calculate this, let $$$c_{i, x}$$$ be the maximum coop value we can get in the first $$$i$$$ groups if exactly $$$\min(a_{i-1}, x)$$$ people are used from group $$$i$$$. This can be calculated simply: $$$c_{i, x} = \min(P_i, P_{i-1})\times\min(a_{i-1}, x) + dp_{i-1, P_{i-1} - \min(x, P_{i-1})}$$$. Once $$$c$$$ is calculated, $$$dp_{i, x} = \max_{0\leq j\leq x}(c_{i, j})$$$, which can be done efficiently by taking prefix maximums. The answer will just be $$$dp_{n, a_n}$$$.

For F:
The intuition is that you will decide for a group $$$i$$$ that some $$$j$$$ people that will cooperate with some $$$j$$$ people from group $$$i - 1$$$. This will leave maximum $$$count[i - 1] - j$$$ people to cooperate with the $$$i - 2$$$ group if it exists. This should give you an idea of using a 2D array to store at what group you are going to work at are and how many people from that group to choose.

This code does the same. [submission:256149281].

Since the constraint mentions that the total number of people and groups $$$\le 10^5$$$. Therefore looping over all the people in group is possible as the total iterations are $$$n + \sum_i^n count_i$$$. Also we are only considering $$$i$$$ and $$$i - 1$$$ at any iteration. Therefore, we only use $$$dp$$$ with first dimension 2.

At the end of each iteration of the outer loop($$$i$$$) we copy all elements changed(updation of $$$dp[1]$$$) in the inner loop($$$j$$$) to $$$dp[0]$$$.

just check consecutive numbers where the first number is even

Its saying that A[i] ^ A[j] 's first bit should be 1, i.e. any of the odd-even pair will suffice this condition. Reread the question again, its taking & with 1.

you can maintain set and iterate form 1 to n , for each index find the (1^a[i]) in set if it exist update the answer