The following C++ program is supposed to report the sum and the squared sum of the 16 numbers hard-coded in the program.  The sum is correct but the squared sum is incorrect.  Can you see the typo?

This typo is taken from a program which I wrote for a report about ten years ago when I was an undergraduate student.  The actual program did something more complicated, but the essence of the typo was the same as the one shown here.

> cat sum.cc
#include <stdio.h>

int main()
{
    static const double data[16] = {
        -8.0,  3.5,  4.0, -2.5,
         3.0,  0.5,  1.5, -6.0
        -1.5,  2.0, -2.5,  4.5,
         3.0, -7.0,  5.0, -1.0
    };

    double s = 0.0;
    double s2 = 0.0;
    for (int i = 0; i < 16; ++i)
    {
        s += data[i];
        s2 += data[i] * data[i];
    }
    printf("sum = %f, sum of squares = %f\n", s, s2);
    return 0;
}
> g++ -Wall -o sum sum.cc
> ./sum
sum = -1.500000, sum of squares = 280.750000

The official solution for CodeFest Manthan 2011 Problem E “Save the City!” first computes the range in the edge in question from where each vertex is visible, and then computes the intersection of these ranges.  All these ranges can be computed in linear time in total as stated in the solution.  Although this algorithm is useful in some contexts, it is overkill for this problem.  In this post, I will explain a simpler algorithm.

The algorithm is based on the following fact (Figure 1).

Fact.  Let v₀,…,v_n−1, v_n=v₀ be the vertices of an n-gon P in the counterclockwise order, and x be a point on the edge v₀v₁.  The whole polygon P is visible from x if and only if for every i=1,…,n−1, the point x is either on the line v_iv_i+1 or on the left of the line v_iv_i+1.


Figure 1

In Manthan 2011 Problem A, I first wrote a C++ code which did not compile, and it took me one minute to figure out why it did not.  I proudly declare that I am a C++ newbie.  The following is the relevant part of the code.

for (int i = 0; i < n - 1; ++i)
{
    case (order[i])
    {
    switch 'R':
        lr[i + 1] = lr[i] + 1;
        break;
    switch '=':
        lr[i + 1] = lr[i];
        break;
    switch 'L':
        lr[i + 1] = 1;
        break;
    }
}

When searching blog posts, apparently tags containing spaces cannot be used.  For example, the result of feature request is:

You are finding: "feature request"
No items matched

CodeFest Manthan 2011 was my first competition on Codeforces, and I enjoyed it a lot.  Thank you very much to the organizers of both Codeforces and CodeFest.

Here are two feature requests on the system of Codeforces from the viewpoint of a newcomer.

First, the most important request is: let us practice locking a problem and hacking solutions!  (If it is possible with the current system, please let me know.)  Hacking competitors’ solutions is an essential part of the competition system of Codeforces, and it is important to learn and practice the steps to do it.  Ideally, it should work during practice just as in real contests except that (a) one solution can be hacked successfully more than once and (b) a user can “unlock” a problem.

The second request is less important than the first, but: the test cases used in the past contests can be presented better.  In particular, the test cases submitted in both successful and unsuccessful hacking attempts should be available (after contests, of course) because they will be valuable information to learn how to create good test cases for hacking.   (Edited: see below.)  In addition, some test cases in the system test are not shown in full; for example, try opening any correct solution to Problem A in Manthan 2011 and look at Test #6.

Hope this helps.

Edit: I learned that the inputs in hacking attempts in past contests are available on the website: choose Contests → (choose the Enter link for a contest) → Hacks.