Блог пользователя shashiHIGS

Автор shashiHIGS, 11 лет назад, По-английски

some somebody explain it.thanks in advance..

  • Проголосовать: нравится
  • -1
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
11 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # |
Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

.