some somebody explain it.thanks in advance..

# | User | Rating |
---|---|---|

1 | tourist | 3438 |

2 | moejy0viiiiiv | 3288 |

3 | W4yneb0t | 3218 |

4 | LHiC | 3196 |

5 | TakanashiRikka | 3178 |

6 | Petr | 3163 |

7 | Um_nik | 3150 |

8 | izrak | 3109 |

9 | ershov.stanislav | 3105 |

10 | mnbvmar | 3018 |

# | User | Contrib. |
---|---|---|

1 | rng_58 | 179 |

2 | tourist | 171 |

3 | csacademy | 170 |

4 | Petr | 162 |

5 | Swistakk | 158 |

6 | Errichto | 156 |

7 | Zlobober | 152 |

7 | matthew99 | 152 |

9 | zscoder | 139 |

10 | Endagorion | 138 |

some somebody explain it.thanks in advance..

↑

↓

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/22/2017 14:42:40 (c3).

Desktop version, switch to mobile version.

User lists

Name |
---|

google "two pointer algorithm site:codeforces.com"

one of results: http://static.codeforces.com/blog/entry/4586

The link is broken

Ohhh man... this comment is 3 years old.

It's kind of optimization. Consider problem 190D - Non-Secret Cypher. The stupid solution goes over all subarrays and checks whether it's good or not. Now we notice that if subarray is 'good', then all its superarrays is 'good' too. Let's go over all left borders

x(1 ≤x≤N) and for each of them findr_{x}.r_{x}is a minimal number such that subarrayx...r_{x}is good. Obviously, all subarrays which starts atxand ends afterr_{x}is good.If you notice that

r_{1}≤r_{2}≤ ... ≤r_{N}, you can use 'two pointers' method. The first pointer isxand the second one isr_{x}. When you move the first one right, the second one can only move right too. No matter how many operations you perform in one step, algo's running time isO(n), because each of pointers makes ≤Nsteps.The other examples of two pointers is Z-function, prefix-function (the last one is not so straight). Also you can take a look at problem 'Pyramid base' from IOI'08 (statement). Last subtask can solved using this idea.

In the previous blog cited Link:

Given two arrays (A and B) sorted in ascending order, and an integer x. we need to find i and j, Such That a [i] + b [j] is equal to X.

Someone could prove why the two pointer technique works ? also if you know that there are n ^ 2 pairs, as is possible if two pointers only checks O (n) pairs.

I'm confused about this issue, someone explain in detail.

well, as you've defined the sample problem, array A and B are already sorted in ascending order and we assume, n = size of A and m = size of B, i = n-1 and j=0

Now take into consideration that,

if A[i]+B[j]<X then A[i-1]+B[j]<X for sure (as they're already sorted, A[i]>=A[i-1]). So in this case, there is no benefit to iterate i downward keeping j fixed. Instead, we should just increase j while j<n-1 and A[i]+B[j]<X.

if A[i]+B[j]>=X, then there may be more A[y], 0<=y<=i-1 such that , A[y]+B[j]>=X. so we should just decrease i while i>0 and A[i]+B[j]>=X.

So there will be in total (n+m) operations as i will be moved between n-1 to 0 and j will be moved between 0 to m-1 and i will never be increased as well as j will never be decreased.

Hope it helps :-)

.

See this post in quora..It will explain it very well..The Two Pointer Algorithm