I was solving this problem Generating sets from the Intel Code Challenge Elimination Round. The editorial doesn't discuss the proof for the idea used. Can anyone help with this? I don't understand the greedy step of why we move the maximum element to the largest possible position.
Also most of the contestants got AC with binary search idea. I considered this idea but couldn't get any head way? I was unable to come up with how to implement a check function which can say whether it is possible to make the maximum $$$\leq x$$$? I read Um_nik's solution and I am unable to figure out why the solution works. Any help is highly appreciated

Here is an interesting problem from the Newton School's June coding competition

Problem: There are $$$x$$$ apples and $$$y$$$ oranges. In one move you can pick an apple or an orange equiprobably and convert it to the other. What is the expected number of moves required to make the count of one of them zero? Constraints $$$0 \leq x, y \leq 10^9$$$

Intended solution: Let $$$E(x , y)$$$ be the expected number of moves with $$$x$$$ apples and $$$y$$$ oranges in the beginning. Quite obviously (or maybe not), we pick apples and oranges with probability $$$\frac{1}{2}$$$ and then we have the following transitions: $$$E(x , y) = 1 + \frac{E(x + 1, y - 1) + E(x - 1, y + 1)}{2}$$$. And also $$$E(x, 0) = E(0 , y) = 0$$$. And probably with a little guess work we can obtain $$$E(x , y) = xy$$$.

A different way: Somehow I interpreted the problem in a different way and landed in a difficult position. I went about thinking that we draw the fruits equiprobably so the probability that we pick up a fruit is $$$\frac{1}{x + y}$$$. This makes the probability that we draw an apple to be $$$\frac{x}{x + y}$$$ and that we draw an orange to be $$$\frac{y}{x + y}$$$. This took me to the following recurrence: $$$E(x , y) = 1 + \frac{x}{x + y}E(x - 1, y + 1) + \frac{y}{x + y}E(x + 1, y - 1)$$$ and that $$$E(x , 0) = E(0 , y) = 0$$$. Now, I want to know if this recurrence has any closed form solution. Are there methods to compute such recursive functions. Maybe some math-person knows how to solve it. Also, how does one even approach this problem with smaller constraints (I mean with $$$dp$$$ we run into cycles)?

I was solving this problem E2.Voting(Hard Version) from Educational Round 75. I found the key idea of the problem somewhat hard to grasp. Also, the editorial doesn't contain the proof of the idea. Although the approach itself is clear but why it should work seems a little hard to think of. So, please solve the problem and share your ideas/proofs about it. How did you come up with the idea or some key observations that led you to solve the problem (need not be rigorous)? Also, this problem allows multiple approaches (looking at neal's submissions).

Consider a segment tree with lazy propagation built on an array. Let it support the following operations $$$f_{update}(l , r)$$$ and $$$f_{query}(l,r)$$$. Here , $$$f_{update}(l , r)$$$ is the range update operation from index $$$l$$$ to $$$r$$$ on the array and $$$f_{query}(l,r)$$$ is the query operation on range $$$l$$$ to $$$r$$$. How to decide mathematically(or intuitively) whether a particular combination of $$$f_{update}$$$ and $$$f_{query}$$$ will work efficiently or not? For instance the following combinations : $$$f_{update}$$$ = $$$increment$$$ $$$each$$$ $$$value$$$ $$$in$$$ $$$interval$$$ $$$by$$$ $$$some$$$ $$$fixed$$$ $$$value$$$ $$$v$$$ and $$$f_{query}$$$ = $$$get$$$ $$$maximum$$$ $$$of$$$ $$$range$$$ works good. However, $$$f_{update}$$$ = $$$take$$$ $$$max$$$ $$$of$$$ $$$each$$$ $$$element$$$ $$$in$$$ $$$l$$$ $$$to$$$ $$$r$$$ $$$with$$$ $$$v$$$ and $$$f_{query}$$$ = $$$get$$$ $$$maximum$$$ $$$of$$$ $$$range$$$ is not that obvious . More formally, what are the conditions that we must check on $$$f_{update}$$$ and $$$f_{query}$$$ to quickly decide whether the combination can be used efficiently or not? Also, if possible please provide some standard combinations that can be done and those that can't.

Can anyone provide links to some codeforces problems on Tries?

Given an array and two types of queries : set a[i] = a[i] xor K, for l <= i <= r for some K and give min over range [l,r]. Can it be done with lazy prop??