two pointers - Codeforces

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

До соревнования
Educational Codeforces Round 173 (Rated for Div. 2)
34:26:24
Зарегистрироваться »

→ Трансляции

aryanc403

До начала 36:36:22

Всё →

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

№	Пользователь	Рейтинг
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

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

Всё →

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

№	Пользователь	Вклад
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	151

Всё →

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

→ Прямой эфир

Детальнее →

Блог пользователя 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

5 месяцев назад, # |

← 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

Время на сервере: 23.12.2024 07:08:38 (k2).

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

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