Оцените презентацию от 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](/documents_6/5170561ad55cbad2162ab0bb66f25a3b/img0.jpg)
Содержание слайда: TWO POINTERS METHOD
Lyzhin Ivan, 2016
№2 слайд![Problem There is array A with](/documents_6/5170561ad55cbad2162ab0bb66f25a3b/img1.jpg)
Содержание слайда: 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 слайд![. Very primitive solution Sum](/documents_6/5170561ad55cbad2162ab0bb66f25a3b/img2.jpg)
Содержание слайда: 1. Very primitive solution
Sum elements for each pair (L, R).
№4 слайд![. Primitive solution Notice](/documents_6/5170561ad55cbad2162ab0bb66f25a3b/img3.jpg)
Содержание слайда: 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 слайд![. Good solution Notice that](/documents_6/5170561ad55cbad2162ab0bb66f25a3b/img4.jpg)
Содержание слайда: 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 слайд![. Good solution](/documents_6/5170561ad55cbad2162ab0bb66f25a3b/img5.jpg)
Содержание слайда: 3. Good solution
№7 слайд![. Best solution Notice that](/documents_6/5170561ad55cbad2162ab0bb66f25a3b/img6.jpg)
Содержание слайда: 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](/documents_6/5170561ad55cbad2162ab0bb66f25a3b/img7.jpg)
Содержание слайда: Tracing, step 0
№9 слайд![Tracing, step](/documents_6/5170561ad55cbad2162ab0bb66f25a3b/img8.jpg)
Содержание слайда: Tracing, step 1
№10 слайд![Tracing, step](/documents_6/5170561ad55cbad2162ab0bb66f25a3b/img9.jpg)
Содержание слайда: Tracing, step 2
№11 слайд![Tracing, step](/documents_6/5170561ad55cbad2162ab0bb66f25a3b/img10.jpg)
Содержание слайда: Tracing, step 3
№12 слайд![Tracing, step](/documents_6/5170561ad55cbad2162ab0bb66f25a3b/img11.jpg)
Содержание слайда: Tracing, step 4
№13 слайд![Tracing, step](/documents_6/5170561ad55cbad2162ab0bb66f25a3b/img12.jpg)
Содержание слайда: Tracing, step 5
№14 слайд![Tracing, step](/documents_6/5170561ad55cbad2162ab0bb66f25a3b/img13.jpg)
Содержание слайда: Tracing, step 6
№15 слайд![Tracing, step](/documents_6/5170561ad55cbad2162ab0bb66f25a3b/img14.jpg)
Содержание слайда: Tracing, step 7
№16 слайд![Tracing, step](/documents_6/5170561ad55cbad2162ab0bb66f25a3b/img15.jpg)
Содержание слайда: Tracing, step 8
№17 слайд![Tracing, step](/documents_6/5170561ad55cbad2162ab0bb66f25a3b/img16.jpg)
Содержание слайда: Tracing, step 9
№18 слайд![Tracing, step](/documents_6/5170561ad55cbad2162ab0bb66f25a3b/img17.jpg)
Содержание слайда: Tracing, step 10
№19 слайд![Tracing, step](/documents_6/5170561ad55cbad2162ab0bb66f25a3b/img18.jpg)
Содержание слайда: Tracing, step 11
№20 слайд![Tracing, step](/documents_6/5170561ad55cbad2162ab0bb66f25a3b/img19.jpg)
Содержание слайда: Tracing, step 12
№21 слайд![Tracing, step](/documents_6/5170561ad55cbad2162ab0bb66f25a3b/img20.jpg)
Содержание слайда: Tracing, step 13
№22 слайд![Tracing, step](/documents_6/5170561ad55cbad2162ab0bb66f25a3b/img21.jpg)
Содержание слайда: Tracing, step 14
№23 слайд![Tracing, step](/documents_6/5170561ad55cbad2162ab0bb66f25a3b/img22.jpg)
Содержание слайда: Tracing, step 15
№24 слайд![Tracing, step](/documents_6/5170561ad55cbad2162ab0bb66f25a3b/img23.jpg)
Содержание слайда: Tracing, step 16
№25 слайд![Tracing, step](/documents_6/5170561ad55cbad2162ab0bb66f25a3b/img24.jpg)
Содержание слайда: Tracing, step 17
№26 слайд![Tracing, step](/documents_6/5170561ad55cbad2162ab0bb66f25a3b/img25.jpg)
Содержание слайда: Tracing, step 18
№27 слайд![Tracing, step](/documents_6/5170561ad55cbad2162ab0bb66f25a3b/img26.jpg)
Содержание слайда: Tracing, step 19
№28 слайд![Tracing, step](/documents_6/5170561ad55cbad2162ab0bb66f25a3b/img27.jpg)
Содержание слайда: Tracing, step 20
№29 слайд![Tracing, step](/documents_6/5170561ad55cbad2162ab0bb66f25a3b/img28.jpg)
Содержание слайда: Tracing, step 21
№30 слайд![Tracing, step](/documents_6/5170561ad55cbad2162ab0bb66f25a3b/img29.jpg)
Содержание слайда: Tracing, step 22
№31 слайд![Tracing, step](/documents_6/5170561ad55cbad2162ab0bb66f25a3b/img30.jpg)
Содержание слайда: Tracing, step 23
№32 слайд![Tracing, step](/documents_6/5170561ad55cbad2162ab0bb66f25a3b/img31.jpg)
Содержание слайда: Tracing, step 24
№33 слайд![Tracing, step](/documents_6/5170561ad55cbad2162ab0bb66f25a3b/img32.jpg)
Содержание слайда: Tracing, step 25
№34 слайд![Tracing, step](/documents_6/5170561ad55cbad2162ab0bb66f25a3b/img33.jpg)
Содержание слайда: Tracing, step 26
№35 слайд![Tracing, step](/documents_6/5170561ad55cbad2162ab0bb66f25a3b/img34.jpg)
Содержание слайда: Tracing, step 27
№36 слайд![Tracing, step](/documents_6/5170561ad55cbad2162ab0bb66f25a3b/img35.jpg)
Содержание слайда: Tracing, step 28
№37 слайд![Other examples There are](/documents_6/5170561ad55cbad2162ab0bb66f25a3b/img36.jpg)
Содержание слайда: 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](/documents_6/5170561ad55cbad2162ab0bb66f25a3b/img37.jpg)
Содержание слайда: 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