I came up with this generic implementation where I just need to write comparator

template <typename T, typename Func>
T bsearch(T start, T end, Func fun, bool debug = false) {
    T mid = start;
    while (true) {
        mid = (end - start) / 2 + start;
        if (debug) {
            cout << "start: " << start << "mid: " << mid << "end: " << end
                 << endl;
        }
        T ret = fun(start, mid, end);
        if (ret == 0 || mid == start || mid == end) {
            break;
        }
        if (ret < 0) {
            end = mid;
        } else if (ret > 0) {
            start = mid;
        }
    }
    return mid;
}

The fun is a lambda which accepts low, mid and high and returns which direction to go next

-1 left
0 exit
1 right

Usage

A submission where I used this
https://www.codechef.com/viewsolution/53343477

MikeMirzayanov I wonder how did you come up with problems like 1607D - Blue-Red Permutation What i mean is how do start thinking while framing a problem (sorry if question is too broad).

why is Retired_MiFaFaOvO not listed in top rated?

I think you are a tourist's fan

I regret for not noticing the contest time. But nice problemset, enjoyed upsolving div2 {a-d}!

You are indeed a mirror :P

Or "them"

Thanks! Fastest rating updates in recent time

How?

My DP solution 133030971 didn't work :( people have tried segment tree and bfs approaches

Kakashi, linear diophantine equations?

Are you aware that you are under Genjutsu :D

A new chunin exams starts today (3:30 IST)! Hope you are still in the game Kakashi!

Same here :D

I used a different approach

131417048

VCS haha

Thanks, hope other posts were also interesting for you.

https://mmpataki.github.io/

I wrote a intro blog about this with an example an year back, you may like it

https://mmpataki.github.io/programming/2020/10/31/insertion-sort-and-sanitizers.html

Hemose Bakry there is unproved part for C. "If you can partition the tree into m components".. how do I prove this?

Can you please help in proving if these (below) are the components with every one of them with xor=x, we can have another set of 3 legal components?

For B I had to wait 4 mins :P, but pre-tests passed

Long Q?

I also came to find proof, but I am going to prove that the given solution is correct. Help me how you derived (your thought process) the solution

assume there are just 3 people and you have sorted then by their max time to talk and time now is $$$t_1$$$

the solution chooses $a_3$ along with $$$a_2$$$ (you can choose anyone with $$$a_3$$$) at $$$t_1$$$

let's assume you instead chose $$$a_2$$$ and $$$a_1$$$, the max time you can involve all these guys is

minimum of $$$a_1$$$ and $$$a_2$$$ + whatever is left with $$$a_2$$$

but if you chose $$$a_3$$$ you can involve them for

I made a mistake of not considering the "picking the next pair" after every unit time :P in my practice and was searching if any one can prove it.

Ritwin please help us with how you derived the solution, thanks!

Agnimandur proof for B please

I wasted 4 submissions because of using int in problem C :(

@Mike what was the RCA

I tried to give n^3 brute-force solution, not sure what tripped it off .100956182

MST on the complete graph and a cheap edge?

Sorry, I meant 'E'

What is '.' doing in D?

My explanation goes something like this

n=4, k=3
A = [a, b, c, d, e, f, g, h, i, j]

we will do exactly `k` iterations, each time picking a median.

sum = 0

iteration 0.
a, b, c, d, e, f, g, h, i, j, k, l
                        \__^_____/

sum += j

now `i` can be replaced with some small numbers which are at the beginning of the original array. If we do so, we have `i` available for next array we are going to create.

iteration 1.
a, b, c, d, e, f, g, h, i, j, k, l
               \__^_____/

sum += g

now again `f` is available for next iteration as it can be replaced with some smaller element from the beginning of the initial array.

iteration 2.
a, b, c, d, e, f, g, h, i, j, k, l
      \__^_____/

sum += d

we are done with `k` iterations. (the elements still on the left also are already used)

print(sum)

98731953

I used a simpler technique (but constraints screwed up my initial submissions, using int instead of long)

My Submission

F looks like greedy to me, but I lack confidence in implementing what I am thinking :D

Just counting and counting and still counting...