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

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Two pointers method, слайд №1Two pointers method, слайд №2Two pointers method, слайд №3Two pointers method, слайд №4Two pointers method, слайд №5Two pointers method, слайд №6Two pointers method, слайд №7Two pointers method, слайд №8Two pointers method, слайд №9Two pointers method, слайд №10Two pointers method, слайд №11Two pointers method, слайд №12Two pointers method, слайд №13Two pointers method, слайд №14Two pointers method, слайд №15Two pointers method, слайд №16Two pointers method, слайд №17Two pointers method, слайд №18Two pointers method, слайд №19Two pointers method, слайд №20Two pointers method, слайд №21Two pointers method, слайд №22Two pointers method, слайд №23Two pointers method, слайд №24Two pointers method, слайд №25Two pointers method, слайд №26Two pointers method, слайд №27Two pointers method, слайд №28Two pointers method, слайд №29Two pointers method, слайд №30Two pointers method, слайд №31Two pointers method, слайд №32Two pointers method, слайд №33Two pointers method, слайд №34Two pointers method, слайд №35Two pointers method, слайд №36Two pointers method, слайд №37Two pointers method, слайд №38
Скачать
Вы можете ознакомиться и скачать презентацию на тему Two pointers method. Доклад-сообщение содержит 38 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

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

Слайд 1


TWO POINTERS METHOD Lyzhin Ivan, 2016
Описание слайда:
TWO POINTERS METHOD Lyzhin Ivan, 2016

Слайд 2


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.
Описание слайда:
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


1. Very primitive solution Sum elements for each pair (L, R).
Описание слайда:
1. Very primitive solution Sum elements for each pair (L, R).

Слайд 4


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
Описание слайда:
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

Слайд 5


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.
Описание слайда:
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


3. Good solution
Описание слайда:
3. Good solution

Слайд 7


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.
Описание слайда:
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.

Слайд 8


Tracing, step 0
Описание слайда:
Tracing, step 0

Слайд 9


Tracing, step 1
Описание слайда:
Tracing, step 1

Слайд 10


Tracing, step 2
Описание слайда:
Tracing, step 2

Слайд 11


Tracing, step 3
Описание слайда:
Tracing, step 3

Слайд 12


Tracing, step 4
Описание слайда:
Tracing, step 4

Слайд 13


Tracing, step 5
Описание слайда:
Tracing, step 5

Слайд 14


Tracing, step 6
Описание слайда:
Tracing, step 6

Слайд 15


Tracing, step 7
Описание слайда:
Tracing, step 7

Слайд 16


Tracing, step 8
Описание слайда:
Tracing, step 8

Слайд 17


Tracing, step 9
Описание слайда:
Tracing, step 9

Слайд 18


Tracing, step 10
Описание слайда:
Tracing, step 10

Слайд 19


Tracing, step 11
Описание слайда:
Tracing, step 11

Слайд 20


Tracing, step 12
Описание слайда:
Tracing, step 12

Слайд 21


Tracing, step 13
Описание слайда:
Tracing, step 13

Слайд 22


Tracing, step 14
Описание слайда:
Tracing, step 14

Слайд 23


Tracing, step 15
Описание слайда:
Tracing, step 15

Слайд 24


Tracing, step 16
Описание слайда:
Tracing, step 16

Слайд 25


Tracing, step 17
Описание слайда:
Tracing, step 17

Слайд 26


Tracing, step 18
Описание слайда:
Tracing, step 18

Слайд 27


Tracing, step 19
Описание слайда:
Tracing, step 19

Слайд 28


Tracing, step 20
Описание слайда:
Tracing, step 20

Слайд 29


Tracing, step 21
Описание слайда:
Tracing, step 21

Слайд 30


Tracing, step 22
Описание слайда:
Tracing, step 22

Слайд 31


Tracing, step 23
Описание слайда:
Tracing, step 23

Слайд 32


Tracing, step 24
Описание слайда:
Tracing, step 24

Слайд 33


Tracing, step 25
Описание слайда:
Tracing, step 25

Слайд 34


Tracing, step 26
Описание слайда:
Tracing, step 26

Слайд 35


Tracing, step 27
Описание слайда:
Tracing, step 27

Слайд 36


Tracing, step 28
Описание слайда:
Tracing, step 28

Слайд 37


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.
Описание слайда:
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


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
Описание слайда:
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
Похожие презентации
Mypresentation.ru
Загрузить презентацию