Evil SRM 541 is evil

Another day, another topcoder contest.

Oh well. After round 2A and now this SRM my rating was going to suffer. I did so many stupid things today that it is hard to believe. At the end, once I noticed my rating was going to die, I decided that I may as well increase my volatility so I opted to do a wrong challenge

It was a cool problem set by a new talent. The div1 250 was easy, it just required you to think things over to avoid making the implementation too long. But if you do make the implementation short, you got to be careful not to make a very stupid mistake that was not caught by the examples. The story with div1 550 is... actually the same. These two factors combined into the perfect anti-vexorian storm.

div1 250: The one with the ants

I was first going to do a complicated bruteforce thing finding equations to get the intersections of each line. In the middle of that business, I noticed that there was an easier (wrong) solution.

The maximum time at which ants can meet is after 4000 moves. Now, we can say that each ant has a pair (dx, dy) which describes its direction (The ant's coordinate change after 1 move, for example , an ant that goes north has (dx=0, dy=1), and an ant that goes west (dx=-1, dy=0). So, the position of the ant after t moves will be: (x[i] + t*dx[i], y[i] + t*dy[i]). Great. So, you can just try all times from 0 to 4000. Then for each pair of (not removed yet) ants, find their positions after the given time, and if their positions are the same, take them out.

This solution is wrong, but only slightly wrong. The issue is that ants will not necessarily meet at a point with integer coordinates. The easiest example would be two ants that initially begin next to each other and each goes to the opposite direction of each other. They will meet exactly one step later in the middle point between their cells.

The solution to this bug is simply to notice that if ants find each other at a coordinate, the coordinate will be integer OR it will be a integer plus 0.5. (Can only meet exactly at the middle of between two cells). Thus you can just use time values like t=0, t=0.5, t=1, ... and do the same thing. Alternatively, you can just multiply every starting coordinate by 2 and also the time limit.

int countAnts(vector <int> x, vector <int> y, string direction) 
{ 
    int n = x.size(); 
    for (int i=0; i<n; i++) { 
        // multiply everything by 2 
        x[i] *= 2; 
        y[i] *= 2; 
    } 
    // find directions dx,dy for each ant: 
    map<char, int> chdy; 
    chdy['N'] = 1; 
    chdy['S'] = -1; 
    map<char, int> chdx; 
    chdx['E'] = 1; 
    chdx['W'] = -1; 
    int dx[n]; 
    int dy[n]; 
    for (int i=0; i<n; i++) { 
        dx[i] = chdx[direction[i]]; 
        dy[i] = chdy[direction[i]]; 
    } 
     
    // simulate everything 
    bool active[n]; 
    fill(active,active+n, true); 
    
    int t = 0; 
    while(t <= 4000) { //The time limit was 2000, we multiplied everything by 2 
        for (int i=0; i<n; i++) if (active[i]) { 
            for (int j=i+1; j<n; j++) if (active[j]) { 
                if ( ( y[i] + dy[i]*t == y[j] + dy[j]*t ) 
                   && ( x[i] + dx[i]*t == x[j] + dx[j]*t ) 
                 ) { 
                    active[i] = active[j] = false; 
               } 
            } 
        } 
        t++; 
    } 
     
    return count(active, active+n, true); 
}

div1 550: The one with the strings

You know, I thought I was going to solve this during the match, because I sort of had the initial idea the second I read the problem. (This problem reminds me of EndlessStringMachine, which I loved although it is a little harder). But I also knew implementation would be tough to do correctly. I also did not optimize my idea well enough before coding it. Mind you, my idea was all right, but it was overcomplicated and I could not finish debugging it in time (I had an hour to code it and no help). It does not help that I needlessly used dynamic programming and matrix power...

Here is the easier solution: For simplicity, I will rename the variables in the input to left, middle, right, S, F and K. So that using the string means concatenating (left + X + middle + X + right). In fact, I will define a string called hack = left+"*"+middle+"*"+right. This string just puts a * in the places where we have to place X.

First of all, let us solve this problem when K is not very large. There is a simple iterative solution that just requires us to tinker some few things. Let us say that the result after (t-1) steps (times the function gets applied) is known: r[t-1]. Then we can find the result after (t) steps by using the following formula:

r[t] = 2*r[t-1] + A(t)

r[t-1] is the number of substrings in f^(t-1){S} that are equal to F., thus the number of substrings inside the * areas in (left*middle*right) is equal to 2*r[t-1]. We just need to know A(t) - The number of substrings equal to F, that may or may not cover characters from the * area, but definitely cover at least one character from left, middle or right. So when calculating A(t) we only care about the instances of F() that begin or finish in one of the characters that were added at time t.

The main trick is to notice that after a quantity of steps, the values of A(t), A(t+1), A(t+2)... all become constant - the same. Let me introduce you to an easy case: a*b*c, x, axb:

0: x
1: axbxc
2: aaxbxcbaxbxcc
3: aaaxbxcbaxbxccbaaxbxcbaxbxccc
4: aaaaxbxcbaxbxccbaaxbxcbaxbxcccbaaaxbxcbaxbxccbaaxbxcbaxbxcccc
...

The idea is that eventually, next to the characters added at time t, there will always be either a repetition of left (in this example aaaaa...), or right (in this example ...ccccc). There will be a time at which the n left repetitions and the n right repetitions will be larger than the length of F. In fact, this will always happen after at most 50 steps (Because that is the length of F). In conclusion, we only need to find A(t) for t <= 50. After that, we can assume that A(k) = ... = A(52) = A(51) = A(50) and be happy, because the iterative solution res[k] = res[k-1]*2 + A can be found easily because k is at most 10000000.

What is left to do is to find the way to solve res[0] and A(t) for t <= 50.

At time 0, the result string is merely S, so res[0] is simply the number of times F appears as a substring of S.

A(t) is the part of the problem that is hard to implement. It helps that we represent the function as left*middle*right though. First of all, we need to find the lengths of the strings returned by the function for all necessary values of t. len[0] = length(S). len[i] = 2*len[i-1] + (characters in left, right and middle). It is very lucky that t is at most 50 in this calculation, because you will see that in the worst case, len[50] is very large and just a couple of steps away of overflowing signed 64 bits integers, thankfully it does not.

At time t, the length of the string is len[t], of all those len[t] positions, we need to extract the positions that would be good for a substring of size len(F) that overlaps with the added left, middle or right. This procedure is not as difficult as you would think. Simple use hack = left*middle*right and iterate through all characters in hack. But for every *, you got len[t-1] starting positions but only some are valid in a way that overlaps with the added parts. Since a string has to begin or end at a character added in time t, there are at most 300 positions to pick. For each of those positions, we need to extract the substring of len(F) elements that begins at that location at time t and compare it with F.

Extracting the substrings

The substrings will always be of size length(F), this means that you will need length(F) steps to extract them if you decide to instead just extract the characters at a given position. The idea is to make a function get(t, p) that returns the p-th character after time t. To implement this function, once again take advantage of hack = left*middle*right. You need to check if p ends at a new character or at a * character. If it ends at a * then you will need to call get(t-1, new position). Since you recurse at most once per function call, you do not need any fancy implementation tricks and can just implement the recursive approach.

Hopefully the code will clear any misunderstanding:

typedef long long int64; 
#define long int64 
 
const int MOD = 1000000007; 
 
 
using namespace std; 
 
const int BASIC = 50; 
struct AkariDaisukiDiv1 
{ 
    string hack; 
    string S, F; 
     
    long len[BASIC]; 
 
    // Get the p-th character of f^t(p)     
    char get(int t, long p) 
    { 
        if (t == 0) { 
            if (p >= S.length()) { 
                return '-'; 
            } 
            return S[(int)p]; 
        } 
        long x = len[t-1]; 
        for (int i=0; i<hack.size(); i++) { 
            if (hack[i] == '*') { 
                if (p < x) { 
                    return get(t-1, p); 
                } 
                p -= x; 
            } else if (p == 0) { 
                return ( hack[i]  );  
            } else { 
                p--; 
            } 
        } 
        return '-'; 
    } 
     
    // At time t, count the number of substrings equal to F, such that they 
    // overlap with the added left, middle or right parts. 
    int A(int t) 
    { 
        // we got a string left{X}middle{X}righ{X} 
        int res = 0; 
        long p = 0, x = len[t-1]; 
        vector<long> valid; 
        for (int i=0; i<hack.size(); i++) { 
            if (hack[i] == '*') { 
                for (int o=1; o<=x && o<F.length(); o++) { 
                    valid.push_back(p+x-o); 
                } 
                p += x; 
            } else { 
                valid.push_back(p); 
                p++; 
            } 
        } 
        for (int i=0; i<valid.size(); i++) { 
            bool ok = true; 
            for (int j=0; (j<F.length()) && ok; j++) { 
                ok = ( get(t, valid[i] + j) == F[j]); 
            } 
            res += ok; 
        } 
        return res; 
    } 
 
    int countF(string left, string middle, string right, string S, string F, int k) 
    { 
        //F = "dc"; 
        hack = left+"*"+middle+"*"+right; 
        this->S = S; 
        this->F = F; 
 
        len[0] = S.length(); 
        for (int i=1; i<BASIC; i++) { 
            int a = hack.length() - 2; 
            len[i] = 2*len[i-1] + a; 
        } 
 
        // Base case: how many times is F a substring of S? 
        long a = 0; 
        long r = 0; 
        for (int i=0; i<S.size(); i++) { 
            int x = F.length(); 
            r += (S.substr(i,x) == F ); 
        } 
 
        for (int i=1; i<=k; i++) { 
            // a is the number of substrings equal to F that overlap with 
            // left, middle or right at time i: 
            // 
            // After BASIC steps, a will become constant. 
            if (i < BASIC) {     
                a = A(i); 
            } 
            r = ( 2*r + a ) % MOD; 
        } 
        return r; 
    } 
}; 
#undef long