## Friday, March 23, 2012

### 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.

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.

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...

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.

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 );
}
// If the array does not contain the wanted median, we shall always add it:
if (eq == 0) {
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.

Bruno said...

Hi, for problem E there is a simpler dp to solve it:

dp[0][i] = dp[1][i-1]*3
dp[1][i] = dp[0][i] + dp[1][i-1]*2

Its like 'how many paths there are with lenght i ending at D (dp[0][i])' and 'how many paths there are with lenght i ending anywhere else but D (dp[1][i])'.

vexorian said...

Not sure which is really simpler. The solution that just needs you to paste your matrix power code. Or that dp solution. Anyway, you can actually adapt that dp solution to have a 8*log(length) solution (2x2 matrix) as opposed to the 256*log(length) solution (4x4 matrix).

Bruno said...

You are right :)

Hey, could you help me on the problem D? I read at the editorial that is a dp problem (it only says that actually). So I tried the following dp:

You have the current person and a mask that represents if the 2 sizes of shoes that this person can use are available (costumers are sorted by shoe size), so it will be a dp[10⁵][4] table.

That is giving WA, maybe my approach is wrong? Here is my submission: http://codeforces.com/contest/166/submission/1400293

Some said that it is solvable with greedy+matching, but it should lead to TLE, and some got ACC because the test cases are weak..

Thank you!

Bruno said...

Found the bug! It happens on the operation x>>y, if y is big it uses only the first 5 bits, so something like 100000 (base 2) wont make x equal 0!

vexorian said...

Oh sorry for not replying before. I didn't notice the notification. Not like I would have done much to help as I haven't solved the problem yet.

Bruno said...

Haha, no problem ^^