Презентация на тему Two pointers method

TWO POINTERS METHODLyzhin Ivan, 2016 ProblemThere is array A with N positive integers.Segment of array – a sequence of one or 1. Very primitive solutionSum elements for each pair (L, R).for (int i = 0; i < 2. Primitive solutionNotice that sum(L, R) = sum(L, R-1)+A[R]If sum(L, R1)>D then sum(L, R2)>D for each 3. Good solutionNotice that it’s enough to find maxR(L) = max(R) such sum(L, R)D for each 3. Good solutionprefixSum[0] = a[0];for (int i = 1; i < n; ++i)	prefixSum[i] = prefixSum[i - 4. Best solutionNotice that maxR(L)>=maxR(L-1). So we can start finding maxR(L) from maxR(L-1).In this way out Tracing, step 0Left=0Right=-1ANS=0SUM=0D=6 Tracing, step 1Left=0Right=0ANS=0SUM=1D=6 Tracing, step 2Left=0Right=1ANS=0SUM=3D=6 Tracing, step 3Left=0Right=2ANS=0SUM=6D=6 Tracing, step 4Left=0Right=2ANS=3SUM=6D=6 Tracing, step 5Left=1Right=2ANS=3SUM=5D=6 Tracing, step 6Left=1Right=2ANS=5SUM=5D=6 Tracing, step 7Left=2Right=2ANS=5SUM=3D=6 Tracing, step 8Left=2Right=3ANS=5SUM=6D=6 Tracing, step 9Left=2Right=3ANS=7SUM=6D=6 Tracing, step 10Left=3Right=3ANS=7SUM=3D=6 Tracing, step 11Left=3Right=3ANS=8SUM=3D=6 Tracing, step 12Left=4Right=3ANS=8SUM=0D=6 Tracing, step 13Left=5Right=3ANS=8SUM=-7D=6 Tracing, step 14Left=5Right=4ANS=8SUM=0D=6 Tracing, step 15Left=6Right=4ANS=8SUM=-8D=6 Tracing, step 16Left=6Right=5ANS=8SUM=0D=6 Tracing, step 17Left=6Right=6ANS=8SUM=6D=6 Tracing, step 18Left=6Right=6ANS=9SUM=6D=6 Tracing, step 19Left=7Right=6ANS=9SUM=0D=6 Tracing, step 20Left=7Right=7ANS=9SUM=4D=6 Tracing, step 21Left=7Right=8ANS=9SUM=6D=6 Tracing, step 22Left=7Right=8ANS=11SUM=6D=6 Tracing, step 23Left=8Right=8ANS=11SUM=2D=6 Tracing, step 24Left=8Right=9ANS=11SUM=5D=6 Tracing, step 25Left=8Right=9ANS=13SUM=5D=6 Tracing, step 26Left=9Right=9ANS=13SUM=3D=6 Tracing, step 27Left=9Right=9ANS=14SUM=3D=6 Tracing, step 28Left=9Right=9ANS=14SUM=0D=6 Other examplesThere are 2 sorted arrays of integers: A and B. Count pairs (i, j) such Additional links and home taskArticle about two pointers method http://informatics.mccme.ru/mod/resource/view.php?id=12716Discussion on codeforces http://codeforces.com/blog/entry/4136?locale=ruContest http://codeforces.com/group/Hq4vrJcA4s/contest/206340

Презентацию Two pointers method, из раздела: Информатика,  в формате PowerPoint (pptx) можно скачать внизу страницы, поделившись ссылкой в социальных сетях! Презентации взяты из открытого доступа или загружены их авторами, администрация сайта не отвечает за достоверность информации в них. Все права принадлежат авторам материалов: Политика защиты авторских прав

Слайды и текст этой презентации

Слайд 1

TWO POINTERS METHOD

Lyzhin Ivan, 2016


Слайд 2

sequence of one or more consecutive elements in array.D-good segment – segment, in which sum

Problem

There is array A with N positive integers.
Segment of array – a sequence of one or more consecutive elements in array.
D-good segment – segment, in which sum of elements not greater than D.
Count the pairs (L, R) such that segment [L, R] of array A is D-good.


Слайд 3

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

1. Very primitive solution

Sum elements for each pair (L, R).

for (int i = 0; i < n; ++i)
for (int j = i; j < n; ++j)
{
int sum = 0;
for (int k = i; k <= j; ++k)
sum += a[k];
if (sum <= d)
ans++;
}

O(N3)


Слайд 4

sum(L, R2)>D for each R2>R1for (int i = 0; i < n; ++i){int sum =

2. Primitive solution

Notice that sum(L, R) = sum(L, R-1)+A[R]
If sum(L, R1)>D then sum(L, R2)>D for each R2>R1

for (int i = 0; i < n; ++i)
{
int sum = 0;
for (int j = i; j < n; ++j)
{
sum += a[j];
if (sum <= d) ans++;
else break;
}
}

O(N2)


Слайд 5

sum(L, R)D for each R’>R.We can precompute prefix sums and than find maxR by binary

3. Good solution

Notice that it’s enough to find maxR(L) = max(R) such sum(L, R)<=D and sum(L, R’)>D for each R’>R.
We can precompute prefix sums and than find maxR by binary search.


Слайд 6

++i)	prefixSum[i] = prefixSum[i - 1] + a[i];for (int i = 0; i < n; ++i){if

3. Good solution

prefixSum[0] = a[0];
for (int i = 1; i < n; ++i)
prefixSum[i] = prefixSum[i - 1] + a[i];
for (int i = 0; i < n; ++i)
{
if (a[i] > d) continue;
int l = i, r = n;
while(r-l>1)
{
int mid = (l + r) / 2;
if (prefixSum[mid] - prefixSum[i] + a[i] <= d)
l = mid;
else
r = mid;
}
ans += l - i + 1;
}

O(NlogN)


Слайд 7

maxR(L-1).In this way out pointer R goes only forward.int right = -1;int sum = 0;for

4. Best solution

Notice that maxR(L)>=maxR(L-1). So we can start finding maxR(L) from maxR(L-1).
In this way out pointer R goes only forward.

int right = -1;
int sum = 0;
for (int i = 0; i < n; ++i)
{
while (right + 1 < n && sum + a[right + 1] <= d)
sum += a[++right];
ans += right - i + 1;
sum -= a[i];
}

O(N)


Слайд 8

Tracing, step 0



Left=0

Right=-1

ANS=0
SUM=0

D=6


Слайд 9

Tracing, step 1



Left=0

Right=0

ANS=0
SUM=1

D=6


Слайд 10

Tracing, step 2



Left=0

Right=1

ANS=0
SUM=3

D=6


Слайд 11

Tracing, step 3



Left=0

Right=2

ANS=0
SUM=6

D=6


Слайд 12

Tracing, step 4



Left=0

Right=2

ANS=3
SUM=6

D=6


Слайд 13

Tracing, step 5



Left=1

Right=2

ANS=3
SUM=5

D=6


Слайд 14

Tracing, step 6



Left=1

Right=2

ANS=5
SUM=5

D=6


Слайд 15

Tracing, step 7



Left=2

Right=2

ANS=5
SUM=3

D=6


Слайд 16

Tracing, step 8



Left=2

Right=3

ANS=5
SUM=6

D=6


Слайд 17

Tracing, step 9



Left=2

Right=3

ANS=7
SUM=6

D=6


Слайд 18

Tracing, step 10



Left=3

Right=3

ANS=7
SUM=3

D=6


Слайд 19

Tracing, step 11



Left=3

Right=3

ANS=8
SUM=3

D=6


Слайд 20

Tracing, step 12



Left=4

Right=3

ANS=8
SUM=0

D=6


Слайд 21

Tracing, step 13



Left=5

Right=3

ANS=8
SUM=-7

D=6


Слайд 22

Tracing, step 14



Left=5

Right=4

ANS=8
SUM=0

D=6


Слайд 23

Tracing, step 15



Left=6

Right=4

ANS=8
SUM=-8

D=6


Слайд 24

Tracing, step 16



Left=6

Right=5

ANS=8
SUM=0

D=6


Слайд 25

Tracing, step 17



Left=6

Right=6

ANS=8
SUM=6

D=6


Слайд 26

Tracing, step 18



Left=6

Right=6

ANS=9
SUM=6

D=6


Слайд 27

Tracing, step 19



Left=7

Right=6

ANS=9
SUM=0

D=6


Слайд 28

Tracing, step 20



Left=7

Right=7

ANS=9
SUM=4

D=6


Слайд 29

Tracing, step 21



Left=7

Right=8

ANS=9
SUM=6

D=6


Слайд 30

Tracing, step 22



Left=7

Right=8

ANS=11
SUM=6

D=6


Слайд 31

Tracing, step 23



Left=8

Right=8

ANS=11
SUM=2

D=6


Слайд 32

Tracing, step 24



Left=8

Right=9

ANS=11
SUM=5

D=6


Слайд 33

Tracing, step 25



Left=8

Right=9

ANS=13
SUM=5

D=6


Слайд 34

Tracing, step 26



Left=9

Right=9

ANS=13
SUM=3

D=6


Слайд 35

Tracing, step 27



Left=9

Right=9

ANS=14
SUM=3

D=6


Слайд 36

Tracing, step 28



Left=9

Right=9

ANS=14
SUM=0

D=6


Слайд 37

pairs (i, j) such that A[i]=B[j].There are N points on circle. Find two points such

Other examples

There are 2 sorted arrays of integers: A and B. Count pairs (i, j) such that A[i]=B[j].
There are N points on circle. Find two points such that distance between them is maximal.
There are N points on circle. Find three points such that area of triangle is maximal.


Слайд 38

http://codeforces.com/blog/entry/4136?locale=ruContest http://codeforces.com/group/Hq4vrJcA4s/contest/206340

Additional links and home task

Article about two pointers method http://informatics.mccme.ru/mod/resource/view.php?id=12716
Discussion on codeforces http://codeforces.com/blog/entry/4136?locale=ru
Contest http://codeforces.com/group/Hq4vrJcA4s/contest/206340


  • Имя файла: two-pointers-method.pptx
  • Количество просмотров: 10
  • Количество скачиваний: 0