Codeforces round #112

It is 17 minutes before the end of the contest, I am giving up on E and D.

Problem A link
There are at most 200 points. You can actually do a O(n*n) search, for each point, iterate through all the other points and if the other point is a left,down,up or right neighbor, set a switch so you know that such a kind of neighbor was found.

int n; 
int x[1000]; 
int y[1000]; 
 
 
int solve() 
{ 
    int c = 0; 
    for (int i=0; i<n; i++) { 
        bool up = false; 
        bool down = false; 
        bool right = false; 
        bool left = false; 
         
        for (int j=0; j<n; j++) { 
            right |= ( y[i]==y[j] && x[i]<x[j] ); 
            left  |= ( y[i]==y[j] && x[i]>x[j] ); 
            down  |= ( x[i]==x[j] && y[i]<y[j] ); 
            up    |= ( x[i]==x[j] && y[i]>y[j] ); 
        } 
        if ( up && down && right && left ) { 
            c++; 
        } 
         
    } 
    return c; 
} 

Problem B link
Imagine the largest case, n=10^9, k=10. Then if you use something as large as v=10000000000, it will finish in one move. So that is a value of v that can work as an upper bound. It is a large bound, but what you can do is do a binary search. If it is not possible for a v, it will not be possible for a smaller v. And if it is possible for a large v, it should be possible for any larger v.

Testing each value in the binary search takes logarithmic time in base k. Thankfully, problemsetter was not evil to allow k=1 :)

bool possible(long n, int k, long v) 
{ 
    long done = 0; 
    long div = 1; 
    while (n > done) { 
        long todo = v / div; 
        if (todo == 0) { 
            break; 
        } 
        done += todo; 
        div *= k;  
    } 
    return (done >= n); 
} 
 
long solve(int n, int k) 
{ 
    long hi = 10000000000ll; 
    long lo = 0; 
     
    while (lo + 1 < hi ) { 
        long ha = (hi + lo) / 2; 
         
        if (possible( n, k, ha ) ) { 
            hi = ha; 
        } else { 
            lo = ha; 
        } 
    } 
    return hi; 
     
} 
 

Problem C link
Ok, with such large constraints we want a linear algorithm.

What about k=2, and a string like "00101001" ? Consider the definition of a important fragment: A fragment that begins and ends with 1 and contains exactly k 1s. In the example, there are two important fragments: --101--- and ----1001 Each of these two places has a number of adjacent 0s to the right and left sides (possibly zero). Now the key is to notice that the number of substrings that contain each of these important fragments is equal to (number of left zeros + 1) * (number of right zeros + 1). In other words, for fragment 101, surrounded by 00 to the left and 00 to the right, there are 9 substrings: 00101, 001010, 0010100, 0101, 01010, 010100, 101, 1010 and 10100. For fragment "1001", there are 2: "01001", "1001".

The problem becomes to find these fragments and count the side zeros in O(n). It is not actually so difficult. Let onepos be an array that contains the positions of 1 characters in the string. Then you can find that each fragment that begins at onepos[i] will finish at some onepos[i + k - 1]. Then you can use onepos[i-1] to count the zeros in the left side (consider the corner case when i=0, though) and a similar idea for the right zeros.

Catch: k can be 0. Then you have to count the number of substrings containing only 0 characters. Too bad I didn't see this during the match and had to resubmit.

To deal with this special case, use the onepos array once again, but this time to find all the maximal fragments that contain only zeros. From the sizes of each of these fragments, you can find the number of substrings inside it.

int k; 
string s; 
 
long solve() 
{ 
    vector<long> onepos; 
    for (int i=0; i<s.size(); i++) { 
        if (s[i] == '1') { 
            onepos.push_back(i); 
        } 
    } 
    long res = 0; 
    if (k == 0) { 
        for (int i=0; i <= onepos.size(); i++) { 
            long  a = ( (i==onepos.size()) ? s.size(): onepos[i] ); 
            long  b = ( (i==0) ? -1: onepos[i-1] ); 
            long leftZeros = a - b - 1; 
            // number of substrings inside this fragment that contains leftZeros zeros 
            res += ( leftZeros * (leftZeros + 1) ) / 2; 
        } 
    } else { 
        for (int i=0; i + k - 1 < onepos.size(); i++) { 
            int j = i + k - 1; 
            long leftZeros = onepos[i] - ( (i==0) ? -1 : onepos[i-1] ) - 1; 
            long rightZeros = ( (j==onepos.size()-1) ? s.size() : onepos[j+1] ) - onepos[j] - 1; 
            // number of ways to add zeros to the important fragment. 
            res += ( leftZeros + 1) * (rightZeros + 1); 
        } 
    } 
     
     
    return res; 
} 

D and E
I avoided D, it seemed that if I found a solution it would take long to code it. Note that the input is a tree (connected, with n-1 vertices) and the single vertex with more than 2 edges can easily be the root you pick. There are never more than 1 path connecting two vertices, so you are only interested in confirming if there is a path or not.

E seemed more interesting so I focused on it. With no success yet. Tried stuff with tries, but everything seems too slow. Might post an update later.