Mapping a permutation to a number has attracted much social concern. In shortest-path problems, in case a node (or state) is a permutation, we should convert states to integers, in order to BFS or Dijkstra on new graph comfortably. Many coders have known using std::map or trie to do this work. However, both have certain disadvantages. My writing will introduce a new way to solve this problem.

It is hard to write both long and detailed blog. Therefore, you can comment anything which you didn't understand well. I will reply (or update this blog if it is necessary).

To understand the role of mapping a permutation to a number, consider problem POSLOZI from COCI. Our goal is to find the length of the shortest path from a permutation S to an other permutation T using allowed operations. A valid operation is swapping two elements in the permutation. We are given a list of pair (p, q) denote we can swap the element indexed p and the element indexed q. Any other swapping operations are not allowed. A possible strategy is to BFS simultaneously from both S and T.

.

I see lots of programmers write code like this one:

pair<int, int> p;
vector<int> v;
// ...
p = make_pair(3, 4);
v.push_back(4); v.push_back(5);

while you can just do this:

pair<int, int> p;
vector<int> v;
// ...
p = {3, 4};
v = {4, 5};

Hello 2015! Hello Codeforces!

It seems it is time to take stock. Frankly, I was almost feared to start summing statistics of 2014. In 2013 Codeforces showed rapid growth so that it would not be surprising to look bad on the background of 2013. Certainly not! I was pleasantly surprised by the statistics and reports!

Just below is a list of major events and achievements of Codeforces over the year. For you, it's just a list, but please note — every item includes hard work of multi-day Codeforces team, writers of problems, the organizers of contests and tournaments, problem testers and volunteers. Yay! Together we have done all of this:

• introduced Codeforces API
• added (and sometimes improved) all Andrew andrewzta Stankevich contests
• Codeforces supported mode to work as iframe-widget, and Codeforces helped Google to run https://www.calltocode.ie/ for Ireland high school children
• nearly 70 rounds have been hosted for our beloved users
• nearly 450 new and interesting problems were prepared for the contests on the Codeforces platform
• supported new programming languages
• together with CROC was held Coder-Strike 2014
• hosted April Fools Day Contest 2014 from magnificent Maria Nickolas Mykhailova

• together with the jury of Russian Code Cup 2014 held RCC Warmup, who opened the RCC for a wide range of Codeforces users
• Codeforces played a role of press-partner of RCC, ACM-ICPC Finals in Ekaterinburg, Yandex.Algorithm
• we held ZeptoLab Code Rush 2014 (Om Nomes!)
• helped wonderful company RocketFuel to run Rockethon 2014 (on Codeforces)
• hosted MemSQL Start [c] UP 2.0 with the finals the MemSQL office!
• had 11 episodes of Codeforces Trainings Season 02
• together with the jury Bayan Contest held Bayan Contest Warm Up
• updated Polygon (http://polygon.codeforces.com/) introducing an infinite number of small improvements
• supported tutorial in Polygon
• file system queries caching in Polygon has led to significant acceleration of most pages
• together with GridDynamics held GridGames (for Saratov university students)
• broke all records: 6274 registrations on Good Bye 2014!

In this cold January day, I send warm greetings to the Codeforces team and our friends: developers, problem coordinators, problem writers, testers, tireless bloggers and all of you — the knowledge-hungry competitors!

And here is a comparison with previous years of Codeforces. Clearly. In Pictures.

As you know, the C++ language assumes that the programmer is always correct. Therefore C++ compilers don't add additional checks to the program, such as checks for null pointer dereference or out-of-bounds array access. This is good, because C++ programs run as fast as possible, and this is bad, because sometimes we may spend a long time debugging some silly mistake. We would want that the compiler can find such mistakes automatically. And many compilers can! In this post I will show various GCC options that do this. Previously zakharvoit already wrote about this here.

All options that will follow should be added to the GCC command line. In various IDEs you can do it in IDE or compiler settings. Many of the options can also be used with Clang (for example, in Xcode). For MSVC++, I think, there is nothing better than Debug mode and /W4.

Recently magic item has been appeared in settings of a profile. Happy New Year!

UPD: New Year holidays are finishing, magic is disappearing... This year the magic features has been used 7482 times. Here are statistics about target handle colors.

Hurry! Only until the 10th of January, you can change your handle! Note that it will be possible to roll back the changes or change the handle again only after a year.

You can change your handle to the new one which wasn't used before by anybody or which was used by you before. Soon, the links like http://mirror.codeforces.com/profile/Alex_KPR would automatically redirect to the actual profile.

Talking about handles I always reminisce the following story. Once a user wrote me the message: "Please change my handle from I_love_Valya to I_love_Sveta, as I no longer love Valya ..."

Happy New Year!

Hey everbody.

Hello 2015 is a Div.1 + Div.2 contest that will be held in gym soon. As I said, there will be 2 divisions and in each divisions, users of that division can participate ( ( - ∞, 1699] and [1700, 9999]). So, anybody who participates in the wrong division will be out of competition (manually).

Duration is 3 hours and there will be 6 problems in each division. Last 4 problems of Div.2 will be same as first 4 problems of Div.1 . Problems are written by me (PrinceOfPersia) and tester's M.Mahdi.

The problems will be sorted according to the estimated order of difficulty according to my opinion but I strongly recommend you to read all of the problems.(sentence from matrix :D).

Problems are more Olympiad style than ACM. I hope you enjoy them.

It takes a while to prepare all problems. So, this contest is not in the gym contests list yet.

Oh, I almost forgot this : the main character of all problems will be my friend, De Prezer :)

UPD: Problems are designed for single participant (as mathlover said), so teams will participate out of competition too.

UPD2: It's in the gym contests list now.

UPD3: For making the contest more interesting, the winner of each division, gets a kiss ;)

UPD4: Round was delayed by 10 minutes for some technical reasons.

UPD5: Contest is over.

Congratulation to all winers specially sankear who solved all Div.1 problems.

Div.1 winners :

1.sankear

2.ikbal

3.kraskevich

4.tourist

5.dreamoon_love_AA

Div.2 winners :

1.cthbst

2.peterpan

3.que_roin

Now it's time to sankear and cthbst kiss each other ;)

See you in next rounds, good luck and have fun.

UPD6: Well, recently I'm a little busy and I'll just post some keywords and tags but maybe I'll write an editorial some time.

Div.2 A : Binary search, B : Partial sum

Div.1 A : Binary search, B : Dijkstra, C : DP,Two pointers,queue, D : 2-sat, E: Hash, Segment tree, F : Divide and Conquer.

UPD7: You can find the editorial here.

Hi, Codeforces!

Welcome to the last Codeforces Round of 2014, Good Bye 2014! This round is very unusual; First, the round starts at December 30th, 18:00 MSK. Second, the round lasts for 2.5 hours. And lastly, the round will be division combined, which means Div1 contestants and Div2 contestants won't be separated.

The problems are prepared by me (.o.) and Seunghyun Jo (ainta). This is our second round at Codeforces. Because our first round caused(?) the Black Day, we hope this round won't cause any errors like before :D

Thanks to Won-seok Yoo(ainu7), who tested our round and gave us comments about the problemset.

We'd like to thank some people who were necessary to make this round: Maxim Akhmedov (Zlobober) gave us great help preparing the problems. Maria Belova (Delinur) translated problem statements in Russian. Mike Mirzayanov (MikeMirzayanov) made Codeforces and Polygon systems, which are really great. Let's give them an applause!

The score distribution will be posted just before the round starts, as usual.

We wish you all the best of luck. Happy New Year!

UPD (2014-12-30 17:33:21) The score for each problem is going to be 500-1000-1000-1500-2750-2750-3500. Thanks to Xellos for giving us some ideas.

UPD (2014-12-31 12:49:05) Round has finished, congratulations to the winners!

1. tourist
2. Petr
3. rng_58
4. HYPERHYPERHYPERCUBELOVER
5. subscriber
6. Merkurev
7. al13n
8. mmaxio
9. mexmans
10. GlebsHP

Also, thanks to Marcin_smu, who solved problem G after the contest for the first time.

UPD(2014-12-31 12:51:08) Editorial is published. Currently, only A-F is available, but I will add G as soon as possible. Sorry for the late editorial.

UPD(2015-01-02 21:30:44) I wrote the editorial of G. Sorry for the late update..

Note that schedule have been changed for a New Year contest Good Bye 2014. Round starts at December 30th, 18:00 MSK and lasts for 2 hours 30 minutes. It will also be division combined.

Wait for an announcement for further details. New Year is coming!