Zadane The BOSS Can Count Pairs Codeforces

Question

Mam problem z takim zadaniem: https://codeforces.com/problemset/problem/1830/B

Nie wiem jak zrobić szybciej niż O(N^2). Zastanawiałem się nad sqrt, ale nic nie wymyśliłem. Bardzo byłbym wdzięczny za hinta.

Z góry dzięki!

Answer 1

Kluczową obserwacją jest ograniczenie na min(a_i, a_j) dla dowolnej pary (i, j).

Comments

Wsumie mogą tu wchodzić sumy harmoniczne.

---

Niestety nie, a przynajmniej nie wiem jak nimi to rozwiązać

---

Wiemy, że min(A[i], A[j]) <= sqrt, czyli teoretycznie możemy dla każdej z sqrt wartości sprawdzać N liczb.

---

Dobry pomysł

---

Mam coś takiego:

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;
typedef long long ll;

ll q = 0, n = 0, k = 450, ile_rownych = 0;
ll wyn = 0;
vector<ll> A;
vector<ll> B;
vector<vector<ll>> wystapienia;
vector<ll> ile_mamy;
vector<ll> idx_poprzedniej;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);


    cin >> q;
    while(q--)
    {
        cin >> n;
        A.assign(n,-1);
        for (int i = 0; i < n; ++i)
            cin >> A[i];
        B.assign(n,-1);
        for (int i = 0; i < n; ++i)
            cin >> B[i];

        wystapienia.assign(n+1,{});
        for (int i = 0; i < n; ++i)
            wystapienia[A[i]].push_back(B[i]);

        ile_mamy.assign(n+1,0);
        idx_poprzedniej.assign(n+1,-1);

        wyn = 0;
        for (int i = 1; i <= min(n,k); ++i)
        {
            for (int j = 0; j < wystapienia[i].size(); ++j)
            {
                int val = wystapienia[i][j];
                if (idx_poprzedniej[val] != i)
                {
                    idx_poprzedniej[val] = i;
                    ile_mamy[val] = 1;
                }
                else
                    ile_mamy[val]++;
            }
            for (int j = 0; j < n; ++j)
            {
                if (A[j] <= i)
                    continue;
                ll iloczyn = i * A[j], ile_zostalo = iloczyn - B[j];
                if (ile_zostalo <= 0 or ile_zostalo > n)
                    continue;
                if (idx_poprzedniej[ile_zostalo] == i)
                {
                    wyn += ile_mamy[ile_zostalo];
                }
            }
        }

        ll do_dodania = 0;
        for (int i = 1; i <= n and i * i <= 2*n+1; ++i)
        {
            if (wystapienia[i].size() <= 1)
                continue;
            map<int,int> stat;
            for (int j = 0; j < wystapienia[i].size(); ++j)
            {
                int val = wystapienia[i][j];
                if (auto it = stat.find(val) != stat.end())
                    stat[val]++;
                else
                    stat[val] = 1;
            }
            for (int j = 0; j < wystapienia[i].size(); ++j)
            {
                int val = wystapienia[i][j], ile_brakuje = i*i - val;
                if (auto it = stat.find(ile_brakuje) != stat.end())
                {
                    if (ile_brakuje == val)
                        do_dodania += stat[ile_brakuje]-1;
                    else
                        do_dodania += stat[ile_brakuje];
                }
            }
        }
        wyn += do_dodania / 2;
        cout << wyn << '\n';
    }

    return 0;
}

Ogołnie działa dobrze, ale na max tescie daje lekko za małe odpowiedzi. Chyba już 1,5h to debuguje i nwm co nie dziala.

---

tak czytam ten kod i nie widzę błędu. Muszę napisać sprawdzarkę.

---

Napisałem sprawdzarkę, z brutem O(N^2), i na testach N = 1000 daje poprawne odpowiedzi na wszystkich, bardzo dużo testach

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;
typedef long long ll;

ll q = 0, n = 0, k = 450;
ll wyn = 0;
vector<ll> A;
vector<ll> B;
vector<vector<ll>> wystapienia;
vector<ll> ile_mamy;
vector<ll> idx_poprzedniej;

ll N = 0;
vector<ll> gen_A, gen_B;

inline int rnd(int l, int p)
{
    return rand() % (p-l+1) + l;
}

inline void generuj()
{
    srand(time(0));
    N = rnd(1,1000);
    gen_A.assign(N,-1);
    for (int i = 0; i < N; ++i)
        gen_A[i] = rnd(1,N);
    gen_B.assign(N,-1);
    for (int i = 0; i < N; ++i)
        gen_B[i] = rnd(1,N);
}

inline void wypisuj()
{
    cout << N << '\n';
    for (int i = 0; i < N; ++i)
        cout << gen_A[i] << " ";
    cout << '\n';
    for (int i = 0; i < N; ++i)
        cout << gen_B[i] << ' ';
    cout << '\n' << '\n';
}

inline ll brut()
{
    ll res = 0;
    n = N;
    A = gen_A, B = gen_B;
    for (int i = 0; i < n; ++i)
        for (int j = i+1; j < n; ++j)
            if (A[i] * A[j] == B[i] + B[j])
                res++;
    return res;
}

inline ll wzo()
{
    n = N, A = gen_A, B = gen_B;
    wystapienia.assign(n+1,{});
    for (int i = 0; i < n; ++i)
        wystapienia[A[i]].push_back(B[i]);

    ile_mamy.assign(n+1,0);
    idx_poprzedniej.assign(n+1,-1);

    wyn = 0;
    for (int i = 1; i <= min(n,k); ++i)
    {
        for (int j = 0; j < wystapienia[i].size(); ++j)
        {
            int val = wystapienia[i][j];
            if (idx_poprzedniej[val] != i)
            {
                idx_poprzedniej[val] = i;
                ile_mamy[val] = 1;
            }
            else
                ile_mamy[val]++;
           }
        for (int j = 0; j < n; ++j)
        {
            if (A[j] <= i)
                continue;
            ll iloczyn = i * A[j], ile_zostalo = iloczyn - B[j];
            if (ile_zostalo <= 0 or ile_zostalo > n)
                continue;
            if (idx_poprzedniej[ile_zostalo] == i)
            {
                wyn += ile_mamy[ile_zostalo];
            }
        }
    }

    ll do_dodania = 0;
    for (int i = 1; i <= n and i * i <= 2*n; ++i)
    {
        if (wystapienia[i].size() <= 1)
            continue;
        map<int,int> stat;
        for (int j = 0; j < wystapienia[i].size(); ++j)
        {
            int val = wystapienia[i][j];
            if (auto it = stat.find(val) != stat.end())
                stat[val]++;
            else
                stat[val] = 1;
        }
        for (int j = 0; j < wystapienia[i].size(); ++j)
        {
            int val = wystapienia[i][j], ile_brakuje = i*i - val;
            if (auto it = stat.find(ile_brakuje) != stat.end())
            {
                if (ile_brakuje == val)
                    do_dodania += stat[ile_brakuje]-1;
                else
                    do_dodania += stat[ile_brakuje];
            }
        }
    }
    wyn += do_dodania / 2;
    return wyn;
}

inline void testuj()
{
    while(true)
    {
        generuj();
        //cout << wzo() << " " << wzo() << " " << brut() << " " << brut() << endl;
        if (wzo() != brut())
            break;
        cout << "t" << '\n';
    }
    wypisuj();
}

int main()
{
    //ios_base::sync_with_stdio(0);
    //cin.tie(0);
    //cout.tie(0);

    testuj();

    return 0;
}

bardzo dziwne

---

Pierwiastek jest za mały. Powinno być sqrt(4*1e5)

---

no i jest ac, dzięki za pomoc!