Hello.

Now you do not have to go into Google if you need to search blog posts. You can do it directly on Codeforces. The implemented search is based on Apache Lucene . The index contains all open public posts, which are already more than 15,000 documents.

Temporarily search for tags are now available (tags will be added to the index soon), but instead you have the opportunity to find posts and even sort using different criteria. By the way, you can use complete syntax of Lucene queries to search. Here is a short description of main features.

You can use several words in query to find by all of them at the same time. In addition, if you are lucky search understands word forms and some synonyms. It supports search by title and author.

Some examples:

• 305 — search for 305, most probably it will find blogs about the Round 305
• andrew stankevich contests — search for words "andrew", "stankevich" and "contests" at the same time
• user:mikemirzayanov title:testlib — search containing "testlib" in title by MikeMirzayanov
• "vk cup" — use quotes to find phrase as is
• title:educational search in title

Regarding indexing comments, solutions and problem statements I have a feeling that it may be useless. Too difficult to find something relevant (or maybe not). What do you think: should we implement it?

Greetings! CodeForces Round #336 welcomes both divisions this Wednesday, December 23, 2015 at 16:35:00 UTC. The round is authored by me, Amor727, Chilli, and GlebsHP. We hope you'll like the problems. Scoring and score distribution: Not Dynamic; Div1: 500 — 1250 — 1500 — 2000 — 3000; Div2: 500 — 1000 — 1500 — 2250 — 2500

Much thanks to Amor727 and Chilli for writing and editing problems, GlebsHP for organizing the competition and for his very helpful attitude, Delinur for translations, winger for testing, Marina Kruglikova for statement fixes, and MikeMirzayanov for his amazing CF and Polygon platforms.

During this contest you will be assisting Genos from the series One Punch Man. His master Saitama will also make some appearances. We wish everyone good luck and high rating in assisting the two. From the contest crew and the two fellows below, happy holidays!

Congratulations to the winners:

Division 1:

1. matthew99

2. tourist

3. ACRush

4. jqdai0815

Division 2:

1. Hansuzu

2. ajjack999888

3. platypus179

4. Petru

5. Mihaell

Editorial of round: /blog/entry/22256

It's always a hassle to define our 2D Geometry library during a contest. Is there a way to make our computational geometry lives easier in any way? Fortunately for us, there is, at least in C++, using complex numbers.

Complex numbers are of the form a + bi, where a is the real part and b imaginary. Thus, we can let a be the x-coordinate and b be the y-coordinate. Whelp, complex numbers can be represented as 2D vectors! Therefore, we can use complex numbers to define a point instead of defining the class ourselves. You can look at std::complex reference here.

Defining our point class

We can define our point class by typing typedef complex<double> point; at the start of our program. To access our x- and y-coordinates, we can macro the real() and imag() functions by using #define. Of course, don't forget to #include <complex> before anything.

#include <iostream>
#include <complex>
using namespace std;

// define x, y as real(), imag()
typedef complex<double> point;
#define x real()
#define y imag()

// sample program
int main() {
	point a = 2;
	point b(3, 7);
	cout << a << ' ' << b << endl; // (2, 0) (3, 7)
	cout << a + b << endl;         // (5, 7)
}

Oh goodie! We can use std:cout for debugging! We can also add points as vectors without having to define operator+. Nifty. And apparently, we can overall add points, subtract points, do scalar multiplication without defining any operator. Very nifty indeed.

Example

point a(3, 2), b(2, -7);

// vector addition and subtraction
cout << a + b << endl;   // (5,-5)
cout << a - b << endl;   // (1,9)

// scalar multiplication
cout << 3.0 * a << endl; // (9,6)
cout << a / 5.0 << endl; // (0.6,0.4)

Functions using std::complex

What else can we do with complex numbers? Well, there's a lot that is really easy to code.

1. Vector addition: a + b

2. Scalar multiplication: r * a

3. Dot product: (conj(a) * b).x

4. Cross product: (conj(a) * b).y
   
   notice: conj(a) * b = (ax*bx + ay*by) + i (ax*by — ay*bx)

5. Squared distance: norm(a - b)

6. Euclidean distance: abs(a - b)

7. Angle of elevation: arg(b - a)

8. Slope of line (a, b): tan(arg(b - a))

9. Polar to cartesian: polar(r, theta)

10. Cartesian to polar: point(abs(p), arg(p))

11. Rotation about the origin: a * polar(1.0, theta)

12. Rotation about pivot p: (a-p) * polar(1.0, theta) + p
    
    UPD: added more useful functions

13. Angle ABC: abs(remainder(arg(a-b) - arg(c-b), 2.0 * M_PI))
    
    remainder normalizes the angle to be between [-PI, PI]. Thus, we can get the positive non-reflex angle by taking its abs value.

14. Project p onto vector v: v * dot(p, v) / norm(v);

15. Project p onto line (a, b): a + (b - a) * dot(p - a, b - a) / norm(b - a)

16. Reflect p across line (a, b): a + conj((p - a) / (b - a)) * (b - a)

17. Intersection of line (a, b) and (p, q):

point intersection(point a, point b, point p, point q) {
  double c1 = cross(p - a, b - a), c2 = cross(q - a, b - a);
  return (c1 * q - c2 * p) / (c1 - c2); // undefined if parallel
}

Drawbacks

Using std::complex is very advantageous, but it has one disadvantage: you can't use std::cin or scanf. Also, if we macro x and y, we can't use them as variables. But that's rather minor, don't you think?

EDIT: Credits to Zlobober for pointing out that std::complex has issues with integral data types. The library will work for simple arithmetic like vector addition and such, but not for polar or abs. It will compile but there will be some errors in correctness! The tip then is to rely on the library only if you're using floating point data all throughout.

Hi, Codeforces!

Educational Codeforces Round 3 will take place on 19 December 2015 at 18:00 MSK for the first and second divisions. You can read about educational rounds here and here. A lot of time have passed since the previous round. I hope that the next rounds will be more regular.

<This paragraph wasn't changed>

The round will be unrated for all users and it will be held with extented ACM ICPC rules. You will have two hours to solve six problems. After that you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

</This paragraph wasn't changed>

This time the round was prepared not only by me, Edvard Davtyan. Firstly, thanks a lot to Alexey Dergunov dalex who shared one of his problems with well-known idea. Also thanks a lot to Alexandr Frolov fcspartakm, Vitaliy Kudasov kuviman and Arthur Svechnikov ikar for their help in preparing problems. MikeMirzayanov helped us to invent the problems. Also thanks a lot to Maria Belova Delinur for translating the problems from my RussianEnglish to English :-)

I hope you will enjoy the problems.

Good luck and have fun!

UPD1: The first part of competition is over. I hope that you enjoyed the problems. Now you let's hack other solutions :-)

UPD2: The editorial is ready.

UPD3: The round is over. All solutions are rejudged on full testset. The results are final.

UPD4: 6725 rows affected :-)

With many regionals around the world finished, I think it is time to start collecting teams that are going to World Final this year. Please help me adding information to the tables :)

Europe

Asia

Latin America

Africa & the Middle East

North America

South Pacific

Hi all!

On Wednesday 9th of December at 19 MSK there will be CF Round #335 (div 1 + div 2) on problems made by me and dalex. Let's play it!

We thank GlebsHP for his help in preparing the problems, Delinur for English translations and MikeMirzayanov for the Codeforces itself.

Scoring system and score distribution will be published when the round starts. Anyway this information makes no sense until the round begins.

Wish you accepted solutions and successful hacks!

UPD. Congratulations to the winners in Div. 2:

weiszago

Invisble

nezametdinov

and in Div. 1:

jqdai0815

Um_nik

Egor

This is the problem analysis: blog/entry/22019.

Hello,

We are launching new feature on Codeforces, in early beta mode. I hope it will be useful to many active users of the web-site. Now you can create, manage and use the "user lists".

Partially, it is a kind of generalization of "friends." You can create a list of users interesting to you (you can create many lists) and, using the list, filter the results of rounds, quickly analyze what problems are solved in the problemset, etc. This feature is a helpful tool for coaching — I'm using it. By combining in a list of all practicing students, it is easy to pick up problems that have not been solved (and even not attempted) by any student.

A user list has name and a pair of two relatively secret keys & mdash; one for view/usage and one for editing. For example, here is the key to view a list of ACM-ICPC students at Saratov State U for autumn of 2015: 15c68c2cf878267d59373d1e56be8c9a

This means that on some pages, you can use the optional parameter ?list=key to apply the list. Here is an example of the screen by the link http://codeforces.net/problemset/page/3?list=15c68c2cf878267d59373d1e56be8c9a:

Yeah, in the recent training I can give the problems 538H - Summer Dichotomy and 538G - Berserk Robot . In additional information the first number indicates the number of users solved problem, and the second is the number users attempted problem. Codeforces searches solutions/attempts not only for this particular problem, but all the possibilities of its use (say, someone can solve it in other division or in a mashup).

There are additional controls to make it more comfortable to use lists:

At the moment, the lists can be applied:

• in the problemset (shown number of solvers/attempters for each problem)
• in list of rounds/trainings in Gym (shown number of solvers/attempters for each problem)
• on the standings page (to filter the rows)

I remind you that the functionality is in early beta mode & mdash; there may be some issues. We will return to development and bug fixing after ACM-ICPC Regional Contest NEERC 2015.

And what other use of the lists can offer you?

Consider a well-known problem: given a static array of size n, answer m queries of kind "how many numbers on [l, r] have value less than x". The standard solution is to build a segment tree where in every node we store a sorted vector. To answer a query we do a binary search in every corresponding node, achieving per query time complexity.

There is a method to reduce time complexity to per query, called fractional cascading. Instead of doing binary search in each node we do it only in the root, and then "push" its result to children in O(1).

For years I thought that the second approach is blazingly faster than the first one. And today I've made a test. I implemented both approaches in a pretty straightforward way and tested them on a random data. The results were quite surprising.

Fractional cascading: 760 ms

Top-down implementation: 670 ms

Bottom-up implementation: 520 ms

The first one is , others are ! Time is averaged over several consecutive runs. Test data is generated randomly with n = 100000, m = 200000.

Why doesn't fractional cascading give any improvements? Am I implementing it in an improper way? Anyway, this might be worth taking a look.