SRM 573: Lack of speed

It is another day to use the suicidal strategy , this time having less than 10 minutes to solve div1 250 has really affected me.

Div1 850

You have up to 50 pebbles in points (x,y). In each step you can move a pebble one unit up, down, left or right in the coordinate system. Count the total number of ways in which you can move all the pebbles to the same position in at most m steps.

This sounds like an "optimize the dp" problem. I was actually able to reduce plenty of things.

For example, it is possible to first solve this problem: Given x[] and m, how many ways are there to make all elements of x equal in at most m steps by reducing or increasing each element by one in each step? (The coordinates are almost independent)

I switched to div1 450. When I solved div1 450 I returned to this problem. But it is not so easy. Actually, I can't remember the last div1 850 points problem that was actually easy :P

Div1 450 - The one with skying

You got a bidirectional graph/network of some locations. You want to be able to reach location n-1 starting up from location 0. The locations have heights. It is only possible to move from location i to location j if the height at i is greater than or equal to the height at j. Fear not, because you can change any location's height from p to q with a cost |p - q|. Return the minimum cost required to change the locations so you can move from 0 to n-1.

The first observation was that, if you define your current position as (location, height), defining the current location you are standing at, and the height (possibly changed) it has, then you can move to (location2 , height2), with a cost of abs(height2 - initialAltitude[ location2 ] ) as long as height2 is less than or equal to height.

This approach is correct. It might appear possible to move to the same location twice and change the height twice. But it is possible to prove by contradiction that such sequence of moves will not be the minimum. So we can use Dijkstra to solve this.

The problem is that the heights can be very large. But not really. You just have to notice that it never makes sense to set the height of a mountain to a height that does not already exist in initialAltitude. There are only O(n) such values.

As I write this, the system test ended and I pass!

typedef long long int64;
#define long int64

const char B_INF = 0x7F;
const long INF = 0x7F7F7F7F7F7F7F7FLL;

#define var(q, s) typeof(s) q = (s);

struct SkiResorts
{
    
    long dist[50][50];
    set< pair<long, pair<int,int> > > Q;
    // I do Dijkstra by using a set<> instead of a priority queue, because it
    // is possible to remove larger elements. Makign the memory complexity 
    // O( log( |V| ) ) as opposed to O( log( |E| ) )
    //
    // The downside is that the code is horrible. But you really had to learn STL
    // anyway :P
    void Dijkstra_push(long d, int p, int height)
    {
        if ( dist[p][height] > d ) {
            var(iter, Q.find( make_pair( dist[p][height], make_pair(p, height) ) ) );
            if (iter != Q.end() ) {
                Q.erase(iter);
            }
            dist[p][height] = d;
            Q.insert( make_pair(d, make_pair(p, height) ) );

        }
    }
    
    
    long minCost(vector <string> road, vector <int> altitude)
    {
        memset(dist, B_INF, sizeof(dist));
        int n = road.size();
        for (int i=0; i<n; i++) {
            long dif = abs( altitude[i] - altitude[0] );
            Dijkstra_push( dif, 0, i );
        }
        while ( Q.begin() != Q.end() ) { // O ( log(n*n) * n * n * n * n )
            var(iter, Q.begin());
            long d = iter->first;
            int p = iter->second.first;
            int height = iter->second.second;
            Q.erase(iter);
            
            // You can move from p to i...
            // with some cost...
            for (int i=0; i < n; i++) {
                if (road[p][i] == 'Y') {
                    for (int newheight = 0; newheight < n;  newheight++) {
                        if ( altitude[newheight] <= altitude[height] ) {
                            long newd = abs( altitude[newheight] - altitude[i] ) + d;
                            Dijkstra_push( newd, i, newheight);
                        }
                    }
                }
            }
        }
        long res = INF;
        for (int fh = 0; fh < n; fh++) {
            res = std::min(res,  dist[n-1][fh] );
        }
        return (res >= INF) ? -1 : res;

        
    }
};
#undef long

Div1 250 - The one with teams of three

There is an array of 3*N strengths of team members. Your team has strengths 0, 1 and 2. There are other teams N-1 teams, but you have no idea of which team members go to each team. Return 1 + the maximum number of teams with a strength greater than yours. The strength of a team is equal to the minimum of its strengths + the maximum of its strengths.

With only 5 minutes left and not thinking of anything, I decided to implement the easiest greedy approach, sort the strengths and make teams with the 3 largest strengths, second 3 largest strengths and so on.

This turned out to fail the last example case.

I had 3 minutes left, when I finally thought of the solution:

After you sort the strengts, you have a maximum strength, if you find the minimum possible strength such that minimum + maximum > your strength, then this is a good team to create. Repeat until all teams are created or there are no good teams anymore.

int worstRank(vector <int> strength)
{
    int n = strength.size();
    int you = 0;
    int mx = strength[0];
    int mn = strength[0];
    for (int i=1; i<3; i++) {
        mx = std::max(mx, strength[i]);
        mn = std::min(mn, strength[i]);
    }
    you = mx + mn;
    // maximize the number of teams with a better score than you
    sort( strength.begin() + 3, strength.end() );
    int rank = 1;
    
    vector<bool> seen(n , false);
    for (int i = strength.size() - 1; i >= 3 ; i --) {
        if (! seen[i]) {
            for (int j = 3; j < i; j++) {
                if (! seen[j]) {
                    if (strength[i] + strength[j] > you) {
                        int k = j + 1;
                        while( k < i && seen[k]) {
                            k++;
                        }
                        if (k >= i) {
                            return rank;
                        }
                        seen[i] = seen[j] = seen[k] = true;
                        rank ++;
                        break;
                    }
                }
            }
        }
    }
    
    return rank;
    
}

By the time I finished debugging this implementation ,the challenge phase started.

Update: Turns out it was still wrong, replaced n with i in some conditions and it passes.

Comments, etc?

It was an ok match, I wish I solved div1 250, but I am fine with only solving div1 450. Plenty of coders managed to get 450 wrong.