Two Pointers

Escrito por: Leonardo Paes

Two Pointers é uma técnica muito utilizada para a resolução de problemas de programação competitiva. A ideia consiste em usar dois ponteiros, $l$ e $r$ , que representam a posição mais a esquerda de um intervalo, o $left$ , e a posição mais a direita, o $right$ . Dados dois ponteiros, calculamos a resposta para esse intervalo e, baseado em alguma condição que varia de problema em problema, escolhemos o próximo intervalo a ser observado. Para isso, podemos incrementar ou decrementar algum dos dois ponteiros.

Em certos casos, como no exercício 1, usaremos essa técnica apenas para representar duas posições de um vetor, ao invés de um intervalo.

Exercício 1:

Dado um vetor $V$ , ordenado em ordem crescente, de $N$ inteiros, descubra se existe algum par de elementos tal que sua soma seja igual a $X$ .

Restrições: $1\leq N\leq 10^6$ e $1\leq V[i] \leq 10^3$ , $i$ sendo uma posição válida do vetor $V$ .

Solução Lenta: Uma possível e intuitiva abordagem consiste em percorrer o vetor inteiro e, para cada posição do vetor, percorrê-lo por inteiro novamente, checando para cada dupla de elementos encontrados, se a sua soma é igual a $X$ . Infelizmente, tal algoritmo tem a complexidade $\mathcal{O}(N^{2})$ , o que significa que o código não é bom o bastante.

Código de exemplo:

	// Noic - Ideia 4
	// Exercício 1
	// Complexidade: O(N^2)
	// Por Leonardo Paes

	#include <bits/stdc++.h>

	using namespace std;

	int v[1000100];

	int main(){

	int n, x;

	cin >> n >> x;

	for(int i=1; i<=n; i++){
	cin >> v[i];
	}

	bool resposta=false;

	for(int i=1; i<=n; i++){
	for(int j=1; j<=n; j++){
	if(v[i]+v[j]==x){
	resposta=true;
	}
	}
	}

	cout << resposta << endl;

	return 0;
	}

view raw

Exercício 1.cpp

hosted with ❤ by GitHub

Agora, note que o vetor está ordenado. Mas em que, exatamente, isso pode nos ajudar? Simples! Vamos começar com nosso ponteiro $l$ na primeira posição do vetor e com $r$ na última posição do vetor. Então, se $V[l] + V[r] = X$ , encontramos uma soma que satisfaz o problema! Mas e se $V[l] + V[r] \neq X$ ? Há dois casos a serem analisados: Ou $V[l] + V[r] < X$ , ou $V[l] + V[r] > X$ .

Primeiro Caso: Como o vetor está ordenado crescentemente, ao incrementarmos em 1 o nosso $l$ , a soma $V[l] + V[r]$ será maior do que a soma anterior!

Segundo Caso: Analogamente, ao decrementarmos em 1 o nosso $r$ , a soma $V[l] + V[r]$ será menor do que a soma anterior!

Após efetuarmos as operações necessárias de um dos dois casos, basta checarmos se a soma atual $V[l] + V[r] = X$ . Se ela for, encerramos o algoritmo, de forma contrária, continuaremos a escolher um dos dois casos, dependendo da soma atual encontrada! Devemos interromper o algoritmo caso $r \leq l$ , pois, se $l=r$ , estaríamos olhando apenas uma posição, e não duas.

Código da Solução:

	// Noic - Ideia 4
	// Exercício 1
	// Complexidade: O(N)
	// Por Leonardo Paes
	#include <bits/stdc++.h>

	using namespace std;

	int v[1000100];

	int main(){

	int n, x;

	cin >> n >> x;

	for(int i=1; i<=n; i++){
	cin >> v[i];
	}

	bool resposta=false;

	for(int l=1, r=n; l<r;){
	if(v[l]+v[r]==x){
	resposta=true;
	break;
	}
	if(v[l]+v[r]<x){
	l++;
	}
	if(v[l]+v[r]>x){
	r--;
	}
	}

	cout << resposta << endl;

	return 0;
	}

view raw

Exercicio 1 Solução.cpp

hosted with ❤ by GitHub

Exercício 2:

Seja $V$ um vetor cíclico de $N$ posições. Um vetor cíclico é um vetor tal que a posição que vem após a última é a primeira, ou seja, $V[N+1] = V[1]$ . Dado um inteiro $X$ , diga o número de intervalos $V[l], V[l+1], ..., V[r-1], V[r]$ , tal que a soma de todos os elementos do vetor $V$ correspondentes a esse intervalo possui soma igual a $X$ . Ou seja: $V[l] + V[l+1] + ... V[r-1] + V[r] = X$ . Note que, como o vetor $V$ é circular, intervalos em que $l>r$ são intervalos válidos. Dois intervalos são considerados diferentes se seus respectivos inícios ou fins são diferentes.

Restrições: $1\leq N\leq 10^6$ e $1\leq X\leq 10^9$ . $1\leq V[i] \leq 10^3$ , $i$ sendo uma posição válida do vetor $V$ .

Inicialmente, vamos resolver o problema do vetor ser cíclico. Para isso, a ideia é de apenas duplicar o vetor! Isso mesmo, enquanto estamos lendo a entrada, basta falarmos que $V[N+i] = V[i]$ . Agora, utilizaremos a ideia dos Two Pointers. Inicializaremos com: O ponteiro $l=1$ , com o ponteiro $r=1$ e com o inteiro $Soma=V[1]$ , o que significa que estamos analisando o intervalo $(l, r) = (1, 1)$ . Então, de forma similar a do exercício 1, se $V[l] + V[l+1] + ... + V[r] = X$ nós aumentaremos nossa resposta em 1. Se $V[l] + V[l+1] + ... + V[r] \neq X$ , há dois casos a serem analisados: Ou $V[l] + V[l+1] + ... + V[r] < X$ , ou $V[l] + V[l+1] + ... + V[r] > X$ .

Primeiro Caso: Como queremos aumentar a soma dos números, incrementaremos $r$ em 1, pois, assim, teremos um número a mais acrescentando na nossa soma. A soma deve ser acrescentada em $V[r]$ .

Segundo Caso: Já que a soma atual está grande demais, devemos diminuir nosso intervalo, então, incrementaremos $l$ em 1, diminuindo em 1 o tamanho do intervalo. Note que antes de incrementarmos, devemos retirar $V[l]$ da soma, pois ele não pertence mais ao intervalo.

Agora, se $V[l] + V[l+1] + ... + V[r] = X$ , encontramos mais um intervalo válido.Neste caso, incrementaremos ambos $l$ quanto o $r$ , para prosseguirmos para o próximo intervalo. Caso contrário, devemos continuar o algoritmo, e escolher entre os dois casos, de acordo com a soma atual. Lembre-se de que o vetor $V$ só tem $N$ posições, então, os nossos intervalos contados devem ter, no máximo, $N$ elementos. Assim, devemos checar se $r-l>N$ . Se isso ocorrer, devemos aumentar o $l$ em 1, para diminuirmos o tamanho do intervalo. Enquanto $l \leq N$ , continuaremos o algoritmo. Se $l=N+1$ , devemos interromper o loop, pois começaríamos a recontar intervalos, já que $V[N+1] = V[1]$ .

Código de Solução:

	// Noic - Ideia 4
	// Exercício 2
	// Complexidade: O(N)
	// Por Leonardo Paes

	#include <bits/stdc++.h>

	using namespace std;

	int v[3000000];

	int main(){

	int n, x, resposta = 0, soma;

	cin >> n >> x;

	for(int i = 1; i <= n; i++){
	cin >> v[i];
	v[n+i]=v[i];
	}

	soma=v[1];

	for(int l=1, r=1; l<=n;){
	if(r-l>n){
	soma-=v[l];
	l++;
	}
	else if(soma<x){
	r++;
	soma+=v[r];
	}
	else if(soma>x){
	soma-=v[l];
	l++;
	}
	else if(soma == x){
	resposta++;
	r++;
	soma+=v[r];
	soma-=v[l];
	l++;
	}
	}
	cout << resposta << endl;
	}

view raw

Exercício 2 Solução.cpp

hosted with ❤ by GitHub

PROBLEMAS PARA PRATICAR:

Sanduíche (OBI 2016 - P2 - F1).
Hottest (Practice Task IOI 2011).
Cities Robbery (CS Academy).
Balanced Team (Codeforces - Div3 C).
Three Parts of the Array (Codeforces - Div3 C).
BerSU Ball (Codeforces - Div2 B).
Desafio: Jury Meeting (Codeforces - Div1 B).