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://mirror.codeforces.com/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.

Howdy Codeforces!

Come join us for a trip to Bovinia with everyone’s favorite munchkin Kevin Sun (ksun48) and his sidekick Nicky Sun (nsun48)! Codeforces Round #334 (for both divisions) will be taking place on December 1st, at 6:35pm MSK. The problems were written by Alex Wei (yummy), Michael Kural (pi37), and myself, Yang Liu. As proud Americans, we’ve themed all of our statements around the most glorious cow (and its many uses in life).

We are immensely grateful to GlebsHP for his guidance and suggestions, without whom we would not have a balanced problem set. In addition, we would like to thank MikeMirzayanov for creating Codeforces and Polygon, as well as Delinur for translating our problem statements to Russian. Finally, we would like to give a huge shoutout to Daniel Chiu (waterfalls), Kevin Sun (ksun48), Nicky Sun (nsun48), Weihang (Frank) Fan (pobelter), Ray Li (abacadaea), and Girishvar Venkat (numbertheorist17) for testing our problems and providing feedback.

We wish you good luck and hope you enjoy our problems and cow jokes. (We’ve milked our brains quite thoroughly for puns.) Come hop on the next cattlebruiser for Bovinia!

(Per Codeforces tradition, we will announce the score distribution just before the contest.)

UPD 1: Some added thanks to AlexFetisov and winger for also testing our problems.

UPD 2: The scoring will be standard (500-1000-1500-2000-2500) for Div 2 and 500-1000-1500-2000-3000 for Div 1. Good luck and have fun!

UPD 3: System testing is done! Congrats to the winners.

Division 1:

1. subscriber
2. rng_58
3. Zlobober
4. ecnerwala
5. FreeMoneyCity

Division 2:

1. matipau
2. geniucos
3. quasisphere
4. emppu
5. tranquility

UPD 4: The editorial is posted here.

Hope everyone enjoyed the contest! Comments about problem quality, etc. are also appreciated.

Now I am writing an article about bit manipulation, bit magic and other trciks for wiki — conspects (This is a great resource of algorithms in Russian). If you know some useful bit tricks, which used in algoritms or just funny things connected with bits write them in comments below. Also you are welcomed with really strange, weird and sophisticated solutions for well-known problems. For example: swapping values with XOR.

Good style for your comments:

• Descripotion of the problem
• Solution of the problem in code with short explanation for tricky moments

Example of a perfect comment:
Determining if an integer is a power of 2

unsigned int v; // we want to see if v is a power of 2
bool f;         // the result goes here 

f = (v & (v - 1)) == 0;

Short explanation: Let v — power of two (this is one and k zeros in binary presentation) and v — 1 is k ones in binary presenation. Then notice that bitwise AND v and v — 1 must be 0.

Warm — up problem: Find smallest 1 — bit (not zero) in O(1)

Hi, Codeforces!

Educational Codeforces Round 2 will take place on November 27th, 2015, at 15:00 UTC for the first and second divisions. You can read about educational rounds here.

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.

Round was prepared by me, Edvard Davtyan. Problems was invented by me and MikeMirzayanov.

I hope you will enjoy the problems.

Good luck and have fun!

UPD: Thanks a lot to PrinceOfPersia for testing the problems and Delinur for checking my bad English (in problem statements).

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

UPD3: At the stage of hacking we found that a lot of correct solutions are numerically unstable, so they print the right answer with error in ninth digit. So we decided to increase the requirement for precision from 10^- 9 to 10^- 6. All submissions and hacks will be rejudged soon. It will not affect correct solutions. They will got Accepted as earlier.

UPD4: The editorial is ready.

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