Weigher problem

Question

I got interested in one problem. I have $N$ rocks, where rock with minimum weight have number equal to $1$, the next heaviest stone has a number equal to 2, etc..

So a rock with maximum weight have a number equal to $N$. And I have $N$ requests, each of N request contains two integers: $R$ $(1≤R≤N)$ and $S$ $(1≤S≤2)$. $R$ is the number of the stone that will be placed on the bowl $S$. All $R$ are different.

For each request I return $>$ if the left bowl is larger than the right, $<$ if the right bowl is larger than the left, $?$ if isn't possible determine that is bowl larger.

Constraint on $N$ is $(N < 10^5)$

For example, for input:

5
1 2
3 1
2 1
4 2
5 1

output is:

<
>
>
?
>

I have no idea whatsoever how to solve this problem. But I wonder, that segment tree can be helpful, but I could not develop my idea.

Answer 1

Here some progress. I'm assuming that no two rocks have the same weight.

We model a generic bowl as as set $X\subseteq \{1,\dots, N\}$ whose elements are the indices of the stones contained in the bowl. Let $n(i,X)$ denote the $i$-th largest index in $X$. If $X$ contains less than $i$ stones, let $n(i,X) = 0$. Let $w(i)$ denote the weight of the stone with index $i$, and define $W(X) = \sum_{i \in X} w(i)$.

Claim: Bowl $A$ is certainly heavier than bowl $B$ if and only if $n(i,A) > n(i,B)$ for all $i=1,\dots, |B|$.

Proof of the "if" direction. Notice that $n(|B|,A) > n(|B|, B) \ge 1$ and hence $|A| \ge |B|$. Then: $$ W(A) = \sum_{i=1}^{|A|} w(n(i,A)) \ge \sum_{i=1}^{|B|} w(n(i,A)) > \sum_{i=1}^{|B|} w(n(i,B)) = W(B). $$

Proof of the "only if direction". Let $i^*$ be an index such that $1 \le i^* \le |B|$ and $n(i^*,A) < n(i^*,B)$ and consider the following weight assignment:

• For $j < n(i^*,B)$, $w(j) = N - j$.
• For $j \ge n(i^*,B)$, $w(j) = N^2 - j$.

We have: $$ \begin{align*} W(A) - W(B) &\le \sum_{i=1}^{i^*-1} \bigg( w(n(i, A)) - w(n(i, B)) \bigg) + \sum_{i=i^*}^{|A|} w(n(i, A)) - w(n(i^*,B))\\ & \le (i^* -1) N + (|A|-i^* + 1) N - (N^2 - N) \\ & \le |A| \cdot N + N - N^2 \\ & \le (N-1)N - N^2 < 0. \end{align*} $$

Therefore the problem boils down to pairing stones from the two bowl in decreasing order of weight, and checking whether each stone from one bowl is larger than the matching stone in the other bowl.