Codeforces Beta round #95

I had a very awful experience today, related to brain apparently forgetting c++.

A - cAPS lOCK
Really a implementation problem.

B - opposites attract
This was so painful.

Anyway, keep in mind that customers with T=0, are the only ones that we have to worry about not matching with themselves. So, we should treat them separately.

We can first count the total number of ways to match customers with T different to 0. We should count for each x from 1 to 10. Let us say count[x] and count[-x] give the number of customers of two opposite counts, then there are (count[x]*count[-x]) couples that have T=abs(x).

Now, for 0, we need to count the unordered pairs. This is known to be (count[0]*(count[0] - 1)) / 2.

Unfortunately, I was failing AND FAILING pretests. I had no idea why. As you can see, the problem is not very difficult. I tried everything to debug. Even suspected a compiler bug.

Eventually , I noticed that I somehow forgot that 64 bits integers in c++ are (long long) not (long) !. Really, this is so strange. It is not like I did not use long long in the last week. I am not sure what happened there.

C - the world is a theatre
This was really all about combinatorics theory. First of all, let us decide the number of girls and boys. It has to add up to t and we also need at least one girl and at least four boys. So, we can just iterate for the number of girls g. Find b = t - g (the number of boys). If they are valid, count the number of ways to pick them.

First of all, of the n boys, pick b. This is Combinations(n, b). (http://en.wikipedia.org/wiki/Combinations) . Then pick g girls out of the m available, that's Combinations(m , g).

We can precalculate the binomial / combinations / whatever using pascal's triangle.

long long C[61][61]; 
 
long long solve(int n, int m, int t) 
{ 
    long long res = 0; 
    for (int g=1; t-g >= 4; g++) { 
        int b = t - g; 
        res += C[m][g] * C[n][b]; 
    } 
    return res; 
} 
 
void init() 
{ 
    memset(C,0,sizeof(C)); 
    for (int i=0; i<=30; i++) { 
        C[i][0] = 1; 
        for (int j=1; j<=i; j++) { 
            C[i][j] = C[i-1][j] + C[i-1][j-1]; 
        } 
    } 
} 

I got hacked during the match because I forgot that I need a 60x60 table, let me fix the issue. Thanks hacker.

D - SubWay
Mostly your Graph theory problem.

First of all, we need to keep in mind that the input can be quite large (3000). So, let us try to keep things linear.

A DFS (http://en.wikipedia.org/wiki/DFS ) can be used to find the cities in the cycle ( ring ). In O(n) time (n cities and n roads).

Then we need to calculate the distance between each city and a cycle. It is faster in this case to use the cities inside the cycle as a starting point, and instead find the distances between the cycle to each of the cities, a single BFS (http://en.wikipedia.org/wiki/Breadth-first_search) can be used to do this.

int N; 
int r1[3000]; 
int r2[3000]; 
int dist[3000]; 
 
int visited[3000]; 
int parent[3000]; 
 
bool cycle[3000]; 
 
vector<int> G[3000]; 
int degree[3000]; 
 
bool dfs(int x, int prev, int indent = 0) 
{ 
    if (visited[x] == 0) { 
        parent[x] = prev; 
        visited[x] = 2; 
        //cout<<string(indent,' ')<<"{ 2 : "<<x<<" , "<<prev<<endl; 
        for (int i=0; i<degree[x]; i++) { 
            if (G[x][i] != prev) { 
                dfs(G[x][i], x, indent+1); 
            } 
        } 
        //cout<<string(indent,' ')<<"}"<<endl; 
        visited[x] = 1; 
    } else if (visited[x] == 2) { 
        //cycle... 
        int z = prev; 
        while ( z != x ) { 
            cycle[z] = true; 
            z = parent[z]; 
        } 
        cycle[x] = true; 
    } 
} 
 
void solve() 
{ 
    fill(degree, degree+N, 0); 
    for (int i=0; i<N; i++) { 
        int x = r1[i]; 
        int y = r2[i]; 
        degree[x]++; 
        degree[y]++; 
    } 
    for (int i=0; i<N; i++) { 
        G[i].resize( degree[i] ); 
        degree[i] = 0; 
    } 
    for (int i=0; i<N; i++) { 
        int x = r1[i]; 
        int y = r2[i]; 
        G[x][degree[x]++]=y; 
        G[y][degree[y]++]=x; 
    } 
     
    fill(visited, visited+N, 0); 
    fill(cycle, cycle+N, false); 
    for (int i=0; i<N; i++) { 
        dfs(i, -1); 
    } 
    const int INF = 6000; 
    fill(dist, dist+N, INF); 
    queue<int> Q; 
    for (int i=0; i<N; i++) { 
        if (cycle[i]) { 
            Q.push(i); 
            dist[i] = 0; 
        } 
    } 
    while (! Q.empty() ) { 
        int x = Q.front(); 
        Q.pop(); 
        for (int i=0; i<degree[x]; i++) { 
            int y =G[x][i]; 
            if (dist[y] > dist[x] + 1) { 
                dist[y] = dist[x] + 1; 
                Q.push(y); 
            } 
        } 
         
    } 
} 

E - Another queens task
A very evil implementation problem. Ever since the little crisis in B, I was rushing to solve the other problems (which caused the issue with C, I guess). So I tried to do this one as fast as possible.

Anyway, a solution goes like this: Let us divide the problem into first verifying if each queen has a queen to its left. We need to do this very fast - O(m). Imagine first that we were visiting each cell row by row and cell by cell in top to bottom and left to right order. Then whenever we found a queen, we would know if we found a queen in the same row before (and since we found it before, it is to the left of the current queen).

Now to optimize, note that there is nothing to do in the empty cells, so we can just ignore them. Sort the queens by row and then by column as a tie breaker. And iterate through them. For each queen, check if the previous queen is in the same row or not.

That solves for just left. Now, here is the painful part. We can use the same exact logic for right, up, down, and each of the four diagonal directions. Only using diagonals or columns or reversing the direction.

It does not have to be so hard. We can just convert the board into a new setting with different coordinates and then just use the same code we used for left. For example, if we want to count for "right", we can just invert the column number. If we want to count for "up", just swap row and column numbers. Etc. This yields the following code:

int n, m; 
int qx[100000]; 
int qy[100000]; 
int qc[100000]; 
int t[9]; 
 
pair< pair<int,int> , int > awesome[100000]; 
 
void sortCount() 
{ 
    sort(awesome, awesome + m); 
    for (int i=1; i<m; i++) { 
        if ( awesome[i].first.first == awesome[i-1].first.first) { 
            qc[ awesome[i].second ]++; 
        } 
    } 
} 
 
void fix0() 
{ 
    for (int i=0; i<m; i++) { 
        awesome[i].first = make_pair( qx[i], qy[i] ); 
        awesome[i].second = i; 
    } 
} 
void fix1() 
{ 
    for (int i=0; i<m; i++) { 
        awesome[i].first = make_pair( qx[i], -qy[i] ); 
        awesome[i].second = i; 
    } 
} 
void fix2() 
{ 
    for (int i=0; i<m; i++) { 
        awesome[i].first = make_pair( qy[i], qx[i] ); 
        awesome[i].second = i; 
    } 
} 
void fix3() 
{ 
    for (int i=0; i<m; i++) { 
        awesome[i].first = make_pair( qy[i], -qx[i] ); 
        awesome[i].second = i; 
    } 
} 
 
void fix4() 
{ 
    for (int i=0; i<m; i++) { 
        awesome[i].first = make_pair( qx[i]+qy[i], qx[i] ); 
        awesome[i].second = i; 
    } 
} 
void fix5() 
{ 
    for (int i=0; i<m; i++) { 
        awesome[i].first = make_pair( qx[i]+qy[i], -qx[i] ); 
        awesome[i].second = i; 
    } 
} 
void fix6() 
{ 
    for (int i=0; i<m; i++) { 
        awesome[i].first = make_pair( qx[i]-qy[i], qx[i] ); 
        awesome[i].second = i; 
    } 
} 
void fix7() 
{ 
    for (int i=0; i<m; i++) { 
        awesome[i].first = make_pair( qx[i]-qy[i], -qx[i] ); 
        awesome[i].second = i; 
    } 
} 
 
 
 
void solve() 
{ 
    fill(qc, qc + m  , 0); 
     
    fix0(); 
    sortCount(); 
    fix1(); 
    sortCount(); 
    fix2(); 
    sortCount(); 
    fix3(); 
    sortCount(); 
    fix4(); 
    sortCount(); 
    fix5(); 
    sortCount(); 
    fix6(); 
    sortCount(); 
    fix7(); 
    sortCount(); 
 
     
     
    fill(t, t+9, 0); 
    for (int i=0; i<m; i++) { 
        t[ qc[i] ]++; 
    } 
} 
 

F - Present to mom

I didn't have much time to try this problem. I'd say it is fairly dynamic programming and OR using accumulated sums. By the time I opened I had little time already. But then C got hacked and had to debug it. Overall, make sure to do things in quadratic time.