You don't read books like these, you study them.

Ten pages in one reading sounds fine, possibly too much. You're supposed to do the exercises as well, not only read the theory, only then you can claim you've understood the stuff.

It's better to have with your own questions before you start reading. (Like "I wonder what's the reasoning behind using red-black trees for C++ STL maps and sets, can the Cormen's book answer that?" and "What's the best data structure to use in this problem I have?") That typically gives me motivation to try to understand the technical material.

It's also important to select the right level of the book and the right approach: some people like more theoretical approach, while others (like me) are more into practical, applied stuff like "how to create computer games". This is completely subjective; you need to pick what you personally find interesting and compelling.

The approach is broadly correct. I just implemented it to test: 15667843. However:

1. it's not enough to sort just by x (or y) coordinate; points that have the same x coordinate should be sorted by y coordinate (x, respectively).

2. points can be on the same line that is neither horizontal nor vertical; this case should be recognized and skipped.

it is better to use marge sort.

Umm, no, it's better to use quicksort. Proof — this text from Skienna, Algorithm Design Manual:

"What we can say is that experiments show that where a properly implemented quicksort is implemented well, it is typically 2-3 times faster than mergesort or heapsort. The primary reason is that the operations in the innermost loop are simpler."

Basically quicksort has better cache locality. Most C++ standard library implementations use a combination of quicksort and insertion sort as their implementation for std::sort.

Looks like someone went through the trouble to generate an extremely bad test case input for hacking 620C - Pearls in a Row. Now the hack is included in the system tests as Test 42. It causes a huge number of collisions in that specific G++ implementation of unordered map.

• a submission with unordered_map fails with TL: 15496737
• a submission with map gets AC (only one line of code changed!): 15496747
• a submission with unordered_map and custom hash function: AC again! 15497036. Bit slower compared to map, anyway.

To the OP: good idea to change the max load factor! Looks like a simple solution compared to writing a custom hash function.

Tweaking the load factor + pre-creating many buckets (with reserve) solves the problem because you only get bad performance when there are many items per bucket. The worst-case is when all items are in a single bucket: then lookup in the hash map is reduced to list lookup.

In problem C:

• a submission with unordered_map fails with TL: 15496737

• a submission with map gets AC (only one line of code changed!): 15496747

• a submission with unordered_map and custom hash function: AC again! 15497036. Bit slower compared to map, anyway.

What exactly is test 42? Looks like someone went through the trouble to generated an extremely bad test case input that causes huge number of collisions in that specific G++ implementation of unordered map. In my opinion, it's a bit against the spirit of the competition ;)

Check out contest #472, it's a kind of problem setting tutorial. Each problem in it has a different source of inspiration, as you can see from their names and descriptions.

See my answer to masterwayne

Here are some hints: http://math.stackexchange.com/questions/266569/how-to-find-the-root-of-permutation

The answer still may be too advanced to understand if haven't studied the math of permutation groups. Basically, every permutation can be expressed in a cyclic notation. To do that, first write the permutation as multiplication of transpositions (a transposition is a cycles with two elements). For the example q = [4, 5, 1, 2, 3], 1 maps to 4, 2 to 5 and so on, so we write it down:

q = (1 4)(2 5)(3 1)(4 2)(5 3)

Now some transpositions can be merged. In fact in this example all of them can be merged, but that will not always be the case:

q = (1 4 2)(2 5)(3 1)(5 3) = (1 4 2 5)(3 1)(5 3) = (1 4 2 5 3)(3 1) = (1 4 2 5 3)

The resulting cycle of length 5 denotes the same original permutation q, just in a different way.

Now if q=(i1, i2, i3, i4, i5) then in q^2 element i2 moves one step away from i1: q^2=(i1, ..., i2, ...), element i3 one step away from i2 and so on (modulo the size of the permutation): q^2=(i1, i4, i2, i5, i3)

In the example, q^2 = (1 4 2 5 3)^2 = (1 2 3 4 5). Written back in the original form, it is the permutation p = [2 3 4 5 1].

The analysis so far works for cycles with odd length. For a cycle with even length l, for example p = (i1, i2, i3, i4) element i_n-2 maps back to i1 and so on; the result in this case is two cycles with length l/2: p = (i1 i3)(i2 i4)

To solve the exercise, you need to do the opposite: permute every odd-sized cycle back, and merge every pair of same-sized even cycles. (If there are more than one pair of cycles with size 2n, then multiple solutions exist.) If there are even-sized cycles with no pair, then a solution does not exist.

Finding the cycles in the given permutation requires some preprocessing, but it can be done in O(n) time.

Standard name lookup rules apply to your example. It compiles for the same reason why the next example compiles — because the inner scope is always looked up first unless the :: operator is used:

int i = 1;
int main() {
  long i = 2;
  cout << i << " " << ::i << endl;
}

And the other way around: trying to define a variable and a type in the same scope with the same name leads to an error.

typedef long long i64;
int i64 = 1; // <- error

One clear practical difference is that names introduced by #define cannot be used in other contexts in the program. For example:

#define LL long long int 
void foo(void) {
  int LL = 13; // <- compilation error here
}

You can post a link to you submission. When looking at your profile history, I see the submission history anyway.

Your I/O is too slow. There has been written a lot about cout/cin vs. scanf/printf on Codeforces, just search.

First, do not use endl after every line — it flushes the output buffers, therefore is slow.

Second, add this code at start of main():

    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

Then try again and it should be AC.

Internally map, multimap, set, and multiset all use the same implementation (which is a red-black tree for the STL library shipped with GNU C++). As misof suggests, most likely you're seeing a difference because you're comparing apples with oranges, i.e., map and set being used differently.

Auto comment: topic has been updated by kfx (previous revision, new revision, compare).

Was problem C so difficult to get right because it required to use long double? Changed mine solution from double to long double and got AC: http://codeforces.me/contest/598/submission/14258763