Презентация Two pointers method онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Two pointers method абсолютно бесплатно. Урок-презентация на эту тему содержит всего 38 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:38 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:546.46 kB
- Просмотров:70
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: 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.
№3 слайд
Содержание слайда: 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
№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.
№6 слайд
Содержание слайда: 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.
№8 слайд
Содержание слайда: Tracing, step 0
№9 слайд
Содержание слайда: Tracing, step 1
№10 слайд
Содержание слайда: Tracing, step 2
№11 слайд
Содержание слайда: Tracing, step 3
№12 слайд
Содержание слайда: Tracing, step 4
№13 слайд
Содержание слайда: Tracing, step 5
№14 слайд
Содержание слайда: Tracing, step 6
№15 слайд
Содержание слайда: Tracing, step 7
№16 слайд
Содержание слайда: Tracing, step 8
№17 слайд
Содержание слайда: Tracing, step 9
№18 слайд
Содержание слайда: Tracing, step 10
№19 слайд
Содержание слайда: Tracing, step 11
№20 слайд
Содержание слайда: Tracing, step 12
№21 слайд
Содержание слайда: Tracing, step 13
№22 слайд
Содержание слайда: Tracing, step 14
№23 слайд
Содержание слайда: Tracing, step 15
№24 слайд
Содержание слайда: Tracing, step 16
№25 слайд
Содержание слайда: Tracing, step 17
№26 слайд
Содержание слайда: Tracing, step 18
№27 слайд
Содержание слайда: Tracing, step 19
№28 слайд
Содержание слайда: Tracing, step 20
№29 слайд
Содержание слайда: Tracing, step 21
№30 слайд
Содержание слайда: Tracing, step 22
№31 слайд
Содержание слайда: Tracing, step 23
№32 слайд
Содержание слайда: Tracing, step 24
№33 слайд
Содержание слайда: Tracing, step 25
№34 слайд
Содержание слайда: Tracing, step 26
№35 слайд
Содержание слайда: Tracing, step 27
№36 слайд
Содержание слайда: 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.
№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
Скачать все slide презентации Two pointers method одним архивом:
