Spoj Anttt – CPP solution

Link: http://www.spoj.com/problems/ANTTT/
Idea:
Create a graph of the intersecting lines and use dfs/bfs to find whether a path exists from one node to another. For the intersection part there are two possible ways I know:
1) write out equations for the lines and find the formula for the Y (or X) cordinate and then check whether the point is part of the segment. This is however harder and slower to right with some cases to consider. For example the line x=0.
2) just use standard vector operations. If you are given the lines A-B and C-D. Chech whether A is on one side of C-D and if B is on the other. Then check whether C and D are on opposite sides of A-B. In this case they collide. If we also consider the case where one of the points can lie on the segments, then we can to also consider the case: 1 1 3 3, 4 4 5 5. I.e. when they are parallel. Then you have to also check for the bounds.

When I was at high school, I used to write the first technique and it worked out well. I learned about the second while I was doing USACO.

#include <cstdio>
#include <iostream>
using namespace std;

typedef long long ll;

struct Point {
    ll x,y;
    Point() {};
    Point(ll _x, ll _y) : x(_x), y(_y) {};
};

struct Line {
    Point from,to;
    Line() {};
    Line(const Point & _from, const Point & _to) : from(_from), to(_to) {};
};

Point operator -(const Point & A, const Point & B) {
    return Point(A.x-B.x, A.y-B.y);
}

ll cross(const Point & A, const Point & B) {
    return A.x*B.y - A.y*B.x;
}

bool onOneSide(const Line & A, const Line & B) {
    ll v1 = cross(B.from - A.from, A.to - B.from);
    ll v2 = cross(B.to - A.from, A.to - B.to);

    if(v1 == 0LL && v2 == 0LL) {
        if (A.to.x < B.from.x) return false;
        if (A.from.x > B.to.x) return false;
    }
    return (v1 <= 0LL && v2 >=0LL) || (v1 >=0LL && v2 <= 0LL);
}

bool intersect(const Line & A, const Line & B) {
    return onOneSide(A,B) && onOneSide(B,A);
}

int nb[1001][1001];
int nbSz[1001];
int used[1001];
Line lines[1001];
int destination;
int q;

void dfs(int u) {
    if (used[u]==q) return;
    if (destination==-1) return;
    if (u == destination) destination = -1;
    used[u] = q;
    for (int i = 0; i < nbSz[u]; ++i) {
        dfs(nb[u][i]);
    }
}

void cl(int n) {
    for (int i = 1; i<=n; ++i) nbSz[i]=0, used[i]=0;
}

void addNb(int A, int B) {
    nb[A][nbSz[A]++] = B;
    nb[B][nbSz[B]++] = A;
}

int main() {
    int t;
    scanf("%d",&t);
    while (t--) {
        int n,m;
        scanf("%d%d",&n,&m);
        for (int i = 0; i < n; ++i) {
            ll x1,x2,y1,y2;
            scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
            if (x1 > x2) {
                swap(x1,x2);
                swap(y1,y2);
            }
            lines[i+1] = Line(Point(x1,y1),Point(x2,y2));
        }
        for (int i = 1; i<=n; ++i) {
            for (int j = i+1; j<=n; ++j) {
                if (intersect(lines[i], lines[j])) {
                        addNb(i,j);
                }
            }
        }
        for (q = 1; q <= m; ++q) {
            int a,b;
            scanf("%d%d",&a,&b);
            destination = b;
            dfs(a);
            if (destination == -1) {
                printf("YESn");
            } else {
                printf("NOn");
            }
        }
        cl(n);
    }
    return 0;
}

Spoj TFOSS – CPP solution

Problem: http://www.spoj.com/problems/TFOSS/
Given N points, find the longest distance between any two points.
There are two important things to realize when solving the problem:
1) The pairs of such points the distance of which is the maximum are parts of the convex hull. Therefore, it is important to find the convex hull.
2) The size of convex hull is O(N). => We cannot still find the maximum distance naively. There are fast algorithms to find the longest dinstace in a convex polygon (diameter of a convex polygon) – in fact, there are O(N) such algorithms. However, they might be difficult to undestand or hard to implement. O(N logN) is just fast enough.

The idea is to iterate over all points of the convex hull and for each point find the other point for which we maximum distance in O(logN) time. We can use binary search.
Suppose that we are looking at the start of the convex polygon and we calculate the distances to every other vertex of the polygon. It would look something like:
1 6 9 12 55 99 221 88 66 45 33
The 221 would be the maximum. In general, you should realize that we have an ascending sequence and then a descending sequence. You can do binary search to find the peek.

Code:

#include <cstdio>
#include <algorithm>
#include <climits>
using namespace std;

typedef long long ll;

struct Point
{
    ll first;
    ll second;
    Point() {};
    Point (ll x, ll y) : first(x), second(y) {};
};


Point points[100002];
Point hull[200005];
size_t hullSize;

ll cross(const Point & A, const Point & B)
{
    return A.first * B.second - A.second*B.first;
}

Point operator - (const Point & A, const Point & B)
{
    return Point(A.first - B.first, A.second - B.second);
}

Point operator + (const Point & A, const Point & B)
{
    return Point(A.first + B.first, A.second + B.second);
}

ll dist(const Point & A, const Point & B)
{
    return (A.first-B.first)*(A.first-B.first) + (A.second-B.second)*(A.second-B.second);
}

bool comp(const Point & A, const Point & B)
{
    ll v1 = cross(A-points[0],B-points[0]);
    if (v1 > 0LL)
    {
        return true;
    }
    else if (v1 < 0LL)
    {
        return false;
    }
    else
    {
        return dist(A,points[0]) < dist(B,points[0]);
    }
}

ll hullSearch(int idx, int to)
{
    int l = idx+1;
    int r = to;
    ll s = 0LL;
    while (l <= r)
    {
        int mid = (l+r)>>1;
        ll l1 = dist(hull[mid-1], hull[idx]);
        ll l2 = dist(hull[mid], hull[idx]);
        ll l3 = dist(hull[mid+1], hull[idx]);
        s = max(l1, max(l2,l3));
        if (l1 < l2 && l2 > l3)
        {
            break;
        }
        else if (l1 <= l2 && l2 <= l3)
        {
            l = mid+1;
        }
        else
        {
            r = mid-1;
        }
    }
    return s;
}

int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n;
        scanf("%d", &n);
        int idx = 0;
        for (int i = 0; i < n; ++i)
        {
            ll a,b;
            scanf("%lld%lld",&a,&b);
            points[i] = Point(a,b);
            if (b < points[0].second)
            {
                idx = i;
            }
            else if (b == points[0].second && a < points[0].first)
            {
                idx=i;
            }
        }
        swap(points[0], points[idx]);
        sort(points+1, points+n, comp);
        for (int i = 0; i < n; ++i)
        {
            while (hullSize > 1 && cross(hull[hullSize-1]-hull[hullSize-2], points[i]-hull[hullSize-2]) <= 0LL)
            {
                hullSize -= 1;
            }
            hull[hullSize++] = points[i];
        }
        for (int i = 0; i < hullSize; ++i)
        {
            hull[hullSize+i] = hull[i];
        }
        ll ans = 0LL;
        if (n == 1) hullSize=0;
        for (int i = 0; i < hullSize; ++i)
        {
            ll tmp = hullSearch(i, i+hullSize);
            if ( tmp > ans) ans = tmp;
        }
        printf("%lldn", ans);
        hullSize=0;
    }
    return 0;
}

Spoj FACVSPOW – Cpp solution

Problem: http://www.spoj.com/problems/FACVSPOW/
Shortly, you are given a number A as input and you want to find such an N for which
N! > A^N
You must be able to calculate N! fast enough since O(N) would be too slow.
We can use Stirling’s approximation for which:
N! ~ sqrt(2*PI*N) * (N/e)^N
=> we are searching for such an N for which
sqrt(2*PI*N) * (N/e)^N > A^N
or
N * (2*PI*N)^(1/2N) >= A*e
We can do binary search on N and calculate the answer in log(N).

#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;

int calc(int a) {
    int l = 0, r = 10000000000;
    int n=0;
    static double E = exp(1.0);
    static double PI = 3.14159265358979323846;
    double want = E * (double)a;
    while (l <= r) {

        int m = (l+r)/2;
        double val = pow(PI*2.0* ((double)m), 1.0 / (2.0 * (double)m))*(double)m;
        if (val <= want) {
            l = m+1;
        } else {
            r = m-1;
            n = m;
        }

    }

    return n;
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int a;
        scanf("%d", &a);
        printf("%dn",calc(a));
    }
    return 0;
}

Spoj MOHIB1 – CPP solution

Problem: http://www.spoj.com/problems/MOHIB1/

Solution:
Let’s say that we want to answer for N. We first check the first ball, which will collide with balls 2,3,..N.
=> In the box we will then have the sum of the numbers from 2…N. Then we pick ball number 2 and it will collide with balls 3…N. => In the box we will then add sum(3…N) * 2.

=> answer for N is
answer(N) = sum (2…N) * 1 + sum(3…N) * 2 + sum(4..N) * 3 + … + sum(N…N)*(N-1)

We have to calculate this in a fast way. We can use dynamic programming for the sums and for the answers as well.
Precomputation should be done in O(N) time where N < = 10^4. Which will give us a O(1) time to answer a query (test). Let us say that we have the answer for all queries till K and we want to check for K+1. this means that the answer would be: sum (2...K) + (K+1) + (sum(3...K) + (K+1)) * 2 + (sum(4...K) + K+1) * 3 + ... + (sum(K...K) + K + 1) * (K-1) + sum(K+1 ... K+1) * K which is the same as answer(K+1) = answer(K) + sum(1...K) * (K+1). We have for sure precomputed already answer(K) and sum (1...K). => transition is very easy.

Code:

#include <cstdio>
#include <iostream>
using namespace std;

typedef unsigned long long ull;

ull dp[10001];
ull ans[10001];

void precompute() {
    for (ull i = 1; i<= 10000ULL; ++i) {
        dp[i] = dp[i-1]+i;
        if (i >= 2ULL) {
            ans[i] = ans[i-1] + dp[i-1]*i;
        }
    }
}

ull comp(int n) {
    return ans[n];
}

int main() {
    precompute();
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        ull ans = comp(n);
        printf("%llun", ans);
    }
    return 0;
}

Spoj GEOPROB – Cpp solution

The idea is first express A as a function of B, C and D. It’s quite easy to see that the answer would be:
A = 2*C – B – D.
Since the numbers can be quite big, you will have to write your own methods for addition and subtraction of big numbers (200 digits).

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

vector<int>  b(201),c(201),d(201);

void print(const vector<int> & V) {
    for (int i = 0; i < V.size(); ++i) {
        printf("%d", V[i]);
    }
    printf("n");
}

void clean(vector<int> & V) {
    while(V[0] == 0) V.erase(V.begin());
}

vector<int> operator +(const vector<int> & A, const vector<int> & B) {
    vector<int> Arev = A, Brev = B;
    reverse(Arev.begin(), Arev.end());
    reverse(Brev.begin(), Brev.end());
    vector<int> res;
    int sz = (max(Arev.size(), Brev.size()));
    res.resize(sz+1);

    for (int i = 0; i < sz; ++i) {
        int f1=0,f2=0,f3 = 0;
        if (Arev.size() > i) {
            f1 = Arev[i];
        }
        if (Brev.size() > i) {
            f2 = Brev[i];
        }
        f3 = res[i];
        int f4 = f1+f2+f3;
        int dig = f4%10;
        int se = (f4/10)%10;
        res[i] = dig;
        res[i+1] = se;
    }
    reverse(res.begin(), res.end());
    return res;

}

vector<int> operator -(const vector<int> & A, const vector<int> & B) {
    vector<int> Arev = A, Brev = B;
    reverse(Arev.begin(), Arev.end());
    reverse(Brev.begin(), Brev.end());
    vector<int> res;
    int sz = (max(Arev.size(), Brev.size()));
    res.resize(sz);
    for (int i = 0; i < sz; ++i) {
        int f1 = 0, f2 = 0;
        if (Arev.size() > i) {
            f1 = Arev[i];
        }
        if (Brev.size() > i) {
            f2 = Brev[i];
        }
        f2 += res[i];
        res[i] = 0;
        int f3 = (f1-f2);
        if (f3 < 0) {
            f3 += 10;
            res[i] = f3%10;
            res[i+1] = 1;
        } else {
            res[i] = f3;
        }
    }
    reverse(res.begin(), res.end());
    return res;
}

void readS(vector<int> * buf) {
    buf->clear();
    buf->reserve(201);
    string s;
    cin >> s;
    for (int i = 0; i < s.length(); ++i) {
        buf->push_back(s[i]-'0');
    }
}

void read() {
    readS(&b);
    readS(&c);
    readS(&d);
}

void answer() {
    vector<int> dc = c+c;
    clean(dc);
    dc = dc - b;
    clean(dc);
    dc = dc - d;
    clean(dc);
    print(dc);
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        read();
        answer();
    }
    return 0;
}