two pointers - Codeforces

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

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
21:29:08
Зарегистрироваться »

*есть доп. регистрация

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

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

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

Всё →

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

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Всё →

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

→ Прямой эфир

Детальнее →

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

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

← Rev. 2 →

+10

→ Ответить

Kamado_Tanjiro_2008

4 месяца назад, # ^ |

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

Время на сервере: 22.11.2024 20:05:53 (j3).

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

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