A.
the only case in which the mex is better than the other choice is when the subset is made up of 0 (which will be 1).

approach: sum up all the elements except when it is a 0 add 1.

B.

the array is made up of at least one (0, 1, 2). and only consists of (0, 1, 2).

if tot sum of the array is greater than s, then it fulfilled a case where the sum doesn't equal s, so we should output the array.

then if s % the tot is equal to 0, then that means by repeating some amount of time, the other person can get the sum to equal s. thus we should output -1

the last case is when tot < s,

So in this case, we should consider that for our sum to equal s, we have to take the tot, which means touching every element once + taking some segments more than that. the question says that the sum is considered, when we reach the last item, thus from this we establish that, to repeatedly add some elements, we have to at least take two consecutive indices.

for eg, let's say we have [0, 1, 2, 1]
then if I wanted to repeatedly add 1, I can start from index 0 and stop at index 1, because if I move to the left I always have to move to right, since we always should end up at the last item.

based on this here are some numbers in which the sum can be,
if we take (0, 1) -> 1, (1,2) -> 3, (0, 2) -> 2, and the possible necessary combinations: (0, 1, 2), I can get 1 and 3 from this.
(0, 2, 1), I can get 2 and 3 from this.
(1, 0, 2), I can get 1 and 2 from this.

so I always get two choices, right and If I choose the case where I get 1, then I can repeat 1 as many times as I want and I can reach the sum I want.

so the only case in which I can't get the sum I want is when the sum I want is 1 and the array I have is [0,.....,0,2,....,2,1,...,1], in any other case I ( they as per the question since I'm trying to create a case in which the one who does the sum fails), can always get the sum I want.


C.

why don't we consider this, if the difference between a and b is large, I can get a lot of numbers for the first case, also if they are not in any cycle, when we do the second case, that means I got the maximum possible difference between f(s) and g(s),

the solution can be found by being greedy,

Sort the tuples, in descending order based their difference, then one by one build a graph, and if the current tuple creates a cycle in the graph, skip it. ( we can use UnionFind for this), else append the index of the current tuple in the original given order to the output array.


D.

understood it. I took some time to come up with approaches, but couldn't
some rant


and when I checked the time, it was around 1:00 L.T. and I thought there is only 30 minutes left. then gave up and went for dinner, by the time I come back to check the standings, it says 11 min left. turns out the contest was 3 hours long, not like 2 hours as the usual. still didn't solve it.


#contest_analysis


what about your approaches?

can you solve it?

omarchy has gotten a new update.

read the docs.

A.
the only case that satisfies this condition for all elements is: MEX(ai,ai+1,ai+2) = MAX(ai, ai+1, ai+2) - MIN(ai,ai+1,ai+2) = 0.

thus for the answer to be yes all the numbers must be the same and that number should be > 0.


B.

consider this, the second player teleports to the nearest wall in either direction if there is no wall on that direction he escapes.

approach:
if initially there is no wall or the person is at the start or at the end, then it will take him 1 day.

else the first person can choose either direction from the second person to put a wall and either case he will choose the one that is the nearest to the second person.

so based on that, the answer is going to be :
left_tot = count starting from the first until we reach the wall that is nearest to the second person.
right_tot = count starting from the end until we reach the wall that is nearest to the second person.
left_extra = the space between the left nearest wall and the second person.
right_extra = the space between the right nearest wall and the second person.

MAX(MIN(left_tot, right_tot + right_extra), MIN(right_tot, left_tot + left_extra)) + 1

when we add the `extra`s, we are saying the first person chooses that side and the second person is choosing the way which results the minimum day.

and then when we choose the maximum out of both, we are saying the first person won't let the second person leave with the minimum.

we are adding 1. because the first person always adds a wall, thus the second person has to remove that wall and wait until the next day to decide. therefore there is always a day he has to wait.

C.
couldn't do it.

#contest_analysis

A.
straight forward. no explanation

B.
there are two operations 1. add a ball to the bag 2. pop out the smallest ball out of the bag.

use priority queue (heap)

C.
the optimal position to be is at the center.
then we just have to find the center and the time it takes to get there.
on the x-coordinate the center can be found using the minimum and maximum values found out of the x-coordinates.
on the y-coordinate, we can just use the same technique.

then which ever coordinate takes the longest to reach their center is the answer.

D.
we are given two same length strings. and we have to swap characters between some segments with the two strings. we have to return the first string after all the swap operations are done.

we can use a prefix sum to accumulate the swaps and do just one swap at the end.
after we have the prefix sum, we will do the swap for the indices that we have to swap and return the first string.

#contest_analysis

https://mrinalxdev.github.io/mrinalxblogs/blogs/system-design.html
system design