Competitive Programming

Upcoming competitions

Problems for this week

Update on Arena Survival

The following brute force solution (arena-brute.cpp) completes in 50 ms on my machine—a long shot from the 0.35 ms of the mathematical solution but probably still within the time limit—and seems to be sufficiently accurate, so this is probably the intended solution:

#include <iostream>
#include <cmath>
#include <cstdio>

double distance(double x1, double y1, double x2, double y2) {
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

int main() {
    int n;
    std::cin >> n;
    for(int i = 0; i < n; i++) {
        double r1, r2, x, y;
        std::cin >> r1 >> r2 >> x >> y;

        long long int hits, tests;
        hits = tests = 0;

        double epsilon = r1 / 1500.0; 
        // 1500 is the maximum divisor that seems to result in an acceptable runtime

        for(double x1 = -r1; x1 <= r1; x1 += epsilon) {
            for(double y1 = -r1; y1 <= r1; y1 += epsilon) {
                if(distance(x1, y1, 0, 0) > r1 - r2) {
                    // point is not a possible center for the new arena
                    continue;
                }
                tests++;
                if(distance(x1, y1, x, y) < r2) {
                    hits++;
                }
            }
        }

        double p = (double) hits / (double) tests;
        printf("%.2f\n", p);
    }
}

Array and Segments

This problem appeared on Codeforces Round 535 with two variants—one in which array a has maximum length 300 and one in which array a has maximum length 105. As such, any solution to the "Hard" variant will also be a solution to the "Easy" variant—but solutions to the "Easy" variant may not complete within the time limit for the "Hard" variant.

A cursory glance at this problem suggests it is somewhat similar to "Long Long Strings," which we did last semester. My solution to that problem is included in the notes from January 17. I'll post solutions to Array and Segments here before next week.

Ivan and Burgers

There are a couple things we can do to simplify this problem. First, the starting balance of Ivan's bank account is 2 2 100 - 1 , a number decidedly too large to work with comfortably (to store it would use nearly 160 billion exabytes of memory, which is greater than the 256 MB limit imposed by Codeforces). But since each transaction is a bitwise XOR on this balance rather than a subtraction, and the "price" of each burger 10 6 < 2 20 , we need only concern ourselves with the lower 20 bits of the balance—the upper 2 100 - 21 bits cannot change. Furthermore, we know all bits of the balance are initally set to 1, so for our purposes Ivan's balance is the much more wieldy 2 21 - 1 .

Since Ivan's starting balance contains only set bits, the final bitwise XOR to calculate his expenditure is equivalent to a bitwise NOT. This means that to get the minimum final balance in his account, we need to find the maximum value with which to XOR his balance.

An ineffective solution

Let's start by solving for one friend. We can develop an algorithm using very small numbers then extend it to larger numbers later.

A simple test case with values of 3, 5, and 4 for ci demonstrates that a simple greedy algorithm tracking the maximum expenditure after each restaurant will not work: after the first shop, we can spend a maximum of 3 burles; after the second shop, we can spend a maximum of 6 burles; but after the third shop, we can spend a maximum of 7 burles (by eating at the first and third shops)—if we already ate at the first two shops to get an expenditure of 6 burles, eating here would reduce our total expenditure to 2 burles, so this algorithm would not select this shop.

We could keep track of all the possible expenditure values after eating at each shop. In the above example, we can achieve any expenditure except for 1 burle with some combination of the three shops. As previously discussed, we can spend a maximum of 2 21 - 1 burles, so it is not unreasonable to store an array of whether each value is reachable—if each boolean takes up one bit, the size of this array would be 262,144 bytes (of course, in C++ the behavior of an array or vector would be to store each boolean in its own byte, but this still isn't near the 256 MB limit).

How long would this take? At each shop, we would have to read the entire array, xor-ing indices of true values with that shop's price and setting the value at that index, so we'd be looking at up to a trillion operations. The compiler would probably optimize some of those away, but it's still far too many, particularly when we would have to do it for each of Ivan's 500,000 friends.

We could store a vector of reachable values and separately store the maximum reachable value. Then we can simply iterate over the vector at every shop, xor-ing values in the vector with the cost of that shop's burger and updating the stored maximum reachable value as needed. Furthermore, if the maximum reachable value reaches its maximum possible value of 2 21 - 1 , we can break out early:

#include <iostream>
#include <vector>

int main(void) {
	int maxPossible = (1 << 21) - 1;
	int n, q;
	std::cin >> n;
	int c[n];
	for(int i = 0; i < n; i++) {
		std::cin >> c[i];
	}
	std::cin >> q;
	for(int i = 0; i < q; i++) {
		int li, ri;
		std::cin >> li >> ri;

		std::vector<bool> reachable(maxPossible + 1, 0);
		std::vector<int> reachableVector = {0};
		int maxReachable = 0;
		for(int j = li - 1; j < ri; j++) {
			reachableVector.push_back(c[j]); // We can always reach this value by eating only here
			if(c[j] > maxReachable) {
				maxReachable = c[j];
			}
			for(int i = 0; i < reachableVector.size(); i++) { // can't use range-based for since we modify vector
				int reachableValue = reachableVector.at(i);
				int xord = reachableValue ^ c[j];
				if(reachable.at(xord)) {
					continue; // already reached
				}
				reachable.at(xord) = 1;
				if(xord > maxReachable) {
					maxReachable = xord;
					if(xord == maxPossible) {
						break;
					}
				}
				reachableVector.push_back(xord);
			}
			if(maxReachable == maxPossible) {
				break;
			}
		}

		std::cout << maxReachable << '\n';
	}
}

This program (burgers-partial.cpp) works, but even with one friend is a bit too slow when there are many burger joints. An input file (burgers_singlefriend.in) generated with burgers.py caused it to take 3 minutes, 10 seconds on my system—and the input file only had Ivan and his friend walk from joint 191,248 to joint 267,253, a tiny fraction of the possible 500,000-joint walk. With an actual maximal input, it would take 18.8 years to complete even if the time complexity were linear, and since the number of calculations at each restaurant increases when more restaurants have been visited previously, it could potentially take millions of years.

Another approach

We want to find the maximum xor-summation of any subset of a given subarray of ci. We can do this by maximizing the most significant bit, then maximizing the next bit out of the combinations that remain after maximizing the most significant bit, and so on.

For each bit, we know the result bit will be set if and only if we xor together an odd number of values with this bit set. It does not matter how many values with this bit unset we xor together. So whenever possible we want to come up with a subset of joints in which an odd number of elements have their most significant bit set.

Since we don't need to know which burger joints yield the optimal solution, we can start by separating the set of burger joints into a set of burger joints with the most significant bit set and another set of those with the most significant bit unset. When the size of the former set is zero, we don't need to do anything—we can simply continue to the next bit, as there's no way to get a value of 1 out of the most significant bit. When it isn't zero, we will always want to use an odd number of the elements in that set.

If we implement this using brute force—checking every combination of an odd number of n> elements—we'll have to recursively test k = 0 n 2 - 1 n 2 k + 1 combinations, a number which grows very quickly with n (it can exceed 3.5 × 10 150514 ). So a simple recursive algorithm for that won't do.

If you think you know how to do this, here is a maximal input file for testing purposes: burgers.in

The official solution involves a lot of linear algebra and may be found here.