Behrad.'s blog

Need help in a 1700-ish problem
By Behrad., 10 months ago, In English

Hello, CF community, I found this 1700*-ish problem, can somebody help?

Given $$$n$$$, $$$d$$$ positive integers, and the array $$$a$$$ with length $$$n$$$
for each $$$i$$$ s. t $$$1 \leq i \leq n$$$
Find the maximum j s. t $$$\vert{a_i - a_j}\vert \leq d$$$

Input format:
Integers n,d: $$$1 \leq n \leq 1e5, 1 \leq d \leq 1e9$$$
In the next line given $$$n$$$ integers representing $$$a_1$$$, $$$a_2$$$, ..., $$$a_{n-1}$$$, $$$a_n$$$

Output format:
In single line for each $$$1 \leq i \leq n$$$ output the corresponding $$$j$$$
if there is no corresponding $$$j$$$ output -1

I'd appreciate a solution without any kind of advanced data structure(___Trees, ___Arrays, etc)
Thanks for any help

  • Vote: I like it
  • -19
  • Vote: I do not like it

»
10 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

For all ai, Find max j where aj is (> ai and <= ai + d) and( < ai and >= ai — d ).

You can use binary search for this

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You know you can't run binary search on a random array with no logic? and if you know a way please provide me code and I'll try to understand it, thx

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      store the array with index then sort, then use binary search to find the range. then max j in that range using segment tree

      → Reply
      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        As I mentioned earlier in the blog, I don't know any advanced data structures including segment trees, and I don't believe in knowing one until I'm not around 1900 and I believe every question can be solved without them(and it worked out better than you're strategy, knowing one)

        So any other solution without a segment tree be helpful thx again

        → Reply
        • »
          »
          »
          »
          »
          10 months ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          just replace the segment tree with two pointers (since ranges will be increasing as you move left to right) and maintain a set of values. From that set, you can get the maximum $$$j$$$. unless sets are too advanced for you?

          → Reply
        • »
          »
          »
          »
          »
          10 months ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          Not knowing is fine, but refusing to know until reaching some level is stupid. It's reasonable to not want to spend time learning it, but refusing to ponder specific solutions paths will only hinder you from having more creative and exploratory thought process. Instead try to find any solution path while considering what things that seem reasonably possible you aren't sure of, then ask yourself how to do or how to simplify those parts of it (or eventually consider it's wrong approach).

          Also segment tree is not advanced in itself, it is basically just writing out all possibilities of binary search.

          lopital24's idea with two pointers is what I would do tho.

          → Reply
          • »
            »
            »
            »
            »
            »
            10 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            About that, It's basically for INOR. Hard to explain, but just wanna tell you that I've wanted to learn it maybe 10 times? but the INOI thing stopped me, so yep, I'll wait for that time

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              10 months ago, # ^ |
              ← Rev. 2   Vote: I like it 0 Vote: I do not like it

              Well you can see right here, instead of disregarding segtree, if you reduced to "i need max under range with these conditions" and continued thinking various possibilities, you would've got to the two pointer idea. But instead you dismissed lauhemahfus's approach completely.

              My point is not you need to learn, but considering applying or using parts of ideas even outside the scope of whatever contest you're working towards can be a stepping stone towards a simpler solution. The goal is to figure out the fundamental steps to get to a solution, not just going through and trying to modify whole solution of different problems you've seen.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                10 months ago, # ^ |
                  Vote: I like it +8 Vote: I do not like it

                I see, thanks for the advice and your time
                (I'll actually listen)
                yeah maybe lately I've been focusing on solving the problems instead of thinking/enjoying them which caused this. Now I don't go deep into a solution, if it has a unfigured out part, I'll Just skip to the next idea
                Thanks, it was a needed realization

                → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

We can scan through given array from right to left, supporting set of indices, answer for which has not been found yet.
Let's suppose we are now in index $$$j$$$ and we want to find all $$$i$$$ s.t. $$$j$$$ is the answer for $$$i$$$. These $$$i$$$'s values are in range $$$[v[j] - d, v[j] + d]$$$, so just finding, processing and deleting all such $$$i$$$s suffices. As I understood, the answer for particular $$$i$$$ can never be $$$-1$$$, because $$$a[i] - a[i] = 0$$$. 

void RunCase([[maybe_unused]] int testcase) {
  int n;
  int d;
  std::cin >> n >> d;

  std::vector<int> v(n);
  for (int& i : v) {
    std::cin >> i;
  }

  // (value, index)
  std::set<std::pair<int, int>> active;
  for (int i = 0; i < n; ++i) {
    active.emplace(v[i], i);
  }

  std::vector<int> ans(n);
  std::iota(ans.begin(), ans.end(), 0);
  for (int i = n - 1; i >= 0; --i) {
    auto it = active.lower_bound(std::pair(v[i] - d, -1));
    while (it != active.end() && it->first <= v[i] + d) {
      ans[it->second] = i;
      it = active.erase(it);
    }
  }

  for (int i = 0; i < n; ++i) {
    std::cout << ans[i] + 1 << " \n"[i == n - 1];
  }
}
→ Reply