0

Need help in a 1700-ish problem

 7 months ago
source link: https://codeforces.com/blog/entry/125717
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client
By bgopc, 3 hours ago, In English

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

Given nn, dd positive integers, and the array aa with length nn
for each ii s. t 1≤i≤n1≤i≤n
Find the maximum j s. t |ai−aj|≤d|ai−aj|≤d

Input format:
Integers n,d: 1≤n≤1e5,1≤d≤1e91≤n≤1e5,1≤d≤1e9
In the next line given nn integers representing a1a1, a2a2, ..., an−1an−1, anan

Output format:
In single line for each 1≤i≤n1≤i≤n output the corresponding jj
if there is no corresponding jj output -1

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

103 minutes ago, # |

← Rev. 2 →  

0

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

  • 95 minutes ago, # ^ |

    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

    • 72 minutes ago, # ^ |

      ← Rev. 2 →  

      0

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

      • 66 minutes ago, # ^ |

        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

        • 40 minutes ago, # ^ |

          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 jj. unless sets are too advanced for you?

        • 11 minutes ago, # ^ |

          ← Rev. 2 →  

          0

          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.

37 minutes ago, # |

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 jj and we want to find all ii s.t. jj is the answer for ii. These ii's values are in range [v[j]−d,v[j]+d][v[j]−d,v[j]+d], so just finding, processing and deleting all such iis suffices. As I understood, the answer for particular ii can never be −1−1, because a[i]−a[i]=0a[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];
  }
}

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK