uva 929 Number Maze solution

/*********************************   MH RIYAD  *************************************/
#include <bits/stdc++.h>
#include<unordered_set>
#define  pb     push_back
#define  MAX    1010
#define  mod    100000007
#define  read   freopen("input.txt","r",stdin);
#define  write  freopen("output.txt","w",stdout);
#define  inf   (1<<30)
using namespace std;
typedef long long ll ;
typedef unsigned long long ull ;


//struct node
//{
//    int index,w;
//
//};
//bool cmp(node i,node j)
//{
//    return i.w>j.w;
//
//}
//vector<node>v[160006];
//bool mark[160006];
//int main()
//{
//    read;
//    int n,s;
//    scanf("%d",&n);
//    for(int i=2; i<=n*2; i++)
//    {
//        for(int j=1; j<i; j++)
//        {
//            scanf("%d",&s);
//            node no,no2;
//            no.index=i;
//            no.w=s;
//            v[j].pb(no);
//            no2.index=j;
//            no2.w=s;
//            v[i].pb(no2);
//        }
//    }
//
//    for(int i=1; i<=n*2; i++)
//    {
//
//        for(int j=0; j<v[i].size(); j++)
//        {
//            node p=v[i][j];
//            cout<<p.index<<" "<<p.w<<"    ";
//        }
//        cout<<endl;
//    }
//    for(int i=1; i<=n*2; i++)
//    {
//
//        sort(v[i].begin(),v[i].end(),cmp);
//        int len=v[i].size();
//        for(int j=0; j<len; j++)
//        {
//            node p=v[i][j];
//          //  if(!mark[p.w])
//          //  {
//                cout<<p.index<<" ";
//             //   mark[p.w]=true;
//                break;
//           // }
//        }
//    }
//
//    return 0;
//}

int dx[]= {-1,0,0,+1};
int dy[]= {0,+1,-1,0};

struct node
{
    int x,y,w;
    friend bool operator<(node i,node j)
    {
        return i.w>j.w;
    }
};
priority_queue<node>Q;
void dijkstra(int a,int b);
int row,col,graph[MAX][MAX],cost[MAX][MAX];
bool mark[MAX][MAX];
int main()
{
  //  read;
    int test;
    scanf("%d",&test);
    while(test--)
    {
        memset(mark,false,sizeof(mark));
        scanf("%d%d",&row,&col);
        for(int i=0; i<row; i++)
        {
            for(int j=0; j<col; j++)
            {
                scanf("%d",&graph[i][j]);
                cost[i][j]=inf;
            }
        }
        dijkstra(0,0);
        printf("%d\n",cost[row-1][col-1]);
    }
    return 0;
}

void dijkstra(int r,int c)
{
    cost[r][c]=graph[r][c];
    node q;
    q.x=r;
    q.y=c;
    q.w=graph[r][c];
    Q.push(q);

    while(!Q.empty())
    {
        node p=Q.top();
        Q.pop();
        mark[p.x][p.y]=true;
     //   cout<<p.x<<" "<<p.y<<" "<<p.w<<endl;
        for(int i=0; i<4; i++)
        {
            int R=dx[i]+p.x;
            int C=dy[i]+p.y;
            if(R>=0&&R<row&&C>=0&&C<col&&mark[R][C]==false)
            {
                if(cost[p.x][p.y]+graph[R][C]<cost[R][C])
                {
                    cost[R][C]=cost[p.x][p.y]+graph[R][C];
                    node yo;
                    yo.x=R;
                    yo.y=C;
                    yo.w=cost[R][C];
                    Q.push(yo);
                }
            }
        }

    }

}

Two pointer (nice and easy tutorial )

Ref#https://tp-iiita.quora.com/The-Two-Pointer-Algorithm

Introduction

The legendary two pointer approach is one such technique which is less of a talk and more of a discussion on the problems. Binary search is a kind of optimization on the number of trials taken to reach the optimal position and so is the two pointer technique. The approach relies on the sequence following one specific property on which our pointers can move.

​

Lets try to learn how we apply two pointers and what advantages does they offer us. We will be discussing a lot of problems that may help you to understand the technique better and for that, it is highly recommendable that you sit with a pen and a paper.

Motivation Problem: Given a sorted array  A,$A,$ having N$N$ integers. You need to find any pair(i,j)$(i,j)$ having sum as given number X$X$.

Constraints:  Array A$A$ contains about 105${10}^5$ integers with each having values around 109${10}^9$.

Solution: No doubt, we always have an option of iterating all the array values and finding their corresponding integer Aj$A_j$ having value as X$X$ −$-$ Ai$A_i$ using binary search. But, lets see how does the two pointer uses the fact that the array is sorted. For this, we keep two pointers, one at the starting tip of the array and another at the tail. Moving on, we now sum up the values contained at both the pointers. In case, value is greater than required sum, we need to shift the right pointer to the left in order to decrease the value by whatever we can since we don't have any other choice. Similarly, if we encounter the sum of values less than required sum, that we can shift the left  pointer, one unit to the right to bring us more closer to required sum. We keep moving the pointers unless we encounter the situation where Al$A_l$ +$+$ Ar$A_r$   reaches the required given sum as X$X$.

C++ implementation of above approach

#define lli long long
 
bool f(lli sum) {
    int l = 0, r = n-1; //two pointers
    while ( l <= r ) {
       if ( A[l] + A[r] == sum ) return 1;
       else if ( A[l] + A[r] > sum ) r--;
       else l++;
    }
    return 0;
}

Overall complexity of the above solution is O(N)$O(N)$.

Motivation Problem: Given two sorted arrays A$A$ and B,$B,$ each having length N$N$and M$M$ respectively. Form a new sorted merged array having values of both the arrays in sorted format.

Constraints: Array A$A$ and  B$B$ contains about 105${10}^5$ integers,$,$ each having value around 109${10}^9$.

Solution: Since the two arrays are given in sorted order, we can surely do something with two pointers. Let us go step by step.

1. We will introduce read-indices l1$l1$, l2$l2$ to traverse arrays A$A$ and B,$B,$ respectively. and another write-index cnt$cnt$ to store position of the first free cell in the resulting array. Initially all l1,l2$l1,l2$ and cnt$cnt$ will be 0$0$
2. Moving on, if both indices are in range (l1$l1$  <$<$ N$N$ and l2$l2$ <$<$ M$M$), choose minimum of (Ai,$A_i,$   Bj$B_j$) and write it to C[cnt],$C[cnt],$ and increase the respective pointer.

C++ implementation of  the above approach

#define MAX 100005
 
lli C[2*MAX];
 
void merge(lli A[], lli B[])
{
    int l1 = 0, l2 = 0, cnt = 0;
    while ( l1 < n || l2 < m ) {
       if ( l1 < n && l2 < m ) {
          if ( A[l1] < B[l2] ) {
              C[cnt++] = A[l1]; 
              l1++;
          }
          else if ( A[l1] > B[l2] ) {
              C[cnt++] = B[l2];
              l2++;
          }
       }
       else if ( l1 < n ) {
          C[cnt++] = A[l1];
          l1++;
       }
       else if ( l2 < m ) {
          C[cnt++] = B[l2];
          l2++; 
       }
    }
    return;
}

We basically traversed both the arrays in the sorted order of combined elements and hence kept inserting the elements into the new array that we needed.

Overall complexity of the solution is O(N+M).$O(N+M).$  

Move on to the next problem if you are sure, you understood the above problems right and have implemented them yourself. I would like you to think as much as you can in all the problems and question yourself, Why?. Thinking is a healthy process and good for exercising your brain to understand the concepts a lot better.

Motivation Problem: Given an array having N$N$ integers,$,$ find the contiguous subarray having sum as great as possible,$,$ but not greater than M$M$. For details on the statement, refer the problem link here

Constraints: Array can have atmost 105${10}^5$ elements and each number will be non-negative and can be as big as 109${10}^9$.

Solution: As the given array contains positive elements, cumulative sum will indeed be increasing as you go on from left to right in the array. If you have already read the binary search tutorial, I am pretty sure you must have found out a way to solve it already.

Solution using binary search:

• Store cumulative sum at each index in a separate auxiliary array.
• Treat each index as startIndex of the required contiguous subarray, find a corresponding endIndex such that the following equation holds true.

cum[endIndex] - cum[startIndex-1] <= M and cum[endIndex+1] - cum[startIndex-1] > M

I leave the implementation for this on the part of the reader to discuss in comments. Now, let us see how can we solve the problem using the two pointers technique.

• We introduce two pointers l,r$l,r$  denoting startIndex and endIndex of our contiguous subarray, with both of them at the tip of the array.
• We now start extending our right pointer r$r$  provided sum[l,r]$sum[l,r]$ <=$<=$ M$M$ Once, we reach at such a stage, we don't have any option but to move the left pointer as well and start decreasing the sum until we arrive at the situation where we can extend our right pointer again.
• As and when we reach the point, where we need to shift the left pointer, we keep updating our maximum sum we have achieved so far.

C++ implementation of the above approach

#include <bits/stdc++.h>
#define lli long long
#define MAX 1000005
 
using namespace std;
 
lli A[MAX];
 
int main()
{
    int n;
 lli sum = 0;  
    cin >> n;
   
    for ( int i = 0; i < n; i++ ) cin >> A[i];
    
    int l = 0, r = 0;
 lli ans = 0;
 
    while ( l < n ) {
       while ( r < n && sum + A[r] <= M ) {
           sum += A[r];
           r++;
       }
       ans = max(ans, sum);
       sum -= A[l];
       l++;
    }
 
    cout << ans << endl;
    return 0;
}

That was a lot of fun, learning one topic in such a less amount of time. Excited still!? Lets see how much more you can grasp. Moving on to the next problem...

Motivation Problem: Given an array containing N$N$ integers, you need to find the length of the smallest contiguous subarray that contains atleast K$K$ distinct elements in it. Output "−1$-1$" if no such subarray exists.

Constraints: Number of elements in the array are around one million with each of them having value as large as 109${10}^9$ .

Solution: Now, thats where the legendary two pointer technique is the only way to your rescue. If you are reading this, I am pretty much sure that you have read the tutorial on STL containers. The STL container you need to know about here is set.

Going by our own traditional way as we approached in the previous problem, we take two pointers l,r$l,r$  with both at the tip of the array. We keep on shifting the right pointer unless we have K$K$ elements into the set as set will only contains distinct elements and will ignore the insertion of duplicate elements. As soon as we meet our condition, we now shift the left pointer unless the size of the set becomes <$<$ K$K$. We also update the length of our minimum contiguous subarray as soon as we are ready to shift the left pointer.

C++ implementation of above approach

int l = 0, r = 0, ans = INF;
map <int , int >  cnt;
 
while ( l < n ) {
    while ( r < n && s.size() < K ) {
       s.insert(A[r]);
       cnt[A[r]]++;
       r++;
    }
    if (s.size() >=K) {
  ans = min(ans, r-l);
 }
    if ( cnt[A[l]] == 1 ) s.erase(A[l]); 
    cnt[A[l]]--; 
    l++;
}
if ( ans == INF ) ans = -1;
 
cout << ans << endl;

Great, that was just kind of similar to previous problem. Lets move on to the final problem and you shall be ready to explore.

Motivation Problem:  Given an array having N$N$ integers, you need to find out a subsequence of K$K$ integers such that these  K$K$ integers have the minimum hustle. Hustle of a sequence is defined as sum of pair-wise absolute differences divided by the number of pairs. For details on the statement, refer the problem link here

Constraints: Both N$N$ and K are less than or equal to 105${10}^5$ and each element has absolute value of around 109${10}^9$.

Solution: Since, this will be the last problem, let us try to spend some more time discussing the solution in detail.

You really don't want this to be the last problem of the discussion, don't you?

Anyway, lets see what the problem demands this time. The number of pairs in the function wont be of much significance since we will always be dividing by fixed number of C(K,2)$C(K,2)$ pairs. So, we can ignore the denominator here and the way function "hustle"  is defined surely tells us that the numerator of the function will be minimum as much as those K$K$ integers will be close to each other. Since, hustle function is nothing but merely summation of absolute difference of pairs. Why not just sort the numbers and consider each consecutive contiguous subarray of length K$K$ for this? That's it. You are done for good !

If you still doubt how we have reduced the problem from subsequence of length K$K$to contiguous substring of length K$K$, try to contradict yourself by removing one element from contiguous K$K$ elements and taking some other element, you will surely realize, what wrong happened their and how much the absolute difference increased overall. Try to prove this way to give yourself complete satisfaction about the greedy technique used over here.

C++ implementation of above approach.

#include <bits/stdc++.h>
using namespace std;
 
#define lli long long
#define MAX 1000006
 
lli A[MAX],C[MAX];
 
int main()
{
    int l = 1, r = 2, st,en,n;
    
    lli sum,ans;
 
    cin >> n >> k;
    
    for ( int i = 1; i <= n; i++ ) cin >> A[i];
 
    sort(A+1, A+n+1);
 
    cum[0] = 0;
    for ( int i = 1; i <= n; i++ ) cum[i] = cum[i-1] + A[i];
    
    while ( r <= k ) {
       sum += (A[r]*(r-l) - (cum[r-1] - cum[l-1]));
       r++;
    }
 
    st = 1, en = k, ans = sum;
 
    while ( r <= n ) {
       sum -= (cum[r-1] - cum[l] - A[l]*(r-l-1));
       l++;
       sum += (A[r]*(r-l) - (cum[r-1] - cum[l-1]));
        
       if ( ans > sum ) {
          ans = sum;
          st = l;
          en = r;
       }
       r++;
    }
    return 0;
}

Overall complexity of the solution is O(NlogN)$O(NlogN)$ +$+$ O(N)