SRM 593: Meh

The one with hexagon grid

You are asked to color some hexagons in an hexagon grid using the least number of colors in such a way that no two adjacent hexagons have the same color.

I messed up during the match, first I thought that the maximum number of colors to color it was 4. It turns out it was 3, which I found out too late. Under the assumption it was 4 I wasted some precious minutes. What is really sad is that I actually looked at this page: http://en.wikipedia.org/wiki/Hexagonal_tiling#Uniform_colorings, in the first minute after opening the problem and I still didn't notice.

Once I knew the maximum result was 3, then you have to verify if it is possible to color using 0, 1, or 2 colors.

I made the assumption that this depended only on the degree, which was wrong. If there are no hexagons to color, the result is zero. If the maximum degree (maximum number of must-paint hexagons adjacent to another must-paint hexagon) is 1 or 2, then we can paint them using 2 colors (because they form a collar or a line). My mistake was in assuming that degree = 3 meant that you needed 3 colors. There is a specific case for which this isn't true:

-X-
-XX
-X-

Too bad I didn't find it, I actually tried a few hexagons with degree 3 and convinced myself that the adjacent hexagons would always share an edge. If I didn't make this blunder, I would have just done a bipartite check. If the graph is bipartite, then you can paint using 2 colors. That's the solution.

The one with teams

This one was 450 but I really couldn't break its secret. I was trying a dynamic programming, but it wasn't working at all. Then the match ended.

Challenge phase

I knew that my 250 was slow, but I was also pretty sure it was tricky (I even prepared some cases, because there were no example cases in which the maximum degree was 1, for example). But I didn't have that much luck. The codes were very complicated to read. I did find one solution that wasn't even relying on degrees but on partial degrees. So I challenged it, and was happy, because the 50 pts would fix the slow submission. So I went to see the room summary and boom: My solution was already challenged. Probably if I noticed about my solution getting challenged I wouldn't have risked making that challenge...

Comments?

I liked the 250 until I learned checking for bipartiteness was mandatory. Too messy for the slot. 450 said "difference" when it should have specified absolute value of the difference, this made me waste time coding a wrong solution.

Read More

SRM 592 - sloow

d1 300 - The one with colors

So you have a sequence of balls, each has one of three colors: red, green and blue. You need to place the balls in a row. The order in which to place the balls is given by a string S. When you place a ball, you get points equal to the number of different colors to its right + the number of different colors to its left. Find the maximum possible score.

At first I thought of a dynamic programming solution. It was correct and all, but perhaps I should have waited to think of something better.

Let us name two sides of the row, the left and right side. When we place a new ball, it is best to place it between the two sides. So the score of that step is equal to the number of different colors in the right side + the number of different colors in the left side. The trick is that after adding this ball, we decide whether it belongs the left or the right side. In my dynamic programming solution I simulated both possibilities, but it is not needed. It is always better to add the ball to a side that doesn't already contain its color (This decision will increase the score of following steps by 1, any other decision won't). If both sides contain the color, it doesn't really matter.

int getNumber(string s)
{
    set<char> s1, s2;
    int res = 0;
    for (char ch: s) {
        res += s1.size() + s2.size();
        // if s1 already contains s[i] insert it to s2:
        ( s1.count(ch) ? s2 : s1).insert(ch);
    }
    return res;
}

There are other ways to implement the same logic. For example, in step i, the maximum score you can get is equal to min(2, number of red balls already placed ) + min(2, number of blue balls) + min(2, number of green balls). But the resulting code is actually more complicated.

d1 500: The one with permutations

Given `k` and `n` , count the number of pairs of permutations `(A, B)` of length `n` such that `sum_(i=1)^(i<=n)( max(A_i, B_i) ) >= K`

I spent most of the match trying to come up with a way to divide this problem into workable sub-problems, I sort of knew it would be a dynamic programming solution, but I had no idea how. I was trying and trying to find a way to simplify sub-problems. Oh well.

The rest

Opened div1 hard. I think it will be an approachable one once I get help. Tried to challenge but there was only one suspicious solution to div1 250 in my room and it got challenged before I could think of something.

Read More

SRM 591 Recap and editorial

So, another SRM, another editorial. http://apps.topcoder.com/wiki/display/tc/SRM+591.

This was another bad day. Well, I was trying to solve the div1 500 for most of the match, but it seemed quite tricky. I opened div1 275 with 10 minutes left. I took a while to code it. Without the 10 minutes constraint I would have submitted this problem. I got tired of the lame strategy. I am going to try something else next match, but opening the problems in the normal order.

When writing the editorial, I learned about div1 900. This SRM had very odd choices for problem scores and slots. I think div1 900 was at least as easy if not easier than div1 medium. Actually, I wonder what would have happened if I opened it during the match. It is my style of problem, bitmask dp when filling a board. Well, I guess I would have probably taken more than 75 minutes to solve it...

The other very odd choice for this SRM was the div2 hard. I actually wasted more time trying to come up with a solution to this problem than I spent understanding the div1 hard solution. That is odd. The thing that made it complicated is that I really didn't expect a solution for a division 2 hard to be so hacky. Tricks to save memory in dp belong to div1 medium. I think even the div1 easy would have felt less out of place for the div2 hard slot.

I think that admins should go back to enforcing there to be at least one shared problem between the divisions. Making div2 medium and div1 easy the same problem was a good way to constraint problem setters to stop them from making the divisions too different and also limited the difficulty of div1 250 which is a serious slippery slope without safeguards. Also, there was nothing that made me feel the division 2 and division 1 versions of this contest were part of the same contest. Part of the experience should be to have red coders and greens talk about the same problems after the end of the match, this cannot happen when the divisions are so different. Also, it is quite easier to write explanations for 5 problems instead of 6 :)

----

Regarding the editorial itself, I suspect the explanation for div1 275 really, really sucks.

Read More

SRM 589: Read the statement! (upd)

So another SRM. This time the scores were very special: 250-450-900. It seemed like a good match to use my strategy. At the end though, I didn't take much advantage of it, because of two blunders...

Div1 450: The one with gears

We have gears of three colors, red, green , blue. Initially, some pairs of gears are meshing: If one of the gears in a meshing pair turns in a direction, the other gear must turn in the other direction. No two gears of the same color ever mesh. We want to be able to turn all the gears in such a way that all the (remaining) gears of the same color turn in the same direction. What is the minimum number of gears to remove?

I think using clock-wise and anti-clockwise for the directions is too verbose, so let us call say that some gears are positive and some gears are negative. Now all the gears of the same color must have the same *sign* and two connected (meshed) gears must have different signs.

There are only three colors and two signs, so how about we do brute force for the signs? There will always be two colors with the same sign, otherwise it doesn't matter which sign. So two colors have equal sign, let us say positive, and another color is negative. Between the two positive colors, there should be no connections...

We can actually ignore the negative gears, all their connections are already valid and removing them won't fix anything. So now we only have gears of two colors that should never be connected. This is the independent set in a bipartite graph. So let us just run max flow...

During the match, I took a bit of time because at first I was considering the negative gears, causing a single wrong case (the other example cases were very weak). It was early in the morning, I was just confused...

Div1 900: The one with bits

You want a binary string of N bits (N is up to 300) to be one in which the prefix of length N-M and the suffix of length N-M are equal. You can flip a single bit at cost 1 and you can also flip the first K*M bits at cost 1 (for any positive K). What is the minimum cost?

I think I have some ideas. Unlike most div1 hards, I think I can solve this in a few hours and without help. It is a dynamic programming problem with complications.

Div1 250: The one with palindromes

Turn a string palindrome (again?). This time your only allowed move is to pick two alphabet letters X and Y , and turn all the X letters into Y. Return the minimum number of letter positions you need to change.

I only had 10 minutes, so I rushed to code a solution, which was mostly right. I missed the fact that you want to minimize the number of changed positions (it didn't help that this fact was disguised by some talk about seconds). Not the number of changed letters. I only noticed when there were some seconds left before the end of the challenge phase. I fixed the code some time before the end of intermission.

Anyway... The palindrome requirement means that some pairs of positions must be equal. This means that at the end the letters in that pair of position must be equal. This creates a relationship/connection between pairs of letters. At the end, all letters in a group of letters that are connected (directly or indirectly) must be equal. We have to change each of these letters to the same letter. It is best to pick the letter that appears the maximum number of times. Repeat for each connected component.

int getmin(string S) 
{
    int n = S.length();
    vector<bool> visited(26, false);

    // This DFS finds a list of all letters that are *connected* to letter ch:
    // Returns the maximum number of times one of the connected letters appears
    function<int(char)> dfs = [&](char ch)->int {
        if (!visited[ch - 'a']) {
            int res  = count(S.begin(), S.end(), ch);
            visited[ch - 'a'] = true;
            // Two letters are connected if the palindrome rule states that
            // two positions that contain the letters must be equal:
            for (int j=0; j<n; j++) {
                if (S[j] == ch) {
                    res = std::max(res, dfs( S[n-j-1] ) );
                }
            }
            return res;
        }
        return 0;
    };

    // For each group of connected letters, find the letter that appears the
    // maximum number of times, subtract it from the total cost:
    int res = S.length();
    for (char ch = 'a'; ch <= 'z'; ch++) {
        res -= dfs(ch);
    }
    
    return res;
    
    
}

Update Maybe that lambda stuff makes the code appear complicated, here is a python version:

def getmin(S):
    n = len(S)
    visited = set()
    
    # This DFS finds a list of all letters that are *connected* to letter ch:
    # Returns the maximum number of times one of the connected letters appears
    def dfs(ch):
        if ch not in visited:
            visited.add(ch)
            res = S.count(ch)
            # Two letters are connected if the palindrome rule states that
            # positions that contain the letters must be equal:
            for i in range(0,n):
                if S[i] == ch:
                    res = max(res, dfs( S[n - i - 1]) )
            return res
        return 0
    
    # for each connected component, subtract the letter with the maximum number
    # of position: Call dfs for each of the letters in string.lowercase :)
    return n - sum( dfs(ch) for ch in string.lowercase )

Outcome / Comments / etc?

So I am back to yellow, I could have gotten much better rating if I paid attention when reading the 250.

What did you think about the match?

Read More

Codeforces #196: slowness

It tends to be difficult for me to find time for Codeforces matches. Today there was finally one in a time/day slot I can try out.

I adapted my TopCoder strategy into Codeforces. I decided not to open problem A until 10 minutes before the contest ends. But I sort of know that problems D and E tend to be too above my level, so I focused on problems C and B.

Problem C: The one with divisor trees

problem statement

A divisor tree is a tree of integer numbers in which all the leaf nodes are prime numbers and every other node is equal to the multiplication of all of its children. Given up to 8 numbers `(a_i <= 10^12)`, return the minimum number of nodes in a divisor tree that contains them all.

My first reaction was to try to think of a dynamic programming idea. Given a sub-set of the numbers, what is the minimum-size tree you can make? But as I was attempting to solve this I eventually noticed a solution that was easier to code and clearly correct.

Other than the numbers `a_i`, you don't need any of the other nodes to be composite. The only exception would be the root, the root of the tree may need to be composite when there is no way to distribute all of the numbers in a single subtree.

This takes us to concluding that each of the numbers `a_i`, will either be a direct child of another `a_j` or of a newly-added root. There are at most `9^8` ways to make this decision, which is not large. You can cut it even more by using backtracking and making sure not to add children to a integer that are not divisors of it, and that the product of all the children divides the parent.

After assigning the parents, we just need to calculate the size of the tree. For this we can use a small dynamic programming. Process the integers in increasing order and find, for each of them, the minimum size of the tree that has it as root. This size depends on the sizes of all the children and the number of remaining prime factors. So we also need something that is able to calculate the prime factors. A memoization does the job well as we only need the number of prime factors for numbers `a_i` and their divisors.

// from library: primesn, number of primes <= 1000000.
//               primes[i] : i-th prime number <= 1000033

// memoizes the number of prime factors for x.
map<long,int> primeFactors;
int countPrimeFactors(long x)
{
    if (primeFactors.find(x) == primeFactors.end()) {
        int res = 0;
        if (x == 1) {
            res = 0;
        } else {
            for (int i=0; i<primesn; i++) {
                if ( primes[i] > x/primes[i]) {
                    break;
                }
                if (x % primes[i] == 0) {
                    //one
                    res = 1 + countPrimeFactors(x / primes[i]);
                    break;
                }
            }
            if (res == 0) {
                res = 1;
            }
        }
        primeFactors[x] = res;
    }
    return primeFactors[x];
}


int n;
const long INF = numeric_limits<long>::max();
long a[8];
int parent[8];
long ta[8];


long best;

void backtrack(int x)
{
    if (x == n) {
        // all right, build the trees
        long tree[n+1]; //tree size
        for (int i=0; i<=n; i++) {
            tree[i] = 0;
            int children = 0; //number of children of a[i]'s root
            for (int j=0; j<i; j++) {
                if ( parent[j] == i ) {
                    children++;
                    tree[i] += tree[j];
                }
            }
            if ( (i != n) && (ta[i] != 1) ) {
                //how many prime factors does ta[i] have?
                int f = countPrimeFactors(ta[i]);
                tree[i] += f;
                children += f;
            }
            if (children > 1) { //we need this because a[i] might be prime.
                tree[i]++;
            }
        }
        best = std::min(best, tree[n]);
    } else {
        // assign a parent to #x, n means the root.
        for (int i=x+1; i < n; i++) {
            if ( ta[i] % a[x] == 0) {
                parent[x] = i;
                ta[i] /= a[x];
                backtrack(x+1);
                ta[i] *= a[x];
            }
        }
        parent[x] = n;
        backtrack(x+1);
    }
}

long solve()
{
    // Call the backtracking
    sort(a, a+n);
    for (int i=0; i<n; i++) {
        ta[i] = a[i];
    }
    best = numeric_limits<long>::max();
    backtrack(0);
    return best;
}

Problem B: The one with the other kind of tree

I opened this problem, seemed difficult but eventually thought of an approach. It took me a while to code it, and when I finished it, there were bugs. 10 minutes before the end of the contest, I switched to A, but it didn't appear that I would be able to solve it in 10 minutes, so I decided to go back to B. Debugged and finishing coding it right as the contest ended. It doesn't really matter though, because it turns out that my idea , while correct, would still time out because of an issue I missed to notice. After I fixed this issue, it works fine.

problem statement

A set of n towns is a tree (n-1 roads and it is connected). m towns are haunted. The origin of the hauntings is a town such that its minimum distance between it and the haunted cities is at most d. Return the number of cities that follow this rule. `(1 <= m <= n <= 100000)`,

Very large constraints, but we got to take advantage of it being a tree.

Since it is a tree, we can pick a root, any vertex works. For each vertex calculate farHaunted, the maximum distance between the vertex and a haunted vertex that is a child or a grand child of it. (In the rooted tree) This is workable in `O(n)` time.

The real challenge is to find the actual maximum distance from a vertex to a haunted one, (possibly outside the subtree). To do this, let me define parentHaunted, the minimum distance between vertex x and a haunted vertex such that the road between x and the haunted vertex visits the parent of x. After this is defined, we can just start on the root and then find parentHaunted for each child and grandchild we find. Using this value we can calculate the real maximum distance between the vertex and a haunted one. parentHaunted depends on the parent's parentHaunted and the data from the siblings, pick the sibling with the worst farHaunted. This is the part that caused my time out bug, it is best to do it in O(degree(x)) time.

int n, m, d;
const int MAX = 100000;
int p[MAX];
bool haunted[MAX];
int a[MAX], b[MAX];

int degree[MAX];
vector<int> g[MAX];

int farHaunted[MAX]; //what is the furthest haunted child of x?

void dfs(int x, int parent)
{
    int & fur = farHaunted[x];
    fur = -1;
    for (int i=0; i<degree[x]; i++) {
        int y = g[x][i];
        if (y != parent) {
            dfs(y, x);
            if (farHaunted[y] != -1) {
                fur = std::max(fur, farHaunted[y] + 1);
            }

        }
    }
    if (haunted[x]) {
        fur = std::max(fur, 0);
    }
}

int reallyFar[MAX];

void dfs2(int x, int parent, int hauntedParent)
{
    //my current position
    reallyFar[x] = std::max(hauntedParent, farHaunted[x]);
   
    pair<int,int> bestChild ={-1,-1};
    pair<int,int> secondBestChild = {-1,-1};
    for (int i=0; i<degree[x]; i++) {
        int y = g[x][i];
        if (y != parent) {
            pair<int,int> p = make_pair(farHaunted[y], y);
            if (p > bestChild) {
                secondBestChild = bestChild;
                bestChild = p;
            } else if (p > secondBestChild) {
                secondBestChild = p;
            }
        }
    }

    
    for (int i=0; i<degree[x]; i++) {
        int y = g[x][i];
        if (y != parent) {
            int furpar = -1;
            if (hauntedParent != -1) {
                furpar = hauntedParent + 1;
            }
            if (haunted[x]) {
                furpar = std::max(furpar, 1);
            }
            int oth = bestChild.first;
            if (y == bestChild.second) {
                oth = secondBestChild.first;
            }
            if (oth != -1) {
                furpar = std::max(furpar, oth + 2);
            }
            dfs2(y, x, furpar);
        }
    }
}

int solve()
{
    fill(haunted, haunted+n, false);
    for (int i=0; i<m; i++) {
        haunted[--p[i]] = true;
    }
    //build the tree
    fill(degree, degree+n, 0);
    for (int i=0; i<n-1; i++) {
        int u = --a[i], v = --b[i];
        
        degree[u]++;
        degree[v]++;
    }
    for (int i=0; i<n; i++) {
        g[i].resize(degree[i]);
        degree[i] = 0;
    }
    for (int i=0; i<n-1; i++) {
        int u = a[i], v = b[i];
        assert(g[u].size() > degree[u] );
        assert(g[v].size() > degree[v] );
        g[u][degree[u]++] = v;
        g[v][degree[v]++] = u;
    }
    // pick an arbitrary root, let us say 0. Find farHaunted
    dfs(0, -1);
    // now do another DFS to fill reallyFar:
    dfs2(0, -1, -1);
    
    for (int i=0; i<n; i++) {
        if (reallyFar[i] <= d) {
            res ++;
        }
    }
    return res;
}

Read More

SRM 588: ouch (Update)

As I write this, I have to go, I am scheduling this to be up the time the challenge phase ends.

Div1 medium: The one with keys

There are up to 12 rooms, each with some red and green locks (up to 10 of each kind). You can use red or white keys to open red locks and green or white keys to open green locks. Each key is consumed once you use it. Each room has keys inside. What is the maximum number of keys you can have?

I was at first trying to make a viable dynamic programming solution. Similar to a GCJ problem. But I was not able to optimize it.

I eventually settled for a brute force search. Whenever you decide to open a room, you should only use white keys if you NEED to. This approach was slow, so I optimized it using all the dirtiest tricks in the book. Let us see if it passes.

Update: Turns out it passes system tests, so I will explain it.

Try all permutations of the order in which you open the rooms.

If you decide to enter a room and you have enough red and green keys, then you simply shouldn't use white keys. You should always use as little white keys as possible. Turns out this is also the "key" to solve it using dynamic programming.

With this, your approach needs `O(n!)` time, 12! is high, but not very high. So we can try some optimizations.

Imagine that at a given moment, there is one room that can be opened and after opening it, you end up with at least as many keys of each type as before. Then you should always open this room. So you shouldn't try sequences in which this room isn't opened.

Another special case, there is a room that you can open, but after opening it you end up with less keys of each type. This room is never a good idea. Ignore it.

I think that the two previous optimizations are enough , I was about to submit this, but last second I decided I could do an extra optimization, give priority to moves that give the maximum number of total keys, and cut the search when we tried too many options. I am not sure this is necessary, but I put it just in case.. Update 2: Yeah, it turns out this optimization wasn't needed.

Before the match I found out std::function causes a bug in TopCoder. That was too bad, because since there is no sane way to have anonymous recursion in c++ without using it, I had to use an outside function for the backtracking. This meant I had to copy all 5 argument variables as class members. What a bore.

vector<int> doorR,doorG,roomR,roomG,roomW;
int n, best, options[12];

void rec(int p, int r, int g, int w)
{
    best = std::max(best, r + g + w);

    if (p < n) {
        //each tuple is (i, nr,ng,nb):
        tuple<int,int,int,int> results[n-p]; //possible options
        int t = 0;
        
        for (int i=p; i<n; i++) {
            // for each candidate options[i], find if it is possible,
            // save it in results
            int &x = options[i];
            int nr = r - doorR[x];
            int ng = g - doorG[x];
            int nw = w;
            if (nr < 0) {
                // Not enough red keys, use white keys
                nw += nr;
                nr = 0;
            }
            if (ng < 0) {
                // Not enough green keys, use white keys
                nw += ng;
                ng = 0;
            }
            if (nw >= 0) {
                // if the number of white keys is non-negative we can do it
                // Increase the number of keys
                nr += roomR[x];
                ng += roomG[x];
                nw += roomW[x];
                if ( nr >= r && ng >= g && nw >= w) {
                    // This move is always a good idea, we should do it:
                    swap(options[p], options[i]);
                    rec(p+1, nr,ng,nw);
                    t = 0;
                    swap(options[p], options[i]);
                    break;
                } else if ( nr > r || ng > g || nw > w) {
                    // Make sure the move is a good idea before adding it
                    results[t++] = make_tuple(i,nr,ng,nw);
                }
            }
        }
        // process tuples:
        for (int j=0; j < t; j++) {
            int i, nr,ng,nw;
            tie(i, nr,ng,nw) = results[j];
            swap(options[p], options[i]);
            rec(p + 1, nr, ng, nw);
            swap(options[i], options[p]);
        }
    } 
}

int maxKeys(vector <int> doorR, vector <int> doorG, vector <int> roomR, vector <int> roomG, vector <int> roomW, vector <int> keys)
{
    // copy stuff, this is tedious:
    this->n = doorR.size();
    this->doorR = doorR;
    this->doorG = doorG;
    this->roomR = roomR;
    this->roomG = roomG;
    this->roomW = roomW;
    best = 0;
    for (int i=0; i<n; i++) {
        options[i] = i;
    }
    rec(0, keys[0], keys[1], keys[2]);
    return best;
}

Div1 easy: The one with songs

You have T time available to play as many songs as you can. Each song has a duration and a tone. If the tones of two consecutive songs are `x, y` then you need to rest `abs(x-y)` time units before playing the second song. What is the maximum number of songs?

It took me too long to correctly code this solution. As usual, I waited till there were less than 10 minutes before opening this problem.

The trick is, let us say you decide to play some songs. If the minimum tone is `p` and the maximum tone of the songs you play is `q`, then the minimum time you will need to wait because of the tone is always `q - p`. So, let us pick the minimum and maximum tone of the songs you will play, `O(n^2)` options for this pair. The rest is just to play the best song durations between these tones such that the total duration is less than or equal to `T - q + p`.

int maxSongs(vector <int> duration, vector <int> tone, int T)
{ 
    //sort the tones:
    int n = tone.size();
    for (int i=0; i<n; i++) {
        for (int j=i+1; j<n; j++) {
            if (tone[j] < tone[i]) {
                swap(tone[j], tone[i]);
                swap(duration[j], duration[i]);
            }
        }
    }
    int res = 0;
    // pick the minimum and maximum tone:
    for (int a=0; a < n; a++) {
        for (int b=a; b < n; b++) {
            int t = T - tone[b] + tone[a];
            int c = 0;
            // save the durations in a vector
            int tim = 0;
            vector<int> d;
            for (int i=a; i<=b; i++) {
                d.push_back(duration[i]);
            }
            // sort the durations, so that we pick the smallest c durations:
            sort(d.begin(), d.end());
            for (int x: d) {
                if (x <= t) {
                    t -= x;
                    c ++;
                }
            }
            // remember the best
            res =std::max(res, c);
        }
    }
    return res;
}

Read More