two pointers - Codeforces

→ Обратите внимание

До соревнования
Educational Codeforces Round 168 (Rated for Div. 2)
16:08:00
Зарегистрироваться »

→ Трансляции

CF Edu Round 168 Solution Discussion

aryanc403

До начала 18:12:59

Codeforces Educational Round 168 - Solution Discussion

Shayan

До начала 18:12:59

Всё →

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	3947
2	ecnerwala	3654
3	jiangly	3627
4	jqdai0815	3621
5	orzdevinwang	3612
6	Benq	3587
7	Radewoosh	3582
8	Geothermal	3569
8	cnnfls_csy	3569
10	ksun48	3474

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	awoo	162
2	maomao90	160
3	adamant	156
4	maroonrk	153
5	atcoder_official	152
6	-is-this-fft-	148
6	SecondThread	148
8	Petr	147
9	nor	145
10	cry	144

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

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

two pointers

Автор vlade087, 11 лет назад, По-английски

Hello anybody can say me what mean when the problem have a tag two pointers. What mean this approach?

two pointers

vlade087
11 лет назад
4

Комментарии (4)

Написать комментарий?

rlac

11 лет назад, # |

Look here

→ Ответить

baukaman

11 лет назад, # |

One of the recent problems involving two pointers is problem I:Pirate Chest from ICPC world finals 2013

This problem reduces to one-dimensional case: in integer array, for each element you want to find element that is lower than current on the left and right sides.

For every element you keep left and right positions for the element which is less than this element. (initially set to itselft). Iterate over descendant sorted array and update your info about pointers.

The problem's time limit pretty large. But involving some other NlogN approaches (such as fenwick tree) gives TL. By pointers you achieve lower constant.

→ Ответить

Among_Us_2008

2 недели назад, # |

← Rev. 2 →

+10

→ Ответить

Kamado_Tanjiro_2008

5 часов назад, # ^ |

Two pointers is really an easy and effective technique that is typically used for searching pairs in a sorted array. Given a sorted array A (sorted in ascending order), having N integers, find if there exists any pair of elements (A[i], A[j]) such that their sum is equal to X.

Illustration :

Let us do discuss the working of two pointer algorithm in brief which is as follows. The algorithm basically uses the fact that the input array is sorted. We start the sum of extreme values (smallest and largest) and conditionally move both pointers. We move left pointer ‘i’ when the sum of A[i] and A[j] is less than X. We do not miss any pair because the sum is already smaller than X. Same logic applies for right pointer j.

Code

#include <bits/stdc++.h>

using namespace std;

bool isPairSum(int A[], int N, int X)
{
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            // as equal i and j means same element
            if (i == j)
                continue;

            // pair exists
            if (A[i] + A[j] == X)
                return true;

            // as the array is sorted
            if (A[i] + A[j] > X)
                break;
        }
    }

    // No pair found with given sum.
    return false;
}

// Driver code
int main()
{
    int arr[] = { 2, 3, 5, 8, 9, 10, 11 };
    int val = 17;
    int arrSize = *(&arr + 1) - arr;
    sort(arr, arr + arrSize); // Sort the array
    // Function call
    cout << isPairSum(arr, arrSize, val);

    return 0;
}

Time Complexity: O(n2). Auxiliary Space: O(1)

Lets solve EDU problem:

step 1:

Merging Arrays

Code

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<int> v1, v2, v3;

int main() {
    scanf("%d%d", &n, &m);
    v1.resize(n);
    for (auto &x : v1) scanf("%d", &x);
    v2.resize(m);
    for (auto &x : v2) scanf("%d", &x);
    int p1 = 0, p2 = 0;
    while (p1 < n || p2 < m) {
        if (p1 == n) v3.push_back(v2[p2++]);
        else if (p2 == m) v3.push_back(v1[p1++]);
        else if (v1[p1] < v2[p2]) v3.push_back(v1[p1++]);
        else v3.push_back(v2[p2++]);
    }
    for (auto x : v3) printf("%d ", x);
    return 0;
}

Number of Smaller

Code

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<int> v1, v2;

int main() {
    scanf("%d%d", &n, &m);
    v1.resize(n);
    for (auto &x : v1) scanf("%d", &x);
    v2.resize(m);
    for (auto &x : v2) scanf("%d", &x);
    int p1 = 0;
    for (auto x : v2) {
        if (x <= v1[0]) {
            printf("0 ");
            continue;
        }
        while (p1 < n && v1[p1] < x) ++p1;
        printf("%d ", p1);
    }
    return 0;
}

Number of Equal

Code

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<int> v1, v2;

int main() {
    scanf("%d%d", &n, &m);
    v1.resize(n);
    for (auto &x : v1) scanf("%d", &x);
    v2.resize(m);
    for (auto &x : v2) scanf("%d", &x);
    int p1 = 0, p2 = 0;
    long long ans = 0;
    while (p1 < n && p2 < m) {
        if (v1[p1] == v2[p2]) {
            int num1 = 1, num2 = 1;
            ++p1;
            while (p1 < n && v1[p1] == v1[p1 - 1]) ++num1, ++p1;
            ++p2;
            while (p2 < m && v2[p2] == v2[p2 - 1]) ++num2, ++p2;
            ans += 1ll * num1 * num2;
        } else if (v1[p1] < v2[p2]) {
            ++p1;
            while (p1 < n && v1[p1] == v1[p1 - 1]) ++p1;
        } else if (v1[p1] > v2[p2]) {
            ++p2;
            while (p2 < m && v2[p2] == v2[p2 - 1]) ++p2;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

step 2:

Segment with Small Sum

Code

#include <bits/stdc++.h>

using namespace std;

int n;
long long s;
vector<int> v;

int main() {
    scanf("%d%lld", &n, &s);
    v.resize(n);
    for (auto &x : v) scanf("%d", &x);
    int l = 0, ans = 0;
    long long sum = 0;
    for (int i = 0; i < v.size(); ++i) {
        sum += v[i];
        while (sum > s) {
            sum -= v[l++];
        }
        ans = max(ans, i - l + 1);
    }
    printf("%d\n", ans);
    return 0;
}

Segment with Big Sum

Code

#include <bits/stdc++.h>

using namespace std;

int n;
long long s;
vector<int> v;

int main() {
    scanf("%d%lld", &n, &s);
    v.resize(n);
    for (auto &x : v) scanf("%d", &x);
    int l = 0, ans = n + 1;
    long long sum = 0;
    for (int i = 0; i < v.size(); ++i) {
        sum += v[i];
        if (sum < s) continue;
        while (sum >= s) {
            sum -= v[l++];
        }
        ans = min(ans, i - l + 2);
    }
    if (ans > n) ans = -1;
    printf("%d\n", ans);
    return 0;
}

Number of Segments with Small Sum

Code

#include <bits/stdc++.h>

using namespace std;

int n;
long long s;
vector<int> v;
vector<long long> v2;

int main() {
    scanf("%d%lld", &n, &s);
    v.resize(n);
    for (auto &x : v) scanf("%d", &x);
    int l = 0;
    long long sum = 0, ans = 0;
    for (int i = 0; i < v.size(); ++i) {
        sum += v[i];
        while (sum > s) sum -= v[l++];
        ans += i - l + 1;
    }
    printf("%lld\n", ans);
    return 0;
}

Number of Segments with Big Sum

Code

#include <bits/stdc++.h>

using namespace std;

int n;
long long s;
vector<int> v;

int main() {
    scanf("%d%lld", &n, &s);
    v.resize(n);
    for (auto &x : v) scanf("%d", &x);
    int l = 0;
    long long sum = 0, ans = 0;
    for (int i = 0; i < v.size(); ++i) {
        sum += v[i];
        while (sum >= s) sum -= v[l++];
        ans += l;
    }
    printf("%lld\n", ans);
    return 0;
}

Segments with Small Set

Code

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 5;

int n, k;
vector<int> v;
int Tms[MAXN];

int main() {
    scanf("%d%d", &n, &k);
    v.resize(n);
    for (auto &x : v) scanf("%d", &x);
    long long ans = 0;
    int l = 0, num = 0;
    for (int i = 0; i < n; ++i) {
        if (!Tms[v[i]]++) {
            if (++num > k) {
                while (true) if (--Tms[v[l++]] == 0) break;
            }
        }
        ans += i - l + 1;
    }
    printf("%lld\n", ans);
    return 0;
}

Segments with Small Spread

Code 1

#include <bits/stdc++.h>

using namespace std;

int n;
long long k;
vector<long long> v;
deque<int> Mn, Mx;

int main() {
    scanf("%d%lld", &n, &k);
    v.resize(n);
    for (auto &x : v) scanf("%lld", &x);
    long long ans = 0;
    int l = 0;
    for (int i = 0; i < n; ++i) {
        while (!Mn.empty() && v[Mn.back()] > v[i]) Mn.pop_back();
        while (!Mx.empty() && v[Mx.back()] < v[i]) Mx.pop_back();
        Mn.push_back(i), Mx.push_back(i);
        while (v[Mx.front()] - v[Mn.front()] > k) {
            l++;
            while (Mx.front() < l) Mx.pop_front();
            while (Mn.front() < l) Mn.pop_front();
        }
        ans += i - l + 1;
    }
    printf("%lld\n", ans);
    return 0;
}

Code 2

#include <bits/stdc++.h>

using namespace std;

int n;
long long k;
vector<long long> v;

struct Stack {
    vector<long long> v, mn = {LLONG_MAX}, mx = {LLONG_MIN};
    void push(long long x) {
        v.push_back(x);
        mn.push_back(std::min(mn.back(), x));
        mx.push_back(std::max(mx.back(), x));
    }
    long long max() {
        return mx.back();
    }
    long long min() {
        return mn.back();
    }
    long long pop() {
        long long x = v.back();
        v.pop_back();
        mn.pop_back();
        mx.pop_back();
        return x;
    }
    bool empty() {
        return v.empty();
    }
} s1, s2;

void remove() {
    if (s1.empty()) {
        while (!s2.empty()) s1.push(s2.pop());
    }
    s1.pop();
}

int main() {
    scanf("%d%lld", &n, &k);
    v.resize(n);
    for (auto &x : v) scanf("%lld", &x);
    long long ans = 0;
    int l = 0;
    for (int i = 0; i < n; ++i) {
        s2.push(v[i]);
        while (max(s1.max(), s2.max()) - min(s1.min(), s2.min()) > k) {
            remove();
            l++;
        }
        ans += i - l + 1;
    }
    printf("%lld\n", ans);
    return 0;
}

Coprime Segment

Code

#include <bits/stdc++.h>

using namespace std;


int n;
vector<long long> v;

struct Stack {
    vector<long long> stk, val = {0};
    void push(long long x) {
        stk.push_back(x);
        val.push_back(__gcd(val.back(), x));
    }
    long long top() {
        return val.back();
    }
    long long pop() {
        long long x = stk.back();
        stk.pop_back();
        val.pop_back();
        return x;
    }
    bool empty() {
        return stk.empty();
    }
} s1, s2;

void remove() {
    if (s1.empty()) {
        while (!s2.empty()) s1.push(s2.pop());
    }
    s1.pop();
}

int main() {
    scanf("%d", &n);
    v.resize(n);
    for (auto &x : v) scanf("%lld", &x);
    int l = 0, ans = n + 1;
    for (int i = 0; i < n; ++i) {
        s2.push(v[i]);
        while (__gcd(s1.top(), s2.top()) == 1) {
            remove();
            ans = min(ans, i - l + 1);
            l++;
        }
    }
    if (ans > n) ans = -1;
    printf("%d\n", ans);
    return 0;
}

step 3:

Looped Playlist

Code

#include <bits/stdc++.h>

using namespace std;

int n;
long long p;
vector<int> v;

int main() {
    scanf("%d%lld", &n, &p);
    v.resize(n);
    long long total = 0;
    for (auto &x : v) {
        scanf("%d", &x);
        total += x;
    }
    long long ans = (p - v[0]) / total * n + 1, sum = (p - v[0]) / total * total + v[0];
    int l = 0, pos = 0;
    if (sum >= p) l = pos = 0;
    else {
        for (int i = n - 1; i >= 0; --i) {
            sum += v[i];
            ++ans;
            if (sum >= p) {
                pos = l = i;
                break;
            }
        }
    }
    long long len = ans;
    for (int r = 1; r < n; ++r) {
        sum += v[r];
        ++len;
        while (sum >= p) {
            sum -= v[l++];
            l %= n;
            --len;
        }
        if (len + 1 < ans) {
            pos = (l - 1 + n) % n;
            ans = len + 1;
        }
    }
    printf("%d %lld\n", pos + 1, ans);
    return 0;
}

Total Length

Code

#include <bits/stdc++.h>

using namespace std;

int n;
long long s;
vector<int> v;

int main() {
    scanf("%d%lld", &n, &s);
    v.resize(n);
    for (auto &x : v) scanf("%d", &x);
    int l = 0;
    long long ans = 0, sum = 0;
    for (int r = 0; r < n; ++r) {
        sum += v[r];
        while (sum > s) sum -= v[l++];
        ans += 1ll * (r - l + 2) * (r - l + 1) / 2;
    }
    printf("%lld\n", ans);
    return 0;
}

Che city

Code

#include <bits/stdc++.h>

using namespace std;

int n, s;
vector<int> v;

int main() {
    scanf("%d%d", &n, &s);
    v.resize(n + 1);
    for (int i = 1; i <= n; ++i) scanf("%d", &v[i]);
    int l = 1;
    long long ans = 1ll * n * (n + 1) / 2;
    for (int r = 1; r <= n; ++r) {
        while (v[r] - v[l] > s) ++l;
        ans -= r - l + 1;
    }
    printf("%lld\n", ans);
    return 0;
}

Stylish clothes

Code

#include <bits/stdc++.h>

using namespace std;

vector<pair<int, int>> v;
int a[4], b[4];

int main() {
    for (int i = 0, n; i < 4; ++i) {
        scanf("%d", &n);
        for (int j = 0, x; j < n; ++j) {
            scanf("%d", &x);
            v.push_back({x, i});
        }
    }
    sort(v.begin(), v.end());
    int l = 0, num = 0, ans = INT_MAX;
    int ll = 0, rr = 0;
    for (int r = 0; r < v.size(); ++r) {
        if (!b[v[r].second]++) ++num;
        if (num < 4) continue;
        while (b[v[l].second] > 1) {
            --b[v[l++].second];
        }
        if (ans > v[r].first - v[l].first) {
            ans = v[r].first - v[l].first;
            ll = l, rr = r;
        }
    }
    a[v[ll].second] = v[ll].first;
    a[v[rr].second] = v[rr].first;
    for (int i = ll + 1; i < rr; ++i) {
        if (!a[v[i].second]) a[v[i].second] = v[i].first;
    }
    for (int i = 0; i < 4; ++i) printf("%d ", a[i]);
    return 0;
}

Knapsack on a Segment

Code

#include <bits/stdc++.h>

using namespace std;

int n, s;
vector<int> w, c;

int main() {
    scanf("%d%d", &n, &s);
    w.resize(n);
    c.resize(n);
    for (auto &x : w) scanf("%d", &x);
    for (auto &x : c) scanf("%d", &x);
    int l = 0, sumw = 0;
    long long sumc = 0, ans = 0;
    for (int r = 0; r < n; ++r) {
        sumw += w[r];
        sumc += c[r];
        while (sumw > s) {
            sumw -= w[l];
            sumc -= c[l++];
        }
        ans = max(ans, sumc);
    }
    printf("%lld\n", ans);
    return 0;
}

Card Substrings

Code

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 5;

int n, m;
char s[MAXN], t[MAXN];
int Num[200], a[200];

int main() {
    scanf("%d%d%s%s", &n, &m, s, t);
    for (int i = 0; i < m; ++i) ++Num[t[i]];
    int l = 0;
    long long ans = 0;
    for (int r = 0; r < n; ++r) {
        if (++a[s[r]] > Num[s[r]]) {
            while (s[l] != s[r]) {
                --a[s[l++]];
            }
            --a[s[l++]];
        }
        ans += r - l + 1;
    }
    printf("%lld\n", ans);
    return 0;
}

Not Very Rude Substring

Code

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6 + 5;

int n;
long long c;
char s[MAXN];

int main() {
    scanf("%d%lld%s", &n, &c, s);
    int l = 0, ans = 0, numa = 0, numb = 0;
    long long sum = 0;
    for (int r = 0; r < n; ++r) {
        if (s[r] == 'a') ++numa;
        else if (s[r] == 'b') {
            ++numb;
            sum += numa;
        }
        while (sum > c) {
            if (s[l] == 'a') {
                sum -= numb;
                --numa;
            } else if (s[l] == 'b') --numb;
            ++l;
        }
        ans = max(ans, r - l + 1);
    }
    printf("%d\n", ans);
    return 0;
}

A-B Knapsack

Code

#include <bits/stdc++.h>

using namespace std;

int n, m, s, a, b;
vector<int> va, vb;

int main() {
    scanf("%d%d%d%d%d", &n, &m, &s, &a, &b);
    va.resize(n);
    vb.resize(m);
    for (auto &x : va) scanf("%d", &x);
    for (auto &x : vb) scanf("%d", &x);
    sort(va.begin(), va.end(), greater<int>());
    sort(vb.begin(), vb.end(), greater<int>());
    int r = min(n, s / a) - 1, sum = (r + 1) * a;
    long long ans = 0;
    for (int i = 0; i <= r; ++i) ans += va[i];
    long long cur = ans;
    for (int l = 0; l < min(m, s / b); ++l) {
        cur += vb[l];
        sum += b;
        while (sum > s) {
            sum -= a;
            cur -= va[r--];
        }
        ans = max(ans, cur);
    }
    printf("%lld\n", ans);
    return 0;
}

Segment with the Required Subset

Code

#include <bits/stdc++.h>

using namespace std;

const int MAXM = 1005;

int n, m;
vector<int> v;

struct Stack{
    vector<int> v;
    vector<bitset<MAXM>> val;
    void init(int x) {
        bitset<MAXM> b = 0;
        b[x] = 1;
        val.push_back(b);
    }
    void push(int x, int t) {
        if (t) val.push_back(val.back() | val.back() << x);
        else val.push_back(val.back() | val.back() >> x);
        v.push_back(x);
    }
    int pop() {
        int x = v.back();
        val.pop_back();
        v.pop_back();
        return x;
    }
    bitset<MAXM> top() {
        return val.back();
    }
    bool empty() {
        return v.empty();
    }
} s1, s2;

void remove() {
    if (s1.empty()) {
        while (!s2.empty()) s1.push(s2.pop(), 1);
    }
    s1.pop();
}

int main() {
    scanf("%d%d", &n, &m);
    v.resize(n);
    for (auto &x : v) scanf("%d", &x);
    int l = 0, ans = n + 1;
    s1.init(0);
    s2.init(m);
    for (int r = 0; r < n; ++r) {
        s2.push(v[r], 0);
        while ((s1.top() & s2.top()).any()) {
            remove();
            ans = min(ans, r - l + 1);
            l++;
        }
    }
    if (ans > n) ans = -1;
    printf("%d\n", ans);
    return 0;
}

all you need to two pointer

→ Ответить

Соревнования по программированию 2.0

Время на сервере: 30.07.2024 01:27:01 (h1).

Десктопная версия, переключиться на мобильную.

При поддержке