Will it be live or re-run of the onsite contest?

In Codeforces #87 Div1 problem B I wrote this struct:

struct st {
    int i, j, d, c;
    st() {
    }
    st(int ii, int jj, int dd, int cc) {
        i = ii;
        j = jj;
        d = dd;
        c = cc;
    }
    bool operator <(const st &s) const {
        return c <= s.c;
    }
};

As you see in the less than operator I used <= instead of < (mistakenly), and after I submitted my solution I saw this bug. And I made a multiset<st>, so this operator may say that x<y and y<x, I thought this will get RTE or WA, but I tested it and I didn't get any RTE or WA, so I decided to take the risk of not to resubmit the problem. And now my solution is accepted, but I don't know what is the behavior of this operator, can anyone explain it to me?

Thanks!

This is my approach for this problem, and I don't know why it's wrong.

I don't know which criteria is used to select the problems difficulty. In round 78 DIV 1, almost the last 4 problems were solved by the same number of coders which is about 20 coders, and the first problem was solved by about 200 coders. These numbers don't make sense at all. Also this is not the only contest with this situation, it happened in many contests which was much harder than expected.

I think this is a mistake, as the next round's number is 75 as the last one.

Hi everyone,

Here are some notes about GCJ tools website during round 1A:

1- 191,538 database queries were executed during the contest.
2- The final result for this round is available now.
3- The live scoreboard had some bugs during the contest, but everything is fixed now.
4- I spent more than half of the contest debugging and fixing bugs in the live scoreboard.
5- The whole scoreboard was updated 839 times during the contest.
6- The average time for each single update was 10 seconds.

--

My Codeforces graph: http://www.codeforces.com/profile/ahmed_aly
My TopCoder graph: http://www.topcoder.com/tc?module=MemberProfile&cr=22707682

Can you see how my graphs are similar in the last few contests?
Is there anyone else with such similar graphs?

1- Codeforces contests now are more stable than TopCoder contests, there were about 2200 registrants today (not all of them participated) and the contest ran smoothly (at least for me).

2- I like Codeforces contest format more than TopCoder contest format, the contest contains more problems and more time, and I like Codeforces hacking more than TopCoder challenges.

3- Codeforces now makes much more contests than TopCoder.

4- I like Codeforces problems quality and difficulty levels more than TopCoder.


Now Codeforces is number 1 for me and TopCoder is number 2, I love Codeforces.

I've noticed in the last few Codeforces contests that almost all problem statements are very long and contain a lot of useless parts.
For example in this problem, the first 4 paragraphs are completely useless, which is about 40% of the problem description.
I don't see any fun in reading a lot of useless parts, and I used to read and understand everything carefully because it could contain something important.
Why should I waste the contest time in reading and understanding useless parts?
I wish to see smaller and more direct description in the next contests.

What do you think about this?

Problem A:
In this problem you need to do what is written in the statement. You can do it in the following 3 steps:
1- Calculate C.
2- Remove all zeros from A, B and C.
3- Check if the new values form a correct equation.

C++ solution for problem A.


Problem B:
This problem is a direct simulation to the rules written in the problem statement.
You need to iterate over all actions and parse each one to know the type of the action, and the 2 names X and Y, and if your name is X or Y then update your priority factor with this person with the action corresponding value. And take care about some special names like "post", "wall", "commented" and "on".
Then sort all names according to the sorting criteria mentioned in the statement.
Just make sure to print all names which are mentioned in the input (excluding yourself), even if the priority factor with you is 0.

C++ solution for problem B.


Problem C:
In this problem you will need to generate all common divisors between a and b before answering any query.
The first step in this problem is to factorize a and b, you can use the trial division technique which runs in O(sqrt(N)), you can check getFactors function in my solutions.
Then using a recursive function you can generate all divisors for a and b from their prime factors, you can check getDivisors function in my solutions.
Then intersect the 2 sets of divisors for both to get all common divisors, you can do this in O(N+M) where N and M are the lengths of the 2 sets, and also you can do a trivial O(N*M) intersection algorithm, because the maximum number of divisors is not too big (it's 1344).
Now for each query you need to find the largest common divisor which lies in the given range, you can do this by sorting all common divisors and do binary search for the largest one which lies in the given range. Also you can do this using linear search, because the total number of queries is not too big.

Also there is much shorter solution for this problem. Here is a hint for it, the GCD between a and b should be dividable by all common divisors of a and b.

C++ solution for problem C (with binary search).
C++ solution for problem C (without binary search).
Java solution for problem C (with binary search).


Problem D:
This problem is my favorite one in this problem set. Maybe it will be easier to solve this problem if you know how to solve the standard one.
But because we can't construct the big array, so we can't apply the standard solution for this problem.
Let's see first how to solve the standard problem, the following code solves it for a given array arr with length len:

int mx = -(1 << 30);
int sum = 0;
for (int j = 0; j < len; j++) {
    mx = max(mx, arr[i]); // we need this for the case where all elements in the array are negatives
    sum += arr[i];
    if (sum < 0)
        sum = 0;
    else
        mx = max(mx, sum);
}

Now let's solve the big array problem, the first step is to calculate 4 values for each small array:
1- The total sum of it, let's call it tot.
2- The maximum sum of 0 or more consecutive elements starting from the first element in the array, let's call it lft.
3- The maximum sum of 0 or more consecutive elements ending at the last element in the array, let's call it rght.
4- The maximum sum of 1 or more consecutive elements, let's call it gen.

The final result will be 1 of 2 cases:
1- The consecutive elements with the maximum sum will start and end inside the same small array.
2- The consecutive elements with the maximum sum will start and end inside different small arrays.

For the first case, we can simply pick the maximum gen for all small arrays which exist in the big array.
For the second case, we can apply something similar to the standard solution, we will keep a variable called sum, and it's initialized to 0, this will be the maximum sum of 0 or more consecutive elements ending at the last element in the previous small array. Now for each small array, if the maximum possible sum will end in this small array, so it will be sum+lft and maximize over this value (make sure this will be for 1 or more elements). And we need to update sum to be the maximum of the following 3 values:
1- sum+tot (we will include all elements of this small array to the old sum).
2- rght (we will take the maximum sum ending at the last element in the current small array).
3- 0 (we will not take any elements in sum).

The running time for this solution will be just for reading the input, in my solutions I have no iterations except for reading the input.

You can check my solutions for more clarification.

C++ solution for problem D.
Java solution for problem D.


Problem E:
The main idea for this problem is not hard, but maybe the hard part is implementing it.
First we need to know if the straight line segment between the source and destination points intersect with the island or not. So we will intersect this line segment with all the polygon sides. If there are 2 segments intersect in more than 1 point we will consider as they don't intersect, because it's mentioned in the problem statement that you can move on the island's edge and it will be considered in the sea.
Now we have a set of all distinct intersection points of the polygon and the straight line segment between the source and destination points. Because the polygon is convex, this set will contain at most 2 points. We have 3 different cases now:
1- This set contains less than 2 points.
2- This set contains 2 points and they are on the same polygon side.
3- This set contains 2 points and they are not on the same polygon side.

In the first 2 cases the result will be simply the length of the straight line segment.
In the 3rd case you can do the following:
1- Move from the source point to the nearest point of the 2 intersection points.
2- You have 3 options here:
    a- Move inside the island to the other intersection point.
    b- Move in clockwise direction on the island's edge to the other intersection point.
    c- Move in anti-clockwise direction on the island's edge to the other intersection point.
    First option will be considered moving inside the island, and the other 2 options will be considered moving in the sea.
    You should pick the minimum one.
3- Move from the 2nd intersection point to the destination point.

Another solution:
You can construct a graph where the nodes are the source point, the destination point, the intersection points and the polygon corner points. Then add an edge between any 2 points which you can move between them with the corresponding cost. Then run any shortest path algorithm, Floyd Warshall for example.

You can check my solutions for more clarification.

C++ solution for problem E.
C++ solution for problem E (with Floyd Warshall).

Hi everyone,

Today I'll be the author for this round, and it's my first time to be an author in Codeforces. I hope you will like the problems and find it interesting, even for Div1 coders.

I would like to say thanks for Artem Rakhov for solving and testing the problems, for Maria Belova for preparing the problem statements, and for Mike Mirzayanov for this great system.

Good luck and have fun.

Edit 1: Congratulation to the winner Chubcheg.
Edit 2: The problem editorial is here.

Will we have just 1 contest in April?

Hi everyone,

Finally I did it, now you can filter Codeforces users by country.
Just go to this page and select the country and click view table.

I found that many Codeforces users didn't write a country in their profile,
but I have a TopCoder Tools website and I have all TopCoders countries in my database,
and I assumed that many users have the same usernames in TopCoder and Codeforces.
So if the country is unknown for a Codeforces user and I found a TopCoder account with the same username,
I assigned the TopCoder country to this Codeforces user.
I know that this way could assign someone the wrong country, but it will happen with low probability.
Also I got the country using this way for 1318 Codeforces users with unknown country, which I think it's very good number.

If you have just added or changed your country, you can go to this page, and write your username and click update my country, and it will be updated in my database too.
You don't need to enter your country in my website, just update it in Codeforces and do the above steps.

Anyway, if you found that your country is selected incorrectly, please send a message to me and I'll fix it.

I hope that you will find this useful.

I see that I have to choose if my comment is in English or Russian, and the Russian comments (or maybe the comments posted from the Russian website version) don't appear in the English version. And it happens that some Russians write a comment in English but mistakenly select Russian for the language.

I agree that the Russian comments shouldn't appear in the English version, but I could miss an English comment because it was mistakenly posted as Russian.

I think we don't need to choose if the comment is in English or Russian, as it can be detected automatically if it's English or Russian. A simple way to do this is to check if the comment contains any Russian letter which does not exist in English (I don't understand Russian, but I think there are many such letters).

Edit: Now I see that if you are writing a comment in the Russian version you can't choose English for the language, it's Russian by default and you can't change it.

Hi everyone,

I've just finished the first Codeforces tools website, currently it contains only one feature called all users table.
This table is similar to Codeforces rating table, but with this additional columns:
- Number of Tried Problems
- Number of Solved Problems
- Solved Problems Percentage
- Number of Successful Hacks
- Number of Unsuccessful Hacks
- Contribution Rank
- Contribution

Also you can sort the table according to any column by clicking on the column header, it may take couple of seconds to sort the table as it's very big, also it may take few seconds to load the table.
There are some important notes in the home page, make sure to check it.

Keep checking this main post to see the new added features.

I'll add the following features:
- Add filtering for the all users table.
- Adding profile page for each user, which contains links for all problems he solved.
- Adding some statistics for each user, for example the languages he used to solved the problem, his average number of solved problems per contest, how many times he solved a problem for each level, and more information.
- The ability to compare to users, by merging their graphs together, or counting how many number solved by one of them while the other one failed to solve it.

If you have any suggestion or a feature you wish, feel free to ask for it in this post, and I'll do my best to make all requested features (if I can).

Hope you will find it useful.

Thanks!

Will Manthan 2011 affect the Codeforces rating?

I won't participate in next Codeforces round, becuase I'll be married just 1 hour before the contest. :)
Also I think many Egyptian coders won't participate in it because they will be attending my wedding.

In Codeforces round 56 there were 1193 registrants, which is new max number of registrants.
And the site didn't go down during the contest, well done Codeforces team. :)

When is the next contest?