How to Share Internet Connection Between PC and Android Phone Using WiFi

Between PC and Android Phone Using WiFi

WiFi Ad-Hoc Networking is a popular method to share internet connection between  computers (pc or laptop) or between a computer and a smartphone that has built in WiFi. Unfortunately, this method of networking is not supported by Android since it was released until the time of this writting. One of the popular method to enable ad hoc mode on Android devices is by  changing a WiFi configuration file located on /system/etc directory called tiwlan.ini. But this method is specific to phone’s WiFi chipset and you need root access to change the file. The tiwlan.ini is a configuration file for Texas Instruments WiFi chipset (e.g HTC dream) so you will not find it on Samsung Spica that use Broadcom WiFi chipset.

Another alternative method is by using a software based virtual access point that using Windows 7’s Wireless Hosted Network technology. This method only runs on Windows 7 and hardware specific. Currently i found two best virtual access point softwares, Virtual Router and Connectify. They both operate in the same maner and very easy to use. I have tested both of them to share internet connection from my PC that used  Sierra Wireless USBConnect 881 modem for internet access and an external TP-Link TL-WN31G Wireless USB adapter with my Samsung Spica.

Here is the guide on how to use virtual router and connectify

• Fill in the settings panel with your prefered WiFi name, password and internet connection to share

Virtual Router

Connectify
• Click start button to start sharing
• On your Wireless Connection Status, click Details to get the network connection information, note the IPV4 Address

To Download the software  click the link below
Click to download Virtual Router

Lists

Lists

Lists are good when data needs to be reorganized a lot. To be able to use STL lists add this before you start using them in your source code:

  #include <list>

Suppose that T is any type or class - say an int, a float, a struct, or a class, then

  list<T> l;

declares a new and empty list called l. Given an object l:

test to see if l is empty:

           l.empty()

find how many items are in l:

           l.size()

push a t:T onto the end of l:

           l.push_back(t)

pop the last off l:

           l.pop_back()

push a t:T onto the start of l:

           l.push_front(t)

pop the front of l off l:

           l.pop_front()

get the front item of l:

           l.front()

• change the front item:

           l.front() = expression.

get the back item of l:

           l.back()

• change the back item:

           l.back() = expression.

• Sort the list:

           l.sort()

• Clear the list:

           l.clear()

• Merge in a sorted list into a sorted list:

           l.merge(list_of_sorted_elements)

• Reverse the list:

           l.reverse()

Assign a copy of q1 to q:

           q = q1

Maximum Triangle Area (Part 3 and final)

After second part, our algorithm became something like this -
for each 0 <= i < n, initialize A = P_i, B = P_{(i + 1) % n}, C = P_{(i + 2) % n}, then move C counter clockwise until area non-decreasing, move B to its adjacent point counter clockwise, if area non-decreasing, move C again until area non decreasing and so on. You will get the maximum area for each A and output the maximum of these areas. For a given point starting point P_i, if the maximum area is ABC. We can say ABC is 'stable' triangle for A, in other word s(p_i, P_{i + 1}, P_{i + 2}) = ABC, that means we cannot move B or C any further by not decreasing the area.

Now, after getting a maximum ABC for a fixed first point P_i, we will start with P_{i + 1}, P_{i + 2} and P_{i + 3}. We get A'B'C' as a stable triangle i.e. s(p_i, p_{i + 1}, p_{i + 2}) = A'B'C'. Hence our algorithm is O(n ^ 2). But it can be proved that, rather than, start from P_{i + 1} as a second point and P_{i + 2} as a third point, we can start with B and C as a second and third point and get the same result, i.e. s(P_{i + 1}, P_{i + 2}, P_{i + 3}) = s(P_{i + 1}, B, C), where s(P_i, P_{i + 1}, P_{i + 2}) = ABC.

Lets assume that we are wrong, and s(P_{i + 1}, P_{i + 2}, P_{i + 3}) = A'B'C' > s(p_i, P_{i + 1}, P_{i + 2}).

Case 1:
B' < B and C' = C


We know that,
ABC >= AB'C (otherwise largest triangle for A would be AB'C)
=> ABC + BB'A >= AB'C + BB'A
=> AB'BC >= AB'C + BB'A
=> AB'C + BB'C >= AB'C + BB'A
=> BB'C >= BB'A
=> BB'C >= BB'A' (for base BB' area is non decreasing from BB'C to BB'A, so it
will be non decreasing from BB'A to BB'C)
=> BB'C + A'B'C >= BB'A' + A'B'C
=> A'B'BC >= BB'A' + A'B'C
=> A'BC + BB'A' >= BB'A' + A'B'C
=> A'BC >= A'B'C
=> A'BC >= A'B'C' ...... [1] (as C = C')

So, for case 1, s(P_{i + 1}, P_{i + 2}, P_{i + 3}) = s(P_{i + 1}, B, C).

Case 2:
Let's say, A'B'C' is the largest triangle for first point A'.
Where, B' < B and C' > C. See the following image.



For first point A, ABC is the largest trianlge,
So, ABC >= AB'C
=> ABC + BB'C >= ABC + BB'C
=> ABC + BB'C >= AB'BC
=> ABC + BB'C >= ABC + BB'A
=> BB'C >= BB'A
i.e. BB'A <= BB'C Hence, BB'A <= BB'C' (otherwise, BB'A > BB'C and BB'A <= BB'C, which is not possible for a convex polygon) So, BB'A' <= BB'C' ... [2] (as the triangle area non increasing by moving C' to A, it will be non increasing from A to A') Now as we are considering, for first point A', the largest area triangle is A'B'C'. So, A'B'C' > A'BC'
=> A'B'C' + BB'A' > A'BC' + BB'A
=> A'B'C' + BB'A' > A'B'BC'
=> A'B'C' + BB'A' > A'B'C' + BB'C'
=> BB'A' > BB'C', this contradicts to [2].

So it is not possible to have, A'B'C' > A'BC' i.e. for case 2, s(P_{i + 1}, P_{i + 2}, P_{i + 3}) = s(P_{i + 1}, B, C).

Case 3:
Let's say, A'B'C' is the largest triangle for fixed first point A', where,
B' < B and C' < C

As ABC is the largest triangle having first point A,
either ABC' >= AB'C' (by moving B' to B, area increases) .. (3A)
or AB'C >= AB'C' (by moving C' to C, area increases) .. (3B)

Case 3A
ABC' >= AB'C'
=> ABC' + BB'A >= AB'C' + BB'A
=> AB'BC' >= AB'C' + BB'A
=> AB'C' + BB'C' >= AB'C' + BB'A
=> BB'C' >= BB'A
=> BB'C' >= BB'A' (As by moving C' to A area non increasing, moving A to A' will area be non increasing)
=> BB'C + A'B'C' >= BB'A' + A'B'C'
=> BB'A'C' >= BB'A' + A'B'C'
=> BB'A' + A'BC' >= BB'A' + A'B'C'
=> A'BC >= A'B'C'

So it is not possible to have, A'B'C' > A'BC' i.e. for case 3A, s(P_{i + 1}, P_{i + 2}, P_{i + 3}) = s(P_{i + 1}, B, C).

Case 3B
AB'C >= AB'C'
=> AB'C + CC'B' >= AB'C' + CC'B'
=> AB'C'C >= AB'C' + CC'B'
=> AB'C' + CC'A >= AB'C' + CC'B'
=> CC'A >= CC'B'
=> CC'A' >= CC'B' (As moving A to B', area decreases, it's not possible moving A' to B' area increases)
=> CC'A' + A'B'C' >= CC'B' + A'B'C'
=> A'B'C'C >= CC'B' + A'B'C'
=> CC'B' + A'B'C >= CC'B' + A'B'C'
=> A'B'C >= A'B'C'

So it is not possible to have, A'B'C' > A'B'C i.e. for case 3B, s(P_{i + 1}, P_{i + 2}, P_{i + 3}) = s(P_{i + 1}, B, C).

Case 4:
C' < C and B' = B

Here,
ABC >= ABC'
=> ABC + CC'A >= ABC' + CC'A
=> ABC + CC'A >= ABC'C
=> ABC + CC'A >= ABC + CC'B
=> CC'A >= CC'B
=> CC'A' >= CC'B
=> CC'A' + A'BC' >= CC'B + A'BC'
=> A'BC'C >= CC'B + A'BC'
=> A'BC + CC'B >= CC'B + A'BC'
=> A'BC >= A'BC'
=> A'BC >= A'B'C' (as B' = B)

So it is not possible to have, A'B'C' > A'BC i.e. for case 3B, s(P_{i + 1}, P_{i + 2}, P_{i + 3}) = s(P_{i + 1}, B, C).

Case 5:
B' > B and C' < C


Now,
A'BC >= A'BC' (From case 4)
=> A'BC + CC'B >= A'BC' + CC'B
=> A'BC'C >= A'BC' + CC'B
=> A'BC' + CC'A' >= A'BC' + CC'B
=> CC'A' >= CC'B
=> CC'A' >= CC'B'
=> CC'A' + A'B'C' >= CC'B' + A'B'C'
=> CC'B'A' >= CC'B' + A'B'C'
=> CC'B' + A'B'C >= CC'B' + A'B'C'
=> A'B'C >= A'B'C'

So it is not possible to have, A'B'C' > A'B'C i.e. for case 5, s(P_{i + 1}, P_{i + 2}, P_{i + 3}) = s(P_{i + 1}, B, C).

So, from all of the 5 possible cases, we found that, s(P_{i + 1}, P_{i + 2}, P_{i + 3}) = s(P_{i + 1}, B, C). So our algorithm will still work, if we start our iteration for first point i = i + 1, without changing the position 2nd and 3rd point. We will move first point from 0 to n - 1, and 2nd and 3rd point will also not move more than n times. So our algorithm in worst case is O (3 * n) = O(n)

My simple implementation in C++.

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<vector>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<cassert>
#include<sstream>
#include<queue>
#include<stack>
#include<iostream>
using namespace std;

struct Point {
    int x;
    int y;
    Point(int _x, int _y) : x(_x), y(_y) {}
    Point() : x(0), y(0) {}
    bool operator <(const Point& p) const {
        return x < p.x || (x == p.x && y < p.y);
    }
};

bool left_turn(const Point& p1, const Point& p2, const Point& p3) {
    return (p2.y - p1.y) * (p3.x - p1.x) - (p2.x - p1.x) * (p3.y - p1.y) > 0;
}

// Returns list of points of convex hull in counter clockwise
// The last point and first point will be equal
vector<Point> convex_hull(vector<Point> p) {
    vector<Point> ret;
    sort(p.begin(), p.end());
    // build lower hull
    for (int i = 0; i < p.size(); ++i) {
        while (ret.size() >= 2 &&
               left_turn(ret[ret.size() - 2], ret[ret.size() - 1], p[i])) {
            ret.pop_back();
        }
        ret.push_back(p[i]);
    }
    int lower_hull_size = ret.size();
    // build upper hull
    for (int i = p.size() - 2; i >= 0; --i) {
        while (ret.size() - lower_hull_size >= 1 &&
               left_turn(ret[ret.size() - 2], ret[ret.size() - 1], p[i])) {
            ret.pop_back();
        }
        ret.push_back(p[i]);
    }
    return ret;
}

double triangle_area (const Point& p1, const Point& p2, const Point& p3) {
    return abs((double) p1.x * p2.y +
               (double) p2.x * p3.y +
               (double) p3.x * p1.y -
               (double) p1.y * p2.x -
               (double) p2.y * p3.x -
               (double) p3.y * p1.x) / 2.0;
}

int main (void)
{
    int n;
    while (scanf("%d", &n) && n != -1) {
        vector<Point> p;
        for (int i = 0; i < n; ++i) {
            int x, y;
            scanf("%d%d", &x, &y);
            p.push_back(Point(x, y));
        }
        p = convex_hull(p); p.pop_back();
        int i = 0;
        int j = i + 1;
        int k = j + 1;
        double res = 0.;
        while (true) {
            double area = triangle_area(p[i], p[j], p[k]);
            while (true) {
                while (true) {
                    int nk = (k + 1) % n;
                    double narea = triangle_area(p[i], p[j], p[nk]);
                    if (narea >= area) {
                        k = nk;
                        area = narea;
                    } else {
                        break;
                    }
                }
                int nj = (j + 1) % n;
                double narea = triangle_area(p[i], p[nj], p[k]);
                if (narea >= area) {
                    j = nj;
                    area = narea;
                } else {
                    break;
                }
            }
            if (area > res) res = area;
            i++;
            if (i == j) j = (j + 1) % n;
            if (j == k) k = (k + 1) % n;
            if (i == n) break;
        }
        printf("%.2lf\n", res);
    }
    return 0;
}

Maximum Triangle Area (Part 1)

Today I'll discuss about another interesting problem. Though the analysis is big, hopefully you'll find it interesting.

Problem name: Maximum Triangle Area
Problem description:
Given n distinct points on a plane, your task is to find the triangle that have the maximum area, whose vertices are from the given points.

The most obvious solution is trying all possible triangle and find out the maximum area. The complexity of that algorithm is O(n^3). Which is huge as n can be as large as 50000.

So what can we do now? An interesting fact is, we can solve this problem by only considering the points of the convex hull for the given set of points. This will work because, if there is a triangle which has a vertex A which is not in the boundary of the convex hull, there will be always a point X in convex hull such that, by moving A to X we can increase the area of the triangle. Let's see an example -

We have a set of points {A, B, C, D, E, F, G, H, I}. The convex hull of these points consists of {D, E, F, G, H, I}. But let's claim that the largest triangle using these points is ABC. None of it's vertex is in convex hull. Let's say, BC is the base of this triangle and AP (perpendicular distance from A to BC) is the height of the triangle. So, the area of the triangle is 0.5 * BC * AP. Now draw a line parallel to the BC which goes through A. As A is inside the convex hull, you will find at least one vertex from the convex hull which is on the other side of the parallel line. Here in our example, we found D and BC are in the opposite side of the parallel line, so perpendicular distance from D to BC (DQ) is greater than AP. Hence, 0.5 * BC * AB < 0.5 * BC * DQ. So, triangle area DBC > triangle area ABC. See the following picture to make it clear -


Now, we got a triangle DBC which has larger area than ABC, but yet we have two vertices in it which are not in the convex hull. Now in the similar way considering DB as a base, and drawing a parallel line of DB which goes through C, we will find that area of DBF is greater than area of DBC. In the next step we can easily show again, that area of DBH is greater than the area of DBF. So we found that, maximum area triangle can be found using only convex hull vertices.



But if all of the given points is in the convex hull, our algorithm is still O(n ^ 3). Using the convex hull property we can improve it. Now our problem is finding the largest triangle using the vertices of a convex polygon. Let's say we have n vertices 0 to n - 1. We will try to find out three vertices A, B, C in clockwise direction from these vertices which will form the maximum triangle.

Now for a given AB, rather than iterating all of the points between B and A, to find the C, we can use ternary search to find C, as if we consider AB as a base, and iterate from the next point of B one by one, the height (of the triangle ABC) will increase in every step up to a certain vertex, and after that height will decrease in every step. This way, we can ternary search the point C for every possible AB, and the complexity will become (n ^ 2 log n), which is still not enough.

As, the analysis becoming large and large, we'll discuss the other improvements in the next part.

(Special thanks to Anna Fariha for helping me understanding some proofs of this analysis.)

Perfect Memory

Problem name: Perfect Memory
Problem source: Topcoder, SRM 513, Div 1 - 500
Link: http://www.topcoder.com/stat?c=problem_statement&pm=11500 (Log in is required to see the problem)

In this problem you have a board having N * M cells. Each cell has a symbol in it's back. Each symbol is in exactly two cells in the board. So there will be (N * M) / 2 symbols. In each move you can turn two cells one by one to see the symbols behind them. If these two symbols differ, both the cell turned back to hide the symbols again. If both the symbols are same, they will remain same and never turn back again. What is the expected number of moves to make all the symbols visible, if you have the perfect memory?

Note that, having perfect memory, you'll never forget what was the symbol in a cell which you saw, but turned back. In this problem it's guaranteed that N * M will be even.

I couldn't solve this problem in real contest. I thought in each turn both of the cells will be turned simultaneously. But in the problem statement it was clearly mentioned that, two cells will be turned one by one. It seems that I am not the only one who got this wrong.

This problem can be solved by dynamic programming. Our state will be (total, seen, turn). Here,
total = number of symbols for which both cells are not seen yet i.e. at least one cell is unseen. So we are actually considering (2 * total) cells.
seen = number of symbols partially seen i.e. number of cells of which exactly one cell is seen.
turn = Is this the first turn or second turn of the move? We know each move consists of two turns.

Initially, total = (N * M) / 2, seen = 0, and turn = FIRST.

Boundary condition: If total = 0, we don't have any symbol left to consider, so expected number will be zero.

In state (total, seen, turn), we have (total * 2 - seen) cells we didn't see yet. Lets say unseen = total * 2 - seen.

Now if the turn = FIRST, here we will always open an unseen cell and two things can happen after turning a cell on.
1. With p1 probability the cell contains a symbol which is already seen in another cell.
2. With p2 probability the cell contains a new symbol which is not visible before.

Here,
p1 = seen / unseen
p2 = 1.0 - p1

If (1) happens, we will just turn on the other symbol we already saw, and both will remain open forever. So our new state will be (total - 1, seen - 1, FIRST) and one move will be completed.
If (2) happens, new state will be (total, seen + 1, SECOND)

exp_move(total, seen, FIRST) = p1 * (1 + exp_move(total - 1, seen - 1, FIRST)) +
p2 * (exp_move(total, seen + 1, SECOND)

Note that, in first option we completed a move, so added +1, but in second option move is not done yet.

If turn = SECOND, we'll open another unseen cell. Three things can happen
1. With probability p1, symbol in the SECOND turn matches with the symbol of the FIRST turn.
Here p1 = 1 / unseen
2. With probability p2, symbol in the SECOND move matches with a symbol which is previously seen, but not seen in the first turn of this move. So,
p2 = seen / unseen - p1 = (seen - 1) / unseen
3. With probability p3, symbol in the SECOND move is completely a new symbol.
p3 = 1 - p2 - p3

If (1) happens, this pair will remain visible, so our state will be (total - 1, seen - 1, FIRST) and one move will be completed.
If (2) happens, this pair will be turned back, but we know both cells of the symbol of last turn. So we'll open both symbol in next move, so two moves will be completed in this case and new state will be (total - 1, seen - 1, FIRST).
If (3) happens, just another seen added. So state will be (total, seen + 1, FIRST), and one move will be completed.

exp_move(total, seen, SECOND) = p1 * ((exp_move(total - 1, seen - 1, FIRST) + 1) +
p2 * ((exp_move(total - 1, seen - 1, FIRST) + 2) +
p3 * ((exp_move(total, seen + 1, FIRST) + 1)

My solution in C++:

#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <map>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <queue>
#include <cstring>
#include <set>
#include <ctime>
#include <cfloat>
using namespace std;

typedef long long i64;
#define I64 "%lld"
#define rep(i,n) for (i=0; i < (n); ++i)
#define all(c) (c).begin(),(c).end() 

bool done[1500][1500][2];
double memo[1500][1500][2];
enum{FIRST = 0, SECOND};
double exp_move(int total, int seen, int turn) {
    double &ret = memo[total][seen][turn];
    if (done[total][seen][turn]) return ret;
    done[total][seen][turn] = true;

    int unseen = total * 2 - seen;
    if (total == 0) return ret = 0;

    ret = 0.;
    
    // open one unseen cell randomly
    if (turn == FIRST) {
        double p1 = 0, p2 = 0;

        // Probability of it's pair is already seen is p1
        if (seen > 0) {
            p1 = (double) seen / (double) unseen;
            ret += p1 * (exp_move(total - 1, seen - 1, FIRST) + 1);
        }

        // Probability of it's pair is not seen yet is p2
        if (unseen > seen) {
            p2 = 1.0 - p1;
            ret += p2 * (exp_move(total, seen + 1, SECOND));
        }
    }
    else {
        double p1 = 0, p2 = 0, p3 = 0;

        // Probability of it's pair is already open is p1
        p1 = (double) 1 / (double) unseen;
        ret += p1 * (exp_move(total - 1, seen - 1, FIRST) + 1);

        // Probability of it's pair is seen but not open is p2
        if (seen > 1) {
            p2 = (double) (seen - 1) / (double) unseen;
            ret += p2 * (exp_move(total - 1, seen - 1, FIRST) + 2);
        }

        // Probability of it's pair is unseen is p3
        if (unseen > seen) {
            p3 = 1.0 - p1 - p2;
            ret += p3 * (exp_move(total, seen + 1, FIRST) + 1);
        }
    }
    return ret;
}

class PerfectMemory {
    public:
    double getExpectation(int N, int M) {
        return exp_move((N * M) / 2, 0, FIRST);
    } 

Counting triangles

I'm going to discuss the analysis of the problem Counting triangles here.

Problem description is very short:

Consider a 2D integer grid with lower left corner at (0, 0) and upper right corner at (X, Y). We are interested in isosceles right triangles which all the 3 corners at the grid node (integer coordinates). Your task is to count the number of those triangles.

There was another problem with the same name: Counting Triangles, in which you have to count all the triangles within a grid having all the three corners in integer coordinate inside the grid. But in this problem you need not to count all of those triangles. You only need to count those triangles which are Isosceles triangle and Right triangle. Now, a triangle can have different shapes and same shaped triangle can have different rotations in the grid. We have to count them all carefully.

For simplicity, lets consider our triangle is OAB, where angle O is right angle, side OA and side OB are equal, so it fulfills both of the conditions above. lets consider the triangle such that, if we rotate OA clockwise in respect of O by 90 degrees then A will be reach to the exactly on the point B. lets consider the coordinate of A, B and O is (x1, y1), (x2, y2) and (x3, y3) respectfully, and also consider O is in the origin, i.e. (0, 0).

Now coordinate of A is (x1, y1) if we rotate it in respect of origin, by rotation matrix of 90 degrees we will get that x2 = y1 and y2 = -x1.

Here is the equation to calculate the coordinate of B form O and A.






You can find the rotation matrix for 90 degrees here.

We know that O (here origin) is an integer coordinate. By the above equation we found that if A is integer coordinate, then B will also be integer coordinate.

So we will brute force for all the integer coordinate for A and calculate the coordinate of B. By all I mean [-X, X] for x coordinate and [-Y, Y] for y coordinate, for other values of x or y, it will definitely occupy a bounding box which is larger than the given 2D grid. So the complexity of this brute force solution is O(X * Y), which is not too big.

In our brute force we will find several triangles OAB, and coordinates of their corner (x3, y3), (x1, y1) and (x2, y2) respectfully. Can you calculate the height and weight of the bounding box of this triangle?

Yes, it's very easy. Height is H = max(y1, y2, y3) - min(y1, y2, y3), and width is W = max(x1, x2, x3) - min(y1, y2, y3).

Now we can place this bounding box in our grid if H ≤ Y and W ≤ X, otherwise it will not fit in our grid and in the same way, our triangle will not fit in the grid. If we can place the bounding box in the grid, we can easily put the lower left corner of the bounding box in (0, 0), so the upper right corner will be (W, H). So, here we found one place where we can place our triangle as well. Can we place the same triangle in another way by shifting our bounding box horizontally or vertically?