I was doing yesterday's division 3 round, when I stumbled upon problem D. I coded together something that frankly shouldn't work but somehow does and didn't fail to hacks either. I was just wondering if anyone could come up with a rigourous(or non rigourous, idrc) proof of why my solution works.
my code: https://codeforces.com/contest/1921/submission/241787069
The way I got this idea was just doing some stuff on paper until I realized that the max diff for each corresponding element could only really be found at two reasonable spots.
Thanks!
Your solution is equivalent to the editorial solution.
Let's call "matching" $$$a[i]$$$ with $$$b[m-i-1]$$$ and $$$b[n-i-1]$$$ as option $$$1$$$ and option $$$2$$$, respectively. The key observation is that if you choose option $$$2$$$ on turn $$$i$$$, then for any $$$k > i$$$ you will always choose option $$$2$$$. We can prove this with induction.
If we chose option $$$2$$$ on iteration $$$i-1$$$, we know that $$$a[i-1]$$$ is closer to $$$b[m-i]$$$ than $$$b[n-i]$$$. As we move from $$$i-1$$$ to $$$i$$$, consider 2 cases:
Case $$$1$$$: $$$a[i] < b[m-i-1]$$$. Since $$$a[i] \geq a[i-1]$$$ and $$$b[m-i-1] \leq b[m-i]$$$, these two values must have gotten even closer together than on the previous iteration, so we still choose option $$$2$$$.
Case $$$2$$$: $$$a[i] \geq b[m-i-1]$$$. Because $$$b[n-i-1] \leq b[m-i-1] \leq a[i]$$$, choosing option $$$2$$$ is obviously the better choice.
This means that we will choose to match with $$$b[n-i-1]$$$ on some suffix and with $$$b[m-i-1]$$$ on some prefix, which is exactly the editorial's solution.
Dang, thank you so much. Two quick questions: 1. Where can I access the editorial? I dont seem to see it anywhere under blog posts. 2. So does that mean that this problem is basically just using two pointers, one pointing to the beginning, and one pointing to the end of arr b, and then strategically choosing which one to use for each corresponding element in arr a?
Apparently, the editorial isn't linked to the problem yet. I found it by looking at the announcement blog on the homepage.
Yes. Refer to the editorial solution for details.
Oh damn, I somehow found the quickest sol by accident. Wish I could pull this off every contest tho...