Competitive Programming

Upcoming competitions

Problems for this week

cAPS lOCK

Simplified problem description

If all characters or all but the first character in the input word (which matches /^[A-Za-z]+$/) are uppercase, swap the case of all characters in the word and output it. Otherwise, output the input word.

Solutions

For doing nothing but manipulating a string of arbitrary length, I'd use Python, or Perl if possible. There isn't much to this problem—indeed, the official solution when translated from Russian effectively reads "Do everything that is requested in the problem" with a recap of the problem.

Python: capslock.py – this solution runs in 14.1 ms on my system and 140 ms in Codeforces' environment.

import re
word = input().strip()
if re.match('^[a-z]?[A-Z]*$', word) is not None:
    word = word.swapcase()
print(word)

Perl: capslock.pl – this solution runs in 0.35 ms on my system and 30 ms in Codeforces' environment.

$_ = <>;
tr/A-Za-z/a-zA-Z/ if /^[a-z]?[A-Z]*\s*$/;
print;

C++: capslock.cpp – this solution runs in 0.34 ms on my system and 30 ms in Codeforces' environment.

#include <iostream>
#include <string>
#include <cctype>

int main() {
    std::string word, converted;
    std::cin >> word;
    if(std::isupper(word[0])) {
        converted += std::tolower(word[0]);
    }
    else {
        converted += std::toupper(word[0]);
    }
    for(int i = 1; i < word.length(); i++) {
        if(std::isupper(word[i])) {
            converted += std::tolower(word[i]);
        }
        else {
            std::cout << word << std::endl;
            return 0;
        }
    }
    std::cout << converted << std::endl;
    return 0;
}

Repeating Goldbachs

Doing a sample input by hand

I didn't immediately understand this problem when I read it—both at November's competition and today. So I worked out the first test case (input 20, output 3) by hand to figure out what it wanted me to do:

  1. 20 = 17 + 3; 17 − 3 = 14
  2. 14 = 11 + 3; 11 − 3 = 8
  3. 8 = 5 + 3; 5 − 3 = 2

Obviously, it is a coincidence that in this case one of the primes is 3 for each number. For an input of, say, 38, this is not so:

  1. 38 = 31 + 7; 31 − 7 = 24
  2. 24 = 19 + 5; 19 − 5 = 14
  3. 14 = 11 + 3; 11 − 3 = 8
  4. 8 = 5 + 3; 5 − 3 = 2

The easy part

It is easy to see the following solution:

#include <iostream>

bool isPrime(int n) {
    // ???
}

int main() {
    int i = 0;
    int n;
    std::cin >> n;
    while(n > 3) {
        for(int j = 2; j <= n / 2; j++) {
            if(isPrime(j) && isPrime(n - j)) {
                n = n - j - j;
                i++;
                break; // out of for, not while
            }
        }
    }
    std::cout << i << std::endl;
    return 0;
}

But C++ doesn't have a built-in function for primality testing, nor do any of the other standard languages.

A naïve primality test

What if we simply do this (goldbachs-test.cpp)?

bool isPrime(int n) {
    for(int i = 2; i <= n / 2; i++) {
        if(n % i == 0) {
            return false;
        }
    }
    return true;
}

This works but is too slow: for the maximum input 1000000, this runs in 15.3 seconds on my machine.

The sieve of Eratosthenes

For large inputs, we're checking the same numbers for primality many times. It will be much more efficient to perform a calculation of the primes up to the input number upfront. The standard algorithm for this is the sieve of Eratosthenes:

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

std::vector<int> primes = {};

bool isPrime(int n) {
    return std::find(primes.begin(), primes.end(), n) != primes.end();
}

void sieve(int n) {
    bool flags[n + 1] = {0};
    for(int i = 2; i <= n; i++) {
        flags[i] = true;
    }
    for(int i = 2; i <= std::sqrt(n); i++) {
        if(flags[i]) {
            for(int j = i * i; j <= n; j += i) {
                flags[j] = false;
            }
        }
    }
    for(int i = 2; i <= n; i++) {
        if(flags[i]) {
            primes.push_back(i);
        }
    }
}

int main() {
    int i = 0;
    int n;
    std::cin >> n;
    sieve(n);
    while(n > 3) {
        for(int j : primes) {
            if(isPrime(n - j)) {
                n = n - j - j;
                i++;
                break; // out of for, not while
            }
        }
    }
    std::cout << i << std::endl;
    return 0;
}

This program (goldbachs-sieve.cpp) runs in 2.68 seconds on my machine. This is still rather slow. I'm not sure if it's good enough since I don't know what the time limit is for this problem, but this can easily be further optimized by storing the flags array from the sieve function for use in the isPrime function, thereby making isPrime run in O(1) rather than O(n):

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

std::vector<int> primes = {};
std::vector<bool> flags = {};

bool isPrime(int n) {
    return flags.at(n);
}

void sieve(int n) {
    flags.push_back(false); // 0
    flags.push_back(false); // 1
    for(int i = 2; i <= n; i++) {
        flags.push_back(true);
    }
    for(int i = 2; i <= std::sqrt(n); i++) {
        if(flags.at(i)) {
            for(int j = i * i; j <= n; j += i) {
                flags.at(j) = false;
            }
        }
    }
    for(int i = 2; i <= n; i++) {
        if(flags.at(i)) {
            primes.push_back(i);
        }
    }
}

int main() {
    int i = 0;
    int n;
    std::cin >> n;
    sieve(n);
    while(n > 3) {
        for(int j : primes) {
            if(isPrime(n - j)) {
                n = n - j - j;
                i++;
                break; // out of for, not while
            }
        }
    }
    std::cout << i << std::endl;
    return 0;
}

This program (goldbachs.cpp) runs in 12 ms on my machine, which is certainly fast enough.

I am fairly certain this solution is correct, but this problem is unavailable in any virtual judge at this time so I cannot verify this.

How does one sieve?

... is the question I asked when I read this problem at the competition in November. None of us could recall the algorithm for the sieve of Eratosthenes, and we had no internet access... but what we did have was a local copy of the official Python documentation.

This documentation is very useful as it contains a number of code samples that happen to include various algorithms. In the answer to the FAQ "Is it possible to write obfuscated one-liners in Python?", one can find a prime sieve:

from functools import reduce
# Primes < 1000
print(list(filter(None,map(lambda y:y*reduce(lambda x,y:x*y!=0,map(lambda x,y=y:y%x,range(2,int(pow(y,0.5)+1))),1),range(2,1000)))))

Rather than trying to unpack that intentionally complex code, we can simply incorporate it into a program (goldbachs-complete.py) practically unmodified:

from functools import reduce

def primes(x):
    return list(filter(None,map(lambda y:y*reduce(lambda x,y:x*y!=0,map(lambda x,y=y:y%x,range(2,int(pow(y,0.5)+1))),1),range(2,x))))

i = 0
n = int(input())

primeList = primes(n)
flags = []
for j in range(n):
    flags.append(False)
for j in primeList:
    flags[j] = True

def isPrime(x):
    return flags[x]

while n > 3:
    j = 2
    while j < n/2:
        if isPrime(n - j):
            n = n - j - j
            i += 1
            break
        j += 1

print(i)

Unfortunately, this program takes 2 minutes, 22 seconds to complete on my machine. I ported the above C++ program to Python (goldbachs-sieve.py) and found that it completed in 340 ms, so this sieve implementation (which I can't be bothered to analyze further) must be very inefficient. It was worth a shot.

Arena Survival

Another way of viewing the problem

The new arena is completely contained within the old arena, so its center must be at least R2 from the edge of the old arena. We want the probability that we are within the new arena—that is, the probability that our position is within R2 from the center of the new arena.

In the diagram below, the large black white circle is the old arena and the red dot is an example position. The blue dashed line and blue shaded area enclose all possible center points for the new arena; a sample new arena is shown in blue. We want the probability that a random point within the blue shaded area is also within radius R2 of our position; this radius is shown as a red dashed line and red shaded area. R₂ R₂ R₁ R₁ R₂

It is easy to see that we want the probability of the new arena center falling within the intersection of the red and blue dashed circles, and that the radius of the blue dashed circle (represented by the green dashed line) is R1R2. The probability of a random point in the blue dashed circle should be the area of this intersection divided by the area of the blue dashed circle. But how can we find the area of the intersection?

The formula for the area

We can find the distance between the center of the blue and red circles fairly easily. The blue circle is centered at (0, 0) and the red circle is centered at (X, Y), so the distance is d = X 2 + Y 2 .

The intersection of the two circles forms an asymmetric lens. You probably don't know the formula for the area of an asymmetric lens (or, indeed, the term asymmetric lens) off the top of your head. It is: A = r 2 cos -1 d 2 + r 2 - R 2 2 d r + R 2 cos -1 d 2 + R 2 - r 2 2 d R - 1 2 - d + r + R d + r - R d - r + R d + r + R

Note that it is possible for the red circle to fall entirely within the blue circle. In this case, the area of the intersection is simply the area of the inner circle. This case is easily detected as it occurs when d < R 2 .

If we know this, we can solve the problem (arena.cpp):

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

#ifndef M_PI
    #define M_PI 3.14159265358979323846264
#endif

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;

        double d = sqrt(x * x + y * y);
        double r, R;
        r = r2;
        R = r1 - r2;
        double A;
        if(d < R / 2.0) {
            A = M_PI * r * r;
        }
        else {
            A =
                r * r * acos(
                    (d * d + r * r - R * R)
                    / (2 * d * r)
                )
                + R * R * acos(
                    (d * d + R * R - r * r)
                    / (2 * d * R)
                )
                - 0.5 * sqrt(
                    (-1 * d + r + R)
                    * (d + r - R)
                    * (d - r + R)
                    * (d + r + R)
                );
        }
        double p = A / (M_PI * R * R);
        if(std::isnan(p) || p > 1.0) printf("1.00\n"); // fix for certain test cases with very large arenas
        else printf("%.2f\n", p);
    }
}

I am fairly certain this solution is correct, but this problem is unavailable in any virtual judge at this time so I cannot verify this.

Deriving this formula

Would a brute force solution work?

Unless you have this very document printed out, coming up with this formula during a competition is probably not going to happen.

We only have to report the probability to two decimal places. Could we simply check very many points where the new arena could be centered?

The circle containing possible center points for the new arena is obviously contained within the square with corners (−R2, R2) and (R2, −R2). So let's test a whole bunch of points in that square for containment in both circles: