Editorial for TopCoder Open round 3B ToastJumping

I know that this is very late, but I was finally able to understand this problem and the medium.

ToastJumping

Problem statement

You jump between lattice points, starting at `(0,0)`, the length of a jump cannot exceed `sqrt(d)`, what is the minimum number of jumps needed to reach `(x,y)`, there are up to 50 queries of this kind.

Each test case involves a number of queries. Since every argument in the queries can vary, including `d[i]`, we should just treat each query as a unique case independently. This approach has the consequence that the time limit of 2 seconds is effectively divided by 50. We should make sure not to take more than 40 milliseconds in a single query.

Points reachable in a single jump

Let us move on assuming a single query: Minimum number of jumps from `(0,0)` to `(x,y)`, if the length of the jumps is at most `sqrt(d)`.

The set of points reachable using at most one jump is interesting. For small values of `d`, it is a bit trivial, so let us try `d=9`, thus `sqrt(d) = 3`. The distance must be at least 3, the reachable points are all those lattice points inside a circle of radius 3:

Points reachable in two jumps

It might take a while to finally notice how this set of points looks like. For each of the points reachable in one jump, find the points that can be reached in one jump starting at that point. This means that there are other circles.

The property that will allow us to solve the problem lies hidden in the above image but it is not too easy to notice it without a different perspective.

Polygon of reachable points

The points reachable in a single jump are those inside a circle, but since they are all lattice points, they do not really make a circle shape. The set of reachable points is merely a convex polygon:

The lattice points that coincide with this polygon are important. Because those extreme moves are possible in one step, we can also assume the other moves inside the convex polygon they generate are possible too. Let us draw those moves as vectors:

When we try the points reachable in two jumps, something interesting happens:

The polygon of points reachable in two jumps is actually a scaled version of the original polygon. For each coordinate `(x,y)` of perimeter of the original polygon, the new polygon will have a point `(2x,2y)`.

Generalizing

This property is true for any value of `k` and for any value of `d`, if the points of the polygon that contains points reachable in 1 jump are `(x_i,y_i)`, the points of the polygon that contains points reachable in `k` jumps will be: `(k * x_i, k * y_i)`.

For a demonstration, start by saying that point `(x_i,y_i)` is reachable in one jump. If we repeat the same jump `k` times, then `(k * x_i, k* y_i)` is also reachable in `k` jumps. The space of reachable points is convex, so we can assume that all points inside the convex hull of points `(k * x_i, k * y_i)` will be reachable in `k` jumps. This shows that the points inside the polygon are reachable. We also need to show that the points outside the polygon aren't reachable. Let us use a less formal approach for this: The points in the perimeter of the polygon are the the reachable points that are the furthest away from the origin, in order to move the furthest distance from the origin in a direction, it is most efficient to use that same direction in each jump.

Solution

The solution is then to find the smallest `k` such that the convex hull `(k * x_i, k * y_i)` contains point `(x,y)`. Implementing the solution is another story.

One quadrant

The polygon will be symmetric in each quadraint, so we can just assume that `(x,y)` belongs to the first quadraint `(x,y >= 0)`, if that wasn't the case, we can just use their absolute values thanks to symmetry. We will need to care only about a quarter of the polygon. For `sqrt(d)=4`, `k<=5`:

We only need to generate the points `(x_i, y_i)` of the first polygon. In order to do that, we can try, for each `px`, the maximum y such that `(px,py)` is reachable in one jump. We need to repeat for each value `px` from 0 to `sqrt(d)`. In order to find the value `py`, we can just assume it has to be less than or equal to the value for the previous `px` (As it is the first quadraint, the slopes in the polygon are decreasing). This ensures we only try each candidate `py` from `sqrt(d)` to 0 exactly once. Thus finding the points `(px,py)` will take `O(sqrt(d))`.

After generating those points, they will not necessarily be a convex polygon. They will look like this:

This polygon isn't convex. This can be solved by taking the Convex Hull of all the points `(px,py)` we find. Since we will already find each point in clockwise order, we do not need to sort the points, so it is possible to do the Graham Scan in `O(sqrt(d))` time.

Minimum k

After we find the points `(px,py)` of the polygon of points reachable in one jump, we still need to find the minimum `k`. Unfortunately, an approach such as using a binary search for `k` may not be efficient enough.

What we can do is take each segment `(k*px_i, k*py_i), (k*px_(i+1), k*py_(i+1))` as a constraint for the point. The point must lie inside the polygon, which means that the point should be below the line formed by the segment. For simplicity, we will rename the points of the segment `(x_0,y_0), (x_1,y_1)`.

From the line equation we have:

`y <= ky_0 - (x - kx_0) * (ky_0 - ky_1) / (kx_1 - kx_0)`
`y <= ky_0 - (x - kx_0) * (y_0 - y_1) / (x_1 - x_0)`

Let `D = (y_0 - y_1) / (x_1 - x_0)`:

`y <= ky_0 - (x - kx_0) * D`
`y <= k * (y_0 + x_0 * D) - Dx`
`k >= (y + Dx) / (y_0 + Dx_0)`
...
`k >= ( x * (y_0 - y_1) + y * (x_1 - x_0) ) / ( x_1 * (y_0 - y_1) + y_1 * (x_1 - x_0) )`

Since `k` must be an integer, the minimum `k` greater than or equal to that expression is the ceiling function of that expression.

Each segment determines a lower bound `k`, `k` must be at least that value. The maximum of those lower bounds is the minimum valid `k`. There are `O(sqrt(d))` segments thus the overall algorithm is still `O(sqrt(d))`.

Code

public long area2(long x1, long y1, long x2, long y2, long x3, long y3) {
    // Returns 2 * area of the triangle using cross product.
    // If the result is negative, the points are in anti-clockwise order.
    return (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1);
}

long px[], py[];
int makePolygon(long d)
{
    // Returns the convex hull of the points in quadraint  that are
    // reachable in one jump.
    final int MAX_SQD = 31623;
    int sz = 0;
    px = new long[MAX_SQD+1];
    py = new long[MAX_SQD+1];
    long y = MAX_SQD;
    for (long x=0; ; x++){
        //decrease y until it is inside the circle / is 0:
        while(y > 0 && x*x + y*y > d) {
            y--;
        }
        if (x*x + y*y > d) {
            // x is outside the circle:
            break;
        }
        //Direction of the segments in the polygon should be clockwise:
        // If the new point makes an anti-clockwise direction with the previous
        // point (aread2 > 0), then we need to remove the previous point to
        // keep the polygon convex and so and so for each of the previous points.
        // We can also remove the previous point if they are colinear
        // (area2 == 0), but it is  not necessary for the solution.
        while(sz >= 2 && area2(px[sz-2], py[sz-2], px[sz-1], py[sz-1], x, y) >= 0) {
            // (If the triangle area is 0, the points are colinear)
            sz--; //remove last point
        }
        // [Basically a simplified version of Graham's scan, we already find the
        // points in clockwise order.]
        
        //Add the point:
        px[sz] = x; py[sz] = y; sz++;
    }
    // Make sure to close the polygon...
    if (py[sz-1] != 0) {
        px[sz] = px[sz-1];
        py[sz] = 0;
        sz++;
    }

    return sz;
}

// Solve for each x[i],y[i],d[i]:
public long minJumpsSingle(long x, long y, long d){
    
    x = Math.abs(x);
    y = Math.abs(y);

    int sz = makePolygon(d);
    
    long k = 0;
    for (int i=0; i<sz-1; i++) {
        long dy = py[i] - py[i+1], dx = px[i+1] - px[i];
        long p = x * dy + y * dx;
        long q = px[i] * dy + py[i] * dx;
        // ceil(p/q) is the minimum k such that the point (x,y) will
        // be below line that visits points:
        //    (k*px[i], k*py[i]) ,  (k*px[i+1], k*py[i+1])
        k = Math.max(k, (p + q - 1) / q); // Do ceil(p/q) without floats.
    }

    return k;
}

Read More

More about c++11 - tuples, tie and make_tuple

Remember that last post about new C++ features enabled in TopCoder's servers? These new features (and far more) are also available in Codeforces if you choose GNU c++0x 4 as language (instead of plain GNU c++) and in those contests in which you can compile locally by just using a recent g++ version with the -std=c++0x modifier.

But there is more about the improvements in C++. Have I ever told you about how much I like std::pair? Let me introduce pair's younger brother, std::tuple:

Why and how were tuples added?

One flaw about std::pair was how it stores only two values. Which made it of limited use. There were plenty of times during contests where I had to use nested pairs. Ugly code like queue<pair<int, pair<int,int> > >. The optimal would be to have something that behaves like std::pair, but allows more than two values. A solution like a std::triple would have been a poor solution though, because it would still be limited. But of course, templates with variable argument number would be crazy, right man?

Enter variadic templates, a c++11 killer feature, in my opinion. Templates with variable number of arguments. They allow these tuples and plenty of other things through recursion. It is amazing the sort of things c++ will be able to do at compile time with these. Imagine a strongly typed printf-like function, for example. The good news is that these templates work in TopCoder's ultra old g++ 4.4, and CodeForces' compiler is even more recent. So they are fair game. While C++, the language, adds variadic templates, the STL, the standard template library, is the one responsible of adding tuples.

Let us get to use them

Just add the include: #include <tuple>

Now we basically use std::tuple the same way we used std::pair in the past, except that we can now use more than two arguments. Let us start with an easy one, imagine that you are running a BFS (Breadth-first-search) on a graph that is described by three dimensions, so imagine that it is a 3D grid with x, y and z. (So typical).

queue<tuple<int,int,int> > Q;
bool visited[X][Y][Z];
memset(visited, 0, sizeof(visited));

visited[0][0][0] = true;
Q.push( make_tuple(0,0,0) );
while (! Q.empty()) {
    tuple<int,int,int> node = Q.front(); Q.pop();
    int x = get<0>(node), y = get<1>(node), z = get<2>(node);
    //... etc
    // augment edges from node (x,y,z)?
}

The first bad news is that things like get<index> are needed to access the tuples. They are a bit verbose for my taste. Also note that although they use integers as a matter of indexing, they have to be constants. (Although if you really need variable indexes, you probably need a vector and not a tuple). However, there was possibly no choice in this case, because in order to implement variadic templates, you need some recursion, which means that indexing is likely needed...

But let us go on. Although the get>0> seems heavy, compare with the alternatives. Coding a whole struct? Using a nested pair like I did in one of the first paragraphs? So verbosity could be worse.

The reality is that tuples (or pairs) are not meant to be a replacement of structs or classes, but just something that will help you in some peculiar cases. Like in the post about std::pair, let us deal with a comparison problem: John wants to pick between two strings. He prefers strings that have a larger number of even letters (b,d,f,...). If two strings have the same number of even letters, he prefers the one with a smaller length, if two strings have the same number of even letters and the same length, he prefers the lexicographically smallest one. As simple as:

int even(const string & x)
{
    // count the number of even characters
    int c = 0;
    for (int i=0; i<x.size(); i++) {
        c += ( x[i] % 2 == 0);
    }
    return c;
}

// Given a and b, picks the string that John likes the most:
string johnLikesString(string a, string b)
{
    auto q = std::min( make_tuple(-even(a), a.length(), a), 
                       make_tuple(-even(b), b.length(), b) );
    
    return get<2>(q);
}

Like with std::pair, tuples can be compared using the common relational operators (They implement lexicographical comparison for the values in the order in which they are in the tuple, so element 0 is compared first, if both are equal, element 1 is compared and so and so). Which means that we can use std::min() to pick the smaller of two tuples. Since we wanted the string with the larger number of even characters to be picked, we call -even(...) instead of just even(). At the end, the tuple that is picked by std::min will contain John's preferred string as element #2.

Thanks to relational operators like `<` , `>` , `<=` , `>=`, being implemented automatically for our tuples, we can sort tuples using std::sort. We can also use tuples in std::set, or as keys in std::map.

Also note the cameo by the auto keyword. A great feature. In this case, we don't even need to know the type of the q variable in order to use it. After some inspection, we can see that its type is: tuple<int,int,string>.

std::tie

std::tie is an interesting thing, it does something similar to std::make_tuple, but it uses "lvalue references" instead of creating copies of the values. For simple types, like ints it is not important. Big deal, you are creating a copy of number 5 in memory. But what if you want to compare data structures that could be sort of big? Like in the previous example, what if the strings could be 10000000 characters long? Creating new copies of the strings could be too expensive, so expensive that you reach a memory limit in a problem. But it is not only memory, creating copies of objects takes time.

string johnLikesString(string a, string b) //using by value-arguments sorts of makes
                                           // the following optimization a bit worthless,
                                           // I know.
{
    // tie uses references, but we can't use a reference to a temporary
    // object. So we couldn't use a.length() directly inside of std::tie
  
    int aeven = -even(a), alen = a.length();
    int beven = -even(b), blen = b.length();
    
    // Comparing without creating a copy of the strings:
    if (std::tie(aeven,alen, a) < std::tie(beven, blen, b) ) {
        return a;
    } else {
        return b;
    }
}

Pitfalls and a bonus

Nothing is perfect, specially not c++, not even c++11. Actually, c++11 follows the long tradition that coding in c++ is a lot like operating riding a rocket. A rocket is a fast method of transportation and it is the product of plenty of work and research. But god, if you ride it, it will explode in your face eventually.

The usual std::pair issues stand, although they seem to behave a bit better. But for example, the following line of code will make your compiler throw hundreds of syntax errors at you:

tuple<int,int,string> a = make_tuple(4,5,"ssss");

Well, of course, the issue is that "sss" is a const char*, did you expect the tuple to know that it can cast const char* to std::string? hahaha. And since the error occurs in the third step of the tuple recursion, your compiler will be very confused. There are ways to fix this.

// make the typeo f the argument explicit:
tuple<int,int,string> a = make_tuple(4,5, string("sss") );

// use make_tuple with explicit types:
tuple<int,int,string> a = make_tuple<int,int,string>(4,5, "sss" );

// use make_tuple with explicit types and abuse auto:
auto a = make_tuple<int,int,string>(4,5, "sss" );

// Also abuse the new { } initializer:
auto a = tuple<int,int,string>{4,5, "sss" };        

// Now that I think about it, the whole thing was very silly:
tuple<int,int,string> a(4,5,"sss");  

But don't be sad. Here is an eastern egg for you. Swapping the values of two variables, python style:

int x = 5, y = 7;
//swap x and y:
tie(x,y) = make_tuple(y,x);

// All possible because tie uses references and make_tuple creates copies

int z = 6;
//cycle x,y,z = (y,z,x)
tie(x,y,z) = make_tuple(y,z,x);


//Greatest common divisor, the way Euclid intended:
int gcd(int a, int b)
{
    while (b != 0) {
        tie(a,b) = make_tuple(b , a%b);
    }
    return a;
}

Read More

Today's TopCoder Test SRM

So I wanted to take this SRM seriously as it would be good practice. It didn't help that I remembered to have solved two of these problems before. But there we go.

I wanted really hard to try the new c++ features, but there wasn't that much of a chance to do it, I still managed to pull some tricks.

RPSTournament

Problem statement

I didn't remember this problem. I likely didn't see it before. This old problem had a very confusing problem statement (So a competitor defeats people with both larger and smaller seeds within range? But then what decides which of the two competitors wins? I gave up.

WebsiteRank

Problem statement

I remembered solving this problem before, but I of course don't have such a precise memory to remember the solution. I did remember that after SRM 357, there were tons of discussion about how trivial Floyd-Warshall passed (There can be around 800 website names.)

I actually had difficulty with the problem because I initially read the statement wrongly. The statement actually tells you to ignore points from pages that link to a site, if the site directly or indirectly links to them. I initially understood it as making the website ignore only the points "that come from it".

Once you read the problem correctly. You should be able to use Floyd-Warshall to quickly find which sites link directly or indirectly to each website. Once you ignore links between sites that do this - You are basically removing cycles from the graph. The graph becomes a directed acyclic graph. You could top-sort it, but it is not needed to. The total number of points each website receives is equal to the total number of paths that finish in the website (which is easy to calculate, even with a Floyd variation, because the graph is acyclic).

If the 800 website names bother you, just notice that there are only at most 51 relevant website names. (Websites that are the query's website or websites that are linked by other websites), so you can ignore the other websites and just consider them as extra initial points for each website. So in addition to counting the number of paths, you multiply the number of paths between each website i to the query website by the number of initial points of i.

// Using long (instead of long long) without a define!
long countVotes(vector <string> votes, string website)
{
    //maximum number of website names is around 50/3 * 50 ~=  833
    int n = votes.size(), t = 0;
    map<string,int> websiteId;
    vector<vector<string>> data;
    
    // Convert the votes array of strings to a data[][] 2d array of a
    // vector of strings. Note the auto keyword:
    for (auto q = votes.begin(); q!=votes.end(); q++) {
        istringstream st(*q);
        string x;
        // Look at this!:, pushing an empty vector:
        data.push_back( {} );
        auto & v =  *data.rbegin();
        while (st >> x) {
            v.push_back(x);
        }
        if (websiteId.count(v[0]) == 0) {
            websiteId[v[0]] = t++;
        }
    }
    if (websiteId.count(website) == 0) {
        websiteId[website] = t++;
    }
    vector<long> initialVotes(t, 1);

    int adj[t][t];   //Adjacency matrix
    int reach[t][t]; //Direct or indirect adjacency matrix (After Floyd-Warshall)
    long ways[t][t]; //Number of paths between each pair of nodes)
    memset(adj, 0, sizeof(adj));
    memset(reach, 0, sizeof(reach));
    memset(ways, 0, sizeof(ways));
    // First, setup the adjacency matrix: 
    for (int i=0; i<n; i++) {
        for (int j=1; j<data[i].size(); j++) {
            if (websiteId.count( data[i][j] ) == 0) {
                initialVotes[i]++;
            } else {
                int u = websiteId[ data[i][j] ], v = websiteId[ data[i][0] ];
                reach[u][v] = 1;
                adj[u][v] = 1;
            }
        }
    }
    // Find what nodes can be reached indirectly:
    for (int k=0; k<t; k++) {
        for (int i=0; i<t; i++) {        
            for (int j=0; j<t; j++) {        
                reach[i][j] |= (reach[i][k] & reach[k][j]);
            }
        }
    }
    // Now count the number of paths between each pair of nodes:
    for (int i=0; i<t; i++) {        
        for (int j=0; j<t; j++) {
            if (adj[i][j] && ! reach[j][i]) {
                ways[i][j] = 1;
            }
        }
    }

    for (int k=0; k<t; k++) {
        for (int i=0; i<t; i++) {        
            for (int j=0; j<t; j++) {
                ways[i][j] += ways[i][k]*ways[k][j];
            }
        }
    }

    // Done and multiply:
    long c = initialVotes[ websiteId[website] ];
    for (int i=0; i<t; i++) {
        c += initialVotes[i] * ways[i][websiteId[website]];
    }
    return c;
}

It seems I took longer to solve this problem than back in 2007, but this time I got the problem correct. I failed system tests in 2007.

PalindromeMaker

Link to statement

I still used my new strategy of waiting till there are less than 10 minutes before the end of the match before opening the easy problem.

This problem gives you a string of upper case letters. Return a palindrome permutation of those letters. If there are multiple solutions, return the lexicographically first one. If there are no solutions, return "".

Forget about the lexicographical condition. If we were to take any string like AABB and turn it into a palindrome, we would usually need each letter to appear an even number of times, so you can do ABBA or BAAB. There is one exception, when the length of the string is odd, then exactly one of the letters must appear an odd number of times. This letter should be used in the middle position.

Let us now deal with the lexicographically-first decision. Try each of the pairs of repeated letters. It is always better to place the lexicographically-smallest letter of those available in the smallest available position. So, for each letter from A to Z, in that order, pick every two of that letter, and push one to the left end and another to the right end. Remember the letters that appear an odd number of times. Then we can put the left, right (and maybe middle) ends together.

string make(string baseString)
{
    string left, right, odd;
    for (char ch='A'; ch <= 'Z'; ch++) {
        // Count the number of times letter ch appears:
        int c = count(baseString.begin(), baseString.end(), ch );
        // If it is odd, save it as the odd letter:
        if ( c % 2 == 1) {
            // Don't allow more than one odd letter:
            if (odd != "") {
                return "";
            }
            odd = ch;
        }
        // Half goes to the left end, other half to the right end.
        string rep = string( c / 2, ch );
        left += rep; right = rep + right;
    }
    // An odd letter must exist if and only if the string has odd length:
    if ( (baseString.size() % 2 == 1) == (odd != "") ) {
        return left + odd + right;
    } else { 
        return "";
    }
}

The end

It was an ok match, old problems feel very easy in comparison to current contests. Six years! That is depressing...

Read More

TopCoder Test SRM, new c++ features

Have you heard, there will be a Test SRM in just a couple of hours. The intention of the SRM is to test new* compiler versions. (* Relatively speaking). But if you want to practice, a test SRM is a good chance, because the problems will be reused but a surprise, and the time limit will simulate a real contest. It also introduces Python as an usable language. Unfortunately for python coders though, Arena plugins shall take a while to get updated to work with python.

Speaking of the new language versions. The new version for the g++ compiler is 4.4. It is a bit old, but at least it can be found in most Linux repositories (unlike the ultra old version that was in use before). The admins say that even newer versions will be used later.

The upgrade will remove some deprecated features. Most notably, the cool min/max operators like <?, >?, <?= and >?=.

Most importantly, there are new features! Specially because g++ is called with -std=c++0x. In other words, some features planned for c++0x will be available in TopCoder SRMs in the future and in today's match. Of course, not all of them. g++ 4.4 only has some of them implemented. But I found a list: http://gcc.gnu.org/gcc-4.4/cxx0x_status.html

There are a couple of things that C++ coders should know.

auto keyword

While it is in terrible taste to use the word auto instead of var, the new auto keyword will prove to be very useful when dealing with the STL.

void doSomething( vector< pair<string, pair<int,int> > > toocomplex ) 
{
    auto copy = toocomplex; //makes a copy of toocomplex.
    //blah blah blah...
    
    

read more

Initializer lists

This is now possible:

// a quick array:
int A[] = {1,2,3,4,5,6};
cout << A[3]<<endl;

// a vector<int>:
vector<int> B = {5,6,7,89};
cout << B[2] << endl;

// Or how about a set?
set<int> B = {1,2,3,7,8,9};
// Is 3 in the set? (will show 1)
cout << B.count(3) << endl;
// Is 4 in the set? (will show 0)
cout << B.count(3) << endl;

// Yep, you can use any expression, not just constants:
int x = 5, y = 7, z = 8;
set<int> b = {x,y,z};

// Forget about make_pair:
pair<int,int> v = {2,3};

Nuff said.

long

Have I ever complained about having to type long long instead of just long? Yes, yes I did.. Fear not, because long is 64 bits now, without having to type long long.

More

Plenty of changes for templates, look at the gcc 4.4 table linked above for more. Most of these template features would be useful if you are coding data structure libraries. static assertions could be nice to avoid some pit falls. Also, vector<int, pair<int,int>> is valid syntax. That double closing > has caused plenty of problems in the past to people that are just starting getting hold of the STL.

Read More