Codeforces round #113 div2 (unofficial)

I am tired of these unofficial events in codeforces. All normal rounds this month seem to be div2 only. Then we have all the VK cup stuff which down right banned us old people. I think div2-only matches could be rated for div1 coders. The rating system should permit it.

Today was strange in that Codeforces was testing "dynamic problem scores". This just means that at the start of the contest, you have no idea what problem is the easiest anymore. The problem scores get updated according to the amount of people that solve each problem. So at the end, you get more points for solving problems less people solve. I am not sure yet if this is an amazing idea or another hassle that turns the game into "find the hidden easy problem" like ACM.

Problem A link
I had a delay at the start of the contest. Lack of rating makes me take these things too lightly. Anyway, not much to do here. Constraints are lower than you'll ever need. You can just sort the given array of problems/penalties according to the statement and just calculate the answer manually.

Problem B link
This problem made me realize that problems are not sorted by difficulty in this contest. Oh well. It is your generic geometry problem. I decided to skip it.

A solution idea that is correct but has many implementation hassles: Pick an arbitrary point from B. If it is outside A's polygon, then return NO. Else, just move between the segments in B starting at that point. If any segment of B intersects a segment of A, then there is no way. You might be able to do a line sweep algorithm to do this quickly enough. A variation, since they are polygons is to, after picking the point in B, find the angles between the points in A and the point you picked. Then for each segment in B, do the same. When picking a segment in B and wanting to look for intersections, you only need segments in A that match the angle range...

Problem E link
First thing I did after noticing that B was hard, was open E. And surprise! It is a rather standard problem. In fact, perhaps way too standard. The shape is a mere dense graph of 4 nodes. Counting the number of paths between all pairs (i,j) of a given length is a standard problem that can be solved in O(n^3 * log( length ) ) time - Simply raise the adjacency matrix (result for length=1) to the (length-1)-th power. Then the result is A[0][0] (the graph is dense, so A[1][1], A[2][2] and A[3][3] hold the same result.

Problem C link
It seemed many were solving this problem, so I picked it.

Note that the number of elements to add is O(n). If the median is currently at position K of the sorted array, you can add other K elements and done. So we can just iterate for the number of added elements.

Note that the wanted median may not necessarily be in the array. You can handle this special case by just adding it, and increasing the result by 1.

Then for each new array size nn, you test you find that the median will be at position (nn+1) / 2 of the sorted array. Let's say that the original array has a variable "less" of elements smaller than the wanted median and "eq" of elements equal to the median (because we handled the special case, this is at least 1). The wanted median will be at least in position (less+1). The upper bound is more interesting, if we don't add any element, then it will be in at most position (less+eq). But since we will add (available = nn-n) elements, we can decide some of these elements to be smaller than the wanted median. Thus the maximum position of the wanted median is: (less+eq+available). Finally, if (nn+1)/2 is between (less+1) and (less+eq+available) then it is possible to have that median when the length of the new array is nn.

int n; 
int a[100000]; 
int wantedMedian; 
 
int solve() 
{ 
     
    int less = 0; //elements < wantedMedian in the original array 
    int eq = 0; //elements <= wantedMedian in the original array 
    for (int i=0; i<n; i++) { 
        less += (a[i] < wantedMedian); 
        eq += ( a[i] == wantedMedian ); 
    } 
    int add = 0; 
    // If the array does not contain the wanted median, we shall always add it: 
    if (eq == 0) { 
        add = 1; 
        eq = 1; 
        n ++; 
    } 
    int nn = n - 1; 
     
    bool worked; 
    do { 
        nn ++; 
        // can the final array have nn elements? 
        // median will be located at position: 
        int p = (nn + 1) / 2; 
         
        int available = (nn - n); 
        // the wanted median is at least at position less+1. 
        // the wanted median is at most at position less+eq+available. 
        worked =  ( less+1 <= p && p <= less+eq+available );         
    } while (! worked); 
    return (nn - n) + add; 
} 
 

Later
I then went to have lunch while trying to solve problem D. I came back and tried some code with no success. I never felt like trying to code B. Forgot to mention there's likely an easier solution for it. But of course, always with geometric functions I was sort of too bored to play with.