- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Two pointers method презентация
Содержание
- 1. Two pointers method
- 2. Problem There is array A with N
- 3. 1. Very primitive solution Sum elements for
- 4. 2. Primitive solution Notice that sum(L, R)
- 5. 3. Good solution Notice that it’s enough
- 6. 3. Good solution prefixSum[0] = a[0]; for
- 7. 4. Best solution Notice that maxR(L)>=maxR(L-1). So
- 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. Other examples There are 2 sorted arrays
- 38. Additional links and home task Article about
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
Слайд 2Problem
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.
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.
Слайд 31. 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++;
}
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)
Слайд 42. 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)
Слайд 53. 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.
We can precompute prefix sums and than find maxR by binary search.
Слайд 63. 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;
}
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)
Слайд 74. 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.
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)
Слайд 37Other 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.
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.
Слайд 38Additional 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
