Блог пользователя Neev4321

Need help with a math problem
Автор Neev4321, история, 5 дней назад, По-английски

I recently came across this blog post and decided to try some of its problems. I am stuck on this problem. I can think of a naive O(n^2) solution by iterating through all pairs but do not see any redundancy in this solution. I cannot see a way to make it sub-quadratic (other than using the fact that 1 ≤ ai ≤ 2.5 * 10^6, maybe?). Any hints would be appreciated.

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
5 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by Neev4321 (previous revision, new revision, compare).

→ Ответить
»
5 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Actually, $$$O(n^2)$$$ is intended, however, not in the way you might think. If I recall correctly, as soon as 4 pairs of the same sum are present, there is always a way to choose 4 different indices among them. For larger n, n^2 solution will end up finding the solution without checking all the pairs, which makes it $$$O(min(n^2, C))$$$, where $$$C$$$ is a large, but not enought to TLE number.

→ Ответить
  • »
    »
    4 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Do you mean that I should randomize the pair selection? Because If one uses a deterministic strategy of going through all pairs and quitting early when a solution if found, you can always create a worst case scenario counter test where there is only a single quadruplet answer and one of the pairs of that quadruplet is the one that you consider last in your strategy.

    → Ответить
    • »
      »
      »
      4 дня назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      that will work good but think about it, in the worst case each pair gives you a different result but you have at most 5e6 possible sums of pairs so that means 5e6 sums to check so its still fast (im ignoring the fact that some of the equal pairs can have common elements but i think it changes the upper bound by not much)

      → Ответить
      • »
        »
        »
        »
        4 дня назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I see now, thx. So, the bound on ai combined with the fact that "as soon as 4 pairs of the same sum are present, there is always a way to choose 4 different indices among them", gives an upper bound of 2 * 10^7.

        → Ответить
»
4 дня назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

after doing a lot of casework, youll be left with a case where all elements will be distinct. now run an (i,0,n)(j,i+1,n) loop some min(n^2, 5* 1e6 + 10) times. if a sum repeats nice. but in 5 * 1e6 iterations if you did not you can only have 5 * 1e6 distinct sums so pigeonhole or common sense any sum after these iterations is a repeat. keep in mind that if you encounter a sum twice, the previous sum indices [x, y] and currently [i, j] x < i && j < y always follows. (sorted distinct elements)

→ Ответить
  • »
    »
    4 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Actually there is no need for casework to remove duplicates, you can incorporate duplicates into your main strategy. Here is my code.

    #include <bits/stdc++.h>
using ll = long long;
using ull = unsigned long long;
using std::cin;
using std::cout;
using std::cerr;
using std::pair;
using std::array;
using std::vector;
using std::bitset;
using std::deque;
using std::queue;
using std::string;
using std::string_view;
using std::priority_queue;
using std::set;
using std::map;
using std::unordered_set;
using std::unordered_map;
using std::min;
using std::max;
using std::sort;
/*
handling of duplicates.
if frequency >= 4, any 4 of them is the answer.
otherwise, it only matters if the frequency is 1 or more than 1.
*/
void preprocess_array(vector<pair<ll, ll>>& a, ll& n){
    sort (a.begin(), a.end());
    vector<pair<ll, ll>> b;
    for (ll i = 0; i < n;){
        ll orig = i, orig_val = a[i].first;
        while (i < n && a[i].first == orig_val) ++i;
        ll freq = i - orig;
        if (freq >= 4){
            cout << "YES\n";
            for (ll j = 0; j < 4; ++j)
                cout << a[orig + j].second + 1 << ' ';
            std::exit(0);
        }
        b.emplace_back(orig_val, a[orig].second);
        if (freq > 1)
            b.emplace_back(orig_val, a[orig + 1].second);
    }
    a = std::move(b);
    n = a.size();
}
/*
check if any two pairs have 4 distinct numbers.
*/
void untangle (const vector<pair<ll, ll>>& occur){
    for (const auto& [i1, i2] : occur){
        for (const auto& [j1, j2] : occur){
            if (i1 != j1 && i1 != j2 && i2 != j1 && i2 != j2){
                cout << "YES\n";
                cout << i1 + 1 << ' ' << i2 + 1 << ' ';
                cout << j1 + 1 << ' ' << j2 + 1 << ' ';
                std::exit(0);
            }
        }
    }
}
static array<vector<pair<ll, ll>>, 5000001> pairs;
int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n;
    cin >> n;
    vector<pair<ll, ll>> a(n);
    for (ll i = 0; i < n; ++i){
        cin >> a[i].first;
        a[i].second = i;
    }
    preprocess_array(a, n);
    for (ll i = 0; i < n; ++i){
        for (ll j = i + 1; j < n; ++j){
            ll sum = a[i].first + a[j].first;
            pairs[sum].emplace_back(a[i].second, a[j].second);
            untangle(pairs[sum]);
        }
    }
    cout << "NO";
}
    → Ответить