When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

shashiHIGS's blog

By shashiHIGS, 11 years ago, In English

some somebody explain it.thanks in advance..

  • Vote: I like it
  • -1
  • Vote: I do not like it

| Write comment?
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

google "two pointer algorithm site:codeforces.com"
one of results: http://static.codeforces.com/blog/entry/4586

»
11 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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 find rx. rx is a minimal number such that subarray x... rx is good. Obviously, all subarrays which starts at x and ends after rx is good.

If you notice that r1 ≤ r2 ≤ ... ≤ rN, you can use 'two pointers' method. The first pointer is x and the second one is rx. 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 is O(n), because each of pointers makes  ≤ N steps.

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.

»
11 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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,

    1. 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.

    2. 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 :-)

»
7 years ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

.