Mmedv2 years ago

Two pointers technique

The Two Pointers technique is a strategy commonly used in computer science and programming for solving problems involving arrays or sequences. It involves using two pointers that traverse the array or sequence from different positions, often moving in opposite directions or at different speeds. This technique is particularly useful for solving problems related to searching, optimization, or manipulation of arrays efficiently.

Here's a breakdown of how the Two Pointers technique works:

Initialization: Initially, you set up two pointers, usually at different positions within the array or sequence.
Movement: You iteratively move the pointers based on certain conditions until they meet or reach a specific condition. The movement of pointers can be controlled based on the problem requirements. For example, one pointer might move faster than the other, or they might move in opposite directions.
Condition Checking: At each step of iteration, you check certain conditions based on the problem requirements. These conditions often determine whether to move the pointers, update some variables, or perform other operations.
Termination: The process continues until one or both pointers reach the end of the array or sequence, or until some other termination condition is met.

The Two Pointers technique is especially useful in problems that involve searching for pairs or subarrays that meet specific criteria, finding optimal solutions, or manipulating sequences efficiently without using nested loops. It often provides a more efficient solution compared to brute-force approaches, especially for problems with linear or logarithmic time complexity requirements.

Eolymp #2098. Invertor

Given $n$ integers. Print them in reverse order.

Input. First given number $n (0 < n < 100)$ n~(0 < n < 100), then given $n$ integers.

Output. Print the given $n$ integers in reverse order.

Open problem

Declare an array.

#define MAX 110
int m[MAX];

Read the input data.

scanf("%d",&n);
for(i = 1; i <= n; i++)
  scanf("%d",&m[i]);

Reverse the array using the two-pointer technique.

i = 1; j = n;
while(i < j)
{
  temp = m[i]; m[i] = m[j]; m[j] = temp;
  i++; j--;
}

Print the numbers.

for(i = 1; i <= n; i++)
  printf("%d ",m[i]);
printf("\n");

Eolymp #11387. Cards game

Huseyn and Yaroslav are playing a card game. There are n cards laid out in a row on the table, each with a different number written on it. The players take turns. Huseyn starts the game. On each turn, a player can take either the leftmost or the rightmost card. The player will always choose the card with the highest number. The game ends when there are no cards left on the table. Find the sum of the numbers on the cards collected by Huseyn and Yaroslav at the end of the game.

Input. The first line contains the number of cards $n (1 \leq n \leq 10000)$ n~(1 \le n \le 10000) on the table. The second line contains $n$ positive integers, each indicating the number on a card. All numbers are not greater than $1 0^{9}$ 10^9.

Output. Print the sum of the numbers on the cards collected by Huseyn and Yaroslav at the end of the game.

Open problem

Declare the arrays. The sum of the numbers on the cards collected by Huseyn and Yaroslav will be stored in $r es [0]$ and $r es [1]$ , respectively.

int m[10001], res[2];

Read the input data.

scanf("%d", &n);
for (i = 0; i < n; i++)
  scanf("%d", &m[i]);

Set the pointers $i = 0$ and $j = n - 1$ j = n - 1.

i = 0; j = n - 1;

The players take turns, making $n$ moves in total. Huseyn takes turns for even $k$ , and Yaroslav takes turns for odd $k$ . Accordingly, Huseyn's sum will accumulate in $r es [0]$ , and Yaroslav's sum will accumulate in $r es [1]$ .

for (k = 0; k < n; k++)
{

On each turn, the player chooses the card with the maximum value $ma x (m [i], m [j])$ max(m[i], m[j]).

  if (m[i] > m[j])
    res[k % 2] += m[i++];
  else
    res[k % 2] += m[j--]; ;
}

Print the answer.

printf("%d %d\n", res[0], res[1]);

Eolymp #11388. Cards game 2

Huseyn arranged $n$ cards in a row with numbers $a_{1}, a_{2}, a_{3}, ..., a_{n}$ a_1, a_2, a_3, ..., a_n. Then he collected them and rearranged them in a different order: $a_{1}, a_{3}, a_{5}, ..., a_{6}, a_{4}, a_{2}$ a_1, a_3, a_5, ..., a_6, a_4, a_2. This is the sequence he gave to Yaroslav. Your task is to help Yaroslav restore Hussein's original sequence.

For example, if Yaroslav received the sequence $(2, 4, 9, 4, 7, 6)$ (2, 4, 9, 4, 7, 6), then he should return the sequence $(2, 6, 4, 7, 9, 4)$ (2, 6, 4, 7, 9, 4) to Huseyn.

Input. The first line contains one integer $n (1 \leq n \leq 10000)$ n~(1 \le n \le 10000), representing the number of cards. The second line contains $n$ positive integers written on the cards. All numbers are no greater than $1 0^{9}$ 10^9.

Output. Print Huseyn's original sequence.

Open problem

Declare an array.

int a[100001];

Read the input data.

scanf("%d", &n);
for (i = 0; i < n; i++)
  scanf("%d", &a[i]);

Set the pointers $i = 0$ and $j = n - 1$ j = n - 1.

i = 0; j = n - 1;

While the inequality $i \leq j$ i \le j holds, alternately print $a_{i}$ a_i and $a_{j}$ a_j, simultaneously moving the pointers.

while (i <= j)
{
  printf("%d ", a[i++]);
  if (i > j) break;
  printf("%d ", a[j--]);
}

Eolymp #11389. Huseyn's game

Huseyn has a string consisting of characters $0$ and $1$ . To entertain himself, he came up with the following game. Huseyn can perform one of two operations on the string:

append $0$ to the left end, and $1$ to the right end;
append $0$ to the right end, and $1$ to the left end;

For example, from the string $010$ , Huseyn can obtain $00101$ or $10100$ .

You are given a string obtained after all of Huseyn's operations (it is possible that he did not perform any operation). Determine the smallest possible length the string could have initially had.

Input. A single string of length no more than $1 0^{5}$ 10^5, consisting only of characters $0$ and $1$ .

Output. Print the smallest possible length of the string that Huseyn could have initially had.

Open problem

Read the input string and calculate its length, storing it in the variable $r es$ .

cin >> s;
res = s.size();

Initialize two pointers: $i = 0$ at the start and $j = n - 1$ j = n - 1 at the end of the string.

i = 0; j = s.size() - 1;

If $s_{i} \neq = s_{j}$ s_i \ne s_j, then the characters at the ends of the string are different. Huseyn could have obtained the substring $s [i ... j]$ from the substring $s [i + 1... j - 1]$ s[i + 1 ... j - 1].

while ((i < j) && (s[i] != s[j]))
{

Move both pointers $i$ and $j$ one position towards each other and decrease the current size $r es$ of the substring $s [i ... j]$ .

  i++; j--;
  res -= 2;
}

Print the answer.

cout << res << endl;

Eolymp #11244. Sum of two

Given an array $A$ , sorted in ascending order and containing $n$ integers. Determine whether there exists a pair of numbers $(A_{i}, A_{j})$ (A_i, A_j), where $i < j$ i < j, such that their sum is equal to $x$ .

Input. The first line contains two integers $n (n \leq 1 0^{5})$ n~(n \le 10^5) and $x (x \leq 1 0^{6})$ x~(x \le 10^6). The second line contains $n$ non-negative integers, each of which is not greater than $1 0^{6}$ 10^6.

Output. Print "YES" if such a pair of elements exists, and "NO" otherwise.

Open problem

Read the input data.

scanf("%d %d", &n, &x);
v.resize(n);
for (i = 0; i < n; i++)
  scanf("%d", &v[i]);

Initialize the pointers.

int i = 0, j = v.size() - 1;

Move pointer $i$ forward and pointer $j$ backward.

while (i < j)
{

If $v_{i} + v_{j} = x$ v_i + v_j = x, then the desired pair of elements is found. Print it and terminate the program.

  if (v[i] + v[j] == x)
  {
    printf("YES\n");
    return 0;
  }

If $v_{i} + v_{j} < x$ v_i + v_j < x, then move pointer $i$ one position to the right;

If $v_{i} + v_{j} > x$ v_i + v_j > x, then move pointer $j$ one position to the left;

  if (v[i] + v[j] < x) i++; else j--;
}

If the desired pair is not found, print "NO".

printf("NO\n");

Eolymp #11246. Sum of three

Given an array of integers $A$ and an integer $x$ . Find a triplet of numbers $(A_{i}, A_{j}, A_{k})$ (A_i, A_j, A_k) in the array whose sum equals $x$ . All indices $i, j, k$ i, j, k should be different.

Input. The first line contains the size of the array $n (n \leq 3 \cdot 1 0^{4})$ n~(n \le 3 \cdot 10^4) and the value of $x (∣ x ∣ \leq 1 0^{9})$ x~(|x| \le 10^9). The second line contains $n$ integers, each of which does not exceed $1 0^{8}$ 10^8 in absolute value.

Output. If the required triplet exists, print it in any order. If multiple triplets exist, print any one of them. If the desired triplet does not exist, print $- 1$ .

Open problem

Read the input data.

cin >> n >> x;
v.resize(n);
for (i = 0; i < n; i++)
  cin >> v[i];

Sort the input array.

sort(v.begin(), v.end());

Iterate through the values $k = 0, 1, ..., n - 3$ k = 0, 1, ..., n - 3.

for (k = 0; k < n - 2; k++)
{

Find a pair of indices $(i, j)$ such that $i > k$ i > k and $v_{i} + v_{j} = x - v_{k} (i < j)$ v_i + v_j = x - v_k~(i < j). Initialize the indices $i$ and $j$ .

  i = k + 1; j = n - 1;
  s = x - v[k];

Use the two-pointer technique to find the desired pair $(i, j)$ .

  while (i < j)
  {
    if (v[i] + v[j] == s)
    {

If the pair $(i, j)$ is found, print the desired triplet of numbers $(v_{k}, v_{i}, v_{j})$ (v_k, v_i, v_j).

      printf("%d %d %d\n", v[k], v[i], v[j]);
      return 0;
    }

If $v [i] + v [j] < s$ v[i] + v[j] < s, then move pointer $i$ one position to the right;

If $v [i] + v [j] > s$ v[i] + v[j] > s, then move pointer $j$ one position to the left;

    if (v[i] + v[j] < s) i++; else j--;
  }
}

If the triplet of numbers is not found, print $- 1$ .

cout << -1 << endl;

Eolymp #11286. Twice bigger

Given a sorted array $A$ of $n$ integers. For each index $i$ , find the number of elements in the array that lie between $A_{i}$ A_i and $2 \cdot A_{i}$ 2 \cdot A_i inclusive.

Input. The first line contains the size $n (n \leq 1 0^{5})$ n~(n \le 10^5) of array $A$ . The second line contains $n$ integers, each ranging from $0$ to $1 0^{9}$ 10^9, in sorted order.

Output. Print $n$ integers. For each index $i (1 \leq i \leq n)$ i~(1 \le i \le n) of the array, print the number of elements lying between $A_{i}$ A_i and $2 \cdot A_{i}$ 2 \cdot A_i inclusive.

Open problem

Read the input data.

scanf("%d", &n);
for (i = 0; i < n; i++)
  scanf("%d", &a[i]);

Initialize the pointers $i = j = 0$ i = j = 0.

i = j = 0;

Move the pointers forward until an answer is found for each value of $i < n$ i < n.

while (i < n) // [i..j]
{

If $A_{j} \leq 2 \cdot A_{i}$ A_j \le 2 \cdot A_i (and $j$ has not exceeded the array bounds, meaning $j < n$ j < n), extend the current interval by incrementing the pointer $j$ .

  if ((j < n) && (a[j] <= 2 * a[i])) j++;
  else
  {

If $A_{j} > 2 \cdot A_{i}$ A_j > 2 \cdot A_i, print the answer for index $i$ and increment $i$ by one.

    printf("%d ", j - i);
    i++;
  }
}

Eolymp #10682. Hotels along the Croatian coast

Along the beautiful Adriatic coast, there are $n$ hotels. Each hotel has its cost in euros. Petr won $m$ euros in the lottery. Now he wants to buy a sequence of consecutive hotels one after another so that the sum of the costs of these consecutive hotels is as large as possible, but does not exceed $m$ .

You need to calculate this maximum possible total cost.

Input. The first line contains two integers $n$ and $m (1 \leq n \leq 3 \cdot 1 0^{5}, 1 \leq m < 2^{31})$ m~(1 \le n \le 3 \cdot 10^5, 1 \le m < 2^{31}). The next line contains $n$ positive integers less than $1 0^{6}$ 10^6, representing the costs of the hotels in the order they are located along the coast.

Output. Print the desired maximum cost (it will be greater than $0$ in all tests).

Open problem

Read the input data.

scanf("%d %lld", &n, &m);

Initialize the variables:

in $r es$ , the maximum value among the costs of all processed good intervals is computed;
in $s$ , the sum of numbers in the current interval $[i ... j]$ is maintained. All the numbers in the current interval $[i ... j]$ are stored in the queue $q$ ;

s = res = 0;

Process the hotel costs sequentially.

for (i = 0; i < n; i++)
{

Read and add the cost $v a l$ of the current hotel to the queue.

  scanf("%d", &val);
  q.push(val);

Update the sum $s$ within the interval. All elements of the current interval are stored in the queue $q$ .

  s += val;

If the sum of numbers in the current interval exceeds $s$ , we remove elements from the beginning of the interval.

  while (s > m)
  {
    s -= q.front();
    q.pop();
  }

Compute the maximum value $r es$ among the sums of elements in good intervals (where the cost of hotels does not exceed $m$ ).

  if (s > res) res = s;
}

Print the answer.

printf("%lld\n", res);

Eolymp #11721. Subarray sums 1

Given an array of $n$ positive integers, find the number of subarrays whose sum is equal to $x$ .

Input. The first line contains the size of the array $n (1 \leq n \leq 2 \cdot 1 0^{5})$ n~(1 \le n \le 2 \cdot 10^5) and the target sum $x (1 \leq x \leq 1 0^{9})$ x~(1 \le x \le 10^9). The next line contains $n$ integers $a_{1}, a_{2}, \dots, a_{n} (1 \leq a_{i} \leq 1 0^{9})$ a_1, a_2, \ldots, a_n~(1 \le a_i \le 10^9) — the contents of the array.

Output. Print the required number of subarrays.

Open problem

Declare an array.

#define MAX 200001
long long a[MAX];

Read the input data.

scanf("%d %lld", &n, &x);
for (i = 0; i < n; i++)
  scanf("%lld", &a[i]);

Initially, set the current interval $[i ... j] = [0; 0]$ [i ... j] = [0; 0]. The sum of the numbers in this interval is $s = 0$ .

s = j = 0;

For each value of $i$ , sequentially process the intervals $[i ... j]$ .

for (i = 0; i < n; i++)
{

For the fixed left end $i$ of the interval $[i ... j]$ , search for the largest $j$ such that the sum of elements in this interval does not exceed $x$ .

  while ((j < n) && (s + a[j] <= x)) s += a[j++];

If the sum of the numbers $s$ in the current interval $[i ... j]$ equals $x$ , increase the desired subarray count $c n t$ by $1$ .

  if (s == x) cnt++;

Recompute the sum $s$ for the interval $[i + 1... j]$ [i + 1 ... j].

  s -= a[i];
}

Print the answer.

printf("%lld\n", cnt);

Eolymp #9631. Competition of sequences

Ziya will take part in the sequence competition tomorrow. The number $x \geq 0$ x \ge 0 is called the top of some sequence if the sequence $1, 2, 3, ..., x - 1, x, x - 1, ..., 3, 2, 1$ 1, 2, 3, ..., x - 1, x, x - 1, ..., 3, 2, 1 is a subsequence of this sequence. The strength of each sequence is considered to be its largest vertex.

Tomorrow all students will go to the competition and the winner of the strongest sequence will be the winner. Zia has the sequence $a_{1}, a_{2}, a_{3}, ..., a_{n}$ a_1, a_2, a_3, ..., a_n. He wants to take over the competition scoring system and remove sequences from it with more force than himself. However, Zia does not know the power of his own consistency, but really wants to win. Help him calculate the strength of his own sequence.

Input. The first line contains the number $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5) of numbers in Zia's sequence. The next line contains $n$ integers $a_{i} (1 \leq a_{i} \leq 1 0^{5})$ a_i~(1 \le a_i \le 10^5) — the elements of the sequence.

Output. Print one number — the strength of the given sequence.

Open problem

Read the input data.

scanf("%d", &n);
v.resize(n);
for (i = 0; i < n; i++)
  scanf("%d", &v[i]);

Set the pointers to the start and end of the array $v$ .

int i = 0, j = v.size() - 1;

In the variable $k$ , we count the strength of the sequence.

k = 1;
while (i <= j)
{

Move the pointer $i$ to the right until it encounters the number $k$ .

  if (v[i] != k) i++;

Move the pointer $j$ to the left until it encounters the number $k$ .

  if (v[j] != k) j--;

If both pointers point to the number $k$ , then increase $k$ by one.

  if (v[i] == k && v[j] == k) k++;
}

Print the answer.

printf("%d\n", k - 1);

Eolymp #9632. The best team

Today, $n$ programmers have gathered. Each programmer has a rating that reflects his strength. The rating is an integer between $0$ and $1 0^{9}$ 10^9. Your rating as a programmer is $m$ . From all the programmers gathered today, you want to choose two for your team. They must be selected in such a way that their total rating is maximized but does not exceed your rating, as you want to be the leader of this team.

Input. The first line contains two integers: $n (2 \leq n \leq 1 0^{5})$ n~(2 \le n \le 10^5) — the number of programmers, and $m (0 \leq m \leq 1 0^{9})$ m~(0 \le m \le 10^9) — your rating. The second line contains $n$ integers $r_{1}, r_{2}, ..., r_{n} (0 \leq r_{i} \leq 1 0^{9})$ r_1, r_2, ... , r_n~(0 \le r_i \le 10^9) — the ratings of the programmers.

Output. Print a single integer — the maximum sum of the ratings of the selected programmers, or $- 1$ if it is impossible to find such two people.

Open problem

Read the input data.

scanf("%d %d", &n, &m);
v.resize(n);
for (i = 0; i < n; i++)
  scanf("%d", &v[i]);

Sort the programmers’ ratings.

sort(v.begin(), v.end());

Initialize the pointers. The variable $m x$ stores the maximum sum of two elements.

int mx = -1, low = 0, high = n - 1;

The pointer $l o w$ is moved forward, and the pointer $hi g h$ is moved backward.

while (low < high)
{

Among all possible sums $v [l o w] + v [hi g h]$ v[low] + v[high] that do not exceed $m$ find the maximum. If $v [l o w] + v [hi g h] \leq m$ v[low] + v[high] \le m, move $l o w$ forward. Otherwise, move $hi g h$ backward.

  if (v[low] + v[high] <= m)
  {
    mx = max(mx, v[low] + v[high]);
    low++;
  }
  else high--;
}

C++

Print the answer.

printf("%d\n", mx);

Eolymp #10568. Diamond Collector (Bronze)

Bessie the cow, always a fan of shiny objects, has taken up a hobby of mining diamonds in her spare time! She has collected $n$ diamonds of varying sizes, and she wants to arrange some of them in a display case in the barn.

Since Bessie wants the diamonds in the case to be relatively similar in size, she decides that she will not include two diamonds in the case if their sizes differ by more than $k$ (two diamonds can be displayed together in the case if their sizes differ by exactly $k$ ). Given $k$ , help Bessie determine the maximum number of diamonds she can display in the case.

Input. The first line contains $n (n \leq 1000)$ n~(n \le 1000) and $k (0 \leq k \leq 10000)$ k~(0 \le k \le 10000). The next $n$ lines each contain an integer giving the size of one of the diamonds. All sizes will be positive and will not exceed $10000$ .

Output. Print the maximum number of diamonds that Bessie can showcase.

Open problem

Declare an array to store the sizes of the diamonds.

int m[1000];

Read the input data.

scanf("%d %d", &n, &k);
for (i = 0; i < n; i++)
  scanf("%d", &m[i]);

Sort the array.

sort(m, m + n);

The maximum number of diamonds that Bessie can display in the barn is counted in the variable $r es$ .

res = 0;

For each index $i$ , consider the sequence $m_{i}, m_{i + 1}, ..., m_{j}$ m_i, m_{i+1}, ..., m_j of the greatest length such that $∣ m_{j} - m_{i} ∣ \leq k$ | m_j - m_i | \le k. Count the length of this sequence in the variable $c n t$ .

for (i = 0; i < n; i++)
{
  cnt = 0;
  for (j = i; j < n; j++)
  {

As soon as the condition $∣ m_{j} - m_{i} ∣ > k$ | m_j - m_i | > k becomes true, exit the loop.

    if (m[j] > m[i] + k) break;
    cnt++;
  }

Among the lengths of all sequences, find the maximum.

  if (cnt > res) res = cnt;
}

Print the answer.

printf("%d\n", res);

Eolymp #11247. Container With Most Water

There is an array $h$ of integers of length $n$ , representing the heights of $n$ vertical lines. For each $i$ -th line, its endpoints are defined by the coordinates $(i, 0)$ and $(i, h_{i})$ (i, h_i).

Find two lines that, together with the $x$ -axis, form a container capable of holding the maximum amount of water.

Input. The first line contains the size $n (n \leq 1 0^{5})$ n~(n \leq 10^5) of the array $h$ . The second line contains $n$ positive integers, the elements of the array $h$ , each of which does not exceed $1 0^{9}$ 10^9.

Output. Print the maximum volume of water that the container can hold.

Open problem

Read the input data.

scanf("%d", &n);
h.resize(n);
for (i = 0; i < n; i++)
  scanf("%lld", &h[i]);

Store the maximum amount of water the container can hold in the variable $r es$ .

long long res = 0;

Initialize two pointers $(l, r) = (1, n)$ (l, r) = (1, n).

int l = 0, r = h.size() - 1;

Move the pointers $l$ and $r$ towards each other until they meet.

while (l < r)
{

The volume of water between the lines $l$ and $r$ is equal to $min (h_{l}, h_{r}) \cdot (r - l)$ min(h_l, h_r) \cdot (r - l). Among all such volumes, find the maximum.

  res = max(res, min(h[l], h[r]) * (r - l));

Move the pointers.

  if (h[l] < h[r])
    l += 1;
  else
    r -= 1;
}

Print the answer.

printf("%lld\n", res);

Eolymp #11340. Radio 106 FM

You are given a list of songs that played on Radio 106 FM. The list contains a total of $n$ songs. Find the length of the longest fragment of the list that consists of non-repeating songs.

Input. The first line contains the number of songs $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5) in the list. The second line contains $n$ integers $k_{1}, k_{2}, ..., k_{n} (1 \leq k_{i} \leq 1 0^{9})$ k_1, k_2, ..., k_n~(1 \le k_i \le 10^9), which are the identification numbers of the songs.

Output. Print the length of the longest fragment of the list that consists of unique songs.

Open problem

Read the input data. The identification numbers of the songs are stored in the array $v$ .

scanf("%d", &n);
v.resize(n);
for (i = 0; i < n; i++)
  scanf("%d", &v[i]);

Maintain the segment $[i; j - 1]$ [i; j - 1] of unique songs (i.e., the songs from $v_{i}$ v_i to $v_{j - 1}$ v_{j-1} do not repeat). In the set $s$ , store the identification numbers of the songs from this segment. The variable $r es$ tracks the length of the longest fragment with unique songs.

i = res = 0;
for (j = 0; j < n; j++)
{

Consider the current song at index $j$ . If it is already in the set $s$ , it will not be possible to extend the current segment $[i; j - 1]$ [i; j - 1] by including the $j$ -th song. In this case, we need to shift the left boundary $i$ , removing the song $v_{i}$ v_i from the set $s$ , until the $j$ -th song disappears from the set $s$ .

  while (s.find(v[j]) != s.end())
  {
    s.erase(v[i]);
    i++;
  }

Add the $j$ -th song to the segment and, accordingly, to the set $s$ . Thus, the segment $[i; j]$ will not contain any repeated songs.

  s.insert(v[j]);

Among all possible segments $[i; j]$ , find the longest one. The length of the segment $[i; j]$ is $j - i + 1$ j - i + 1.

  res = max(res, j - i + 1);
}

Print the answer.

printf("%d\n", res);

Two pointers technique

List of problems

Comments5