-1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Heavier stones may dominate everything below: start from the "big end". $\endgroup$
    – greybeard
    Jul 21 at 7:05
  • $\begingroup$ Is a rock a stone? Is bowl 1 the left bowl or the right bowl? "the left bowl is larger than the right bowl" Do you mean the stone in the left bowl is heavier than the stone in the right bowl? Do you mean all rocks will be split between the two bowls? Does bowl S always contain one rock? $\endgroup$
    – John L.
    Jul 22 at 19:31

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.