Maybe there are bugs on lines 25 and 26.

Do you remember the rule "but a player cannot enter the game, and then exit in the same moment, or vice versa"?

Maybe you could try to think what happens if you just construct the partitioning node by node?

Does Kate still have that bug where the direction of the written text suddenly changes? :)

Lol, I participated IOI 4 times and never had a girl as a guide. Maybe like 3/4 of the guides are girls and (1/4)^4 is about 0,004... Am I cursed or what??? :D

Does anyone know how to solve this: http://wcipeg.com/problem/noi08p3 ?

My linear programming solution passes but I don't think it's the "correct" solution...

It is also worth noticing that time limits are the same as in the competitions but the judge hardware is not. Therefore it might be harder to get 100 points than in the real competition.

It's quite time consuming to read someone else's code... I suggest you code some brute force solution, generate many small test cases and compare the outputs.

Stack limit is 8MB, the linux default.

Seriously?...

Also perhaps I didn't notice but it would be nice to be able to upload the code instead of copy-pasteing it to the editor.

Wish you all beautiful, successful and receive many flowers from guys today :D

>beautiful

>flowers

Hmm... Brings back memories from IOI 2015. Girls were asked to come to the stage and they were given some flowers...

*triggered*

I'm sure the intention of this blog was good but I think it's not the best idea to always associate girls with things like beautifulness and flowers. And don't get me wrong, it's of course OK to say to a girl that she is beautiful and give her flowers. What I mean is that things are different when you are referring to a group.

Don't judge me too harshly. I'm not totally sure how serious this is but I think it's at least worth of giving some thought...

I would prefer a girlfriend to this contest.

It seems that some people have already seen some problems statements...

I did some speed comparison between recursive and non-recursive lazy segment trees. With array size of 1<<18 and 1e7 randomly chosen operations between modifications and queries. Array size of 1<<18 is of course easier for my recursive code which uses arrays of the size 2^n but on practise it doesn't affect much to the speed of the code.

My recursive ( http://paste.dy.fi/BUZ ): 6 s

Non-recursive from the blog: ( http://paste.dy.fi/kBY ): 3 s

That's quite big difference in my opinion. Unfortunately the non-recursive one seems to be a bit more painful to code but maybe it's just that I'm used to code it recursively.

The binary_search is useless. If there is not element e, then lower_bound and upper_bound will return the same iterator and the distance will be 0. If you are worried about performance, then you can just check after the lower_bound if the element was found.

It's not very hard to try these things yourself. Just make some test cases yourself.

It depends on the compiler. In codeforces cstdio is faster. I wonder how many blogs are there about this :P

I could imagine that on his level (he is ranked 17th in codeforces) getting better is not that easy anymore. And also other people are practising :P

Taking part in a codeforces competition doesn't take much time. For example if you take part in 50 competitions, that's only 100 hours, so doing competitions doesn't mean that one is practising very hard.

EDIT: Oops, sorry. I somehow thought that this was a reply to comment regarding Egor. Stupid me...

Oh, I just copied that complexity from the book and didn't think it much since I thought that in would anyway be slower than my O(a_n*n) solution. It seems that in every test case in main.edu.pl, the value of a_1 is always quite small. For example 8000 in the hardest test case... So that's why dijkstra is so much faster :D

Let's stop accusing others and try to be friends :)

B-but isn't 14 a bit too young??? :3

So... You have been on blue for 4 contests, I wouldn't call that "being stuck". There have been so many blogs about "how to practise". You can search for them. You must solve problems that are hard for you. And solve different types of problems.

Also scanf and printf are faster compared to iostream. It depends on the compiler but that's the case in codeforces.

Is that really so serious? Let's say, there are 20 of those fake accounts taking part in a div. 2 competition. Yes, it might make getting to div. 1 a little harder but only a little. You don't have to win the contest to get there or someting...

That kind of restrictions like that you would have to make a new user 2-3 days before a new contest would affect only some real new participants... Making things hard is a very certain way to get rid of new users. If you are already familiar with codeforces and visit here every now and then, of course it is no problem to make a user a bit earlier.

So cool photos!

Taking photographs with famous people is a nice hobby. Last year I also tried to do it in IOI. It was fun though I always failed and looked very stupid in the photos :(. I also faced a problem: some people are so shy (or maybe they just hated me...) that they don't want to come to a photo. Does anyone have some good tips about how to get a photo with shy people?

How can I change my country (in the standings etc)? It says that I'm from USA and I can't find how to change it. I haven't put "USA" to anywhere.

Have you tried ircnet.blacklotus.net ? It should be in USA.

You can also try open.ircnet.net it should contain all country independent servers.

If those don't work, here is a list of servers: http://irc.tu-ilmenau.de/all_servers/

A bit weird since I have never had any trouble connecting to ircnet.

Nice to see another IRC users here! I have been wondering whether it is popular among codeforces users or not.

About the IRC channel, I think there are some details that should be discussed.

What network should we use? I have mostly been using IRCNet but I really don't know about the differences.

Who will be the channel operators?

Will the channel be "official" i.e. related to codeforces.com admins?

I joined to channel #codeforces in some networks (the first who joins usually gets the ops so just in case...). I wasn't the first one on freenode though.

See these: http://wcipeg.com/wiki/Convex_hull_trick http://codeforces.me/blog/entry/8219

I'm not sure if my solution can be called a convex hull trick, but at least there is some similarity.

We map every array element to some coordinates like in the following code:

int x = 0;
int y = 0;
vector<pair<int, int> > v;
v.push_back({0, 0});
for(int i = 0; i < n; ++i) {
    ++x;
    y += a[i];
    v.push_back({x, y});
}

Now the average can be seen as the slope between two points. Then we iterate through the vector v and maintain a set of points that form the convex hull of the points that we have visited.

Now consider that we have the (K-1)th (the length of the subsequence must be at least K as stated in the problem) non-visited array element (or the corresponding point). We know that the consecutive subsequence that starts from there must start from some of the already visited array elements (or point). It can be seen that we cannot get the best average (or slope) by selecting some point that does not lay in the convex hull. Therefore we can use ternary search to find the best average (or slope).

It seems that there is also somewhat similar solution but which uses two pointers and therefore is O(n), but I don't know it in details.

EDIT: I hope I'm now a bit easier to undestand...

Also something like convex hull trick and ternary search works.

Cin.tie(0) + ios_base::sync_with_stdio(0) + '\n': http://codeforces.me/contest/456/submission/9666030 (826 ms)

Scanf/printf: http://codeforces.me/contest/456/submission/9665953 (358 ms)

cin.tie(0) might also help. I actually thought that it would be almost as fast as scanf but doesnt seem to be the case and it is not enough to get AC. However, endl is very slow and with cin.tie(0) and '\n' you can also get AC. With scanf and '\n' or printf it is even faster.

Is there some difference between ios_base::sync_with_stdio(0) and ios::sync_with_stdio(0)?

Nanahira! https://www.youtube.com/watch?v=ToqeQuZHa3s

Can you give a link to this problem? I cannot find it anywhere...

What do you mean? Lol, I don't understand xD Anyway, now I have to meet her :D

So cute profile picture :3

Some years ago, I also read about how mechanical keyboards are the best. I thought that it would be so cool if when I type, there would be sound like "click click click". I would become a real H4Xx0r! :D

Then I bought this . Is it better than my old keyboard? I don't know... Yeah, it's nice to not have the ten key pad or windows keys (lol), but I haven't been able to measure any difference in writing speed between this and my laptop keyboard. Some people say that typing feel is somehow better with mechanical keyboards. I think you could get used to almost any kind of keyboard and in the end everything as good as the others...

I also think that they layout is much more important. I'm using us-layout and I think that it's pretty nice because it is quite widely used and there are not any keys placed very stupidly (like Alt Gr + 7 to type "{"...).

I'm not sure how Dvorak or Colemak or some other can help you with coding. I know people who can code with QWERTY faster that I can think :P

...you always type "int" intstead of "in".

Writing about algorithms is so hard... ;_;

Thank you for a very good explanation. It helped a lot. Seems that I had understood the centroid decomposition a bit wrong :P

I see there times like 904 ms with python...

By the way, I submitted your code with endls replaced with '\n' and look: http://codeforces.me/contest/350/submission/7049199 280 ms.

I had a vector for every possible factor. Then I used trial division to factorize the integers and added the original number to every vector corresponding its factors. The query could be then done simply using using lower_bound and upper_bound to vector corresponding the given factor and calculating the distance between lower_bound and upper_bound.

You know you are a programming competitions addict when you notice you are thinking about "how should I optimize this program" when actually trying to decide in which order to do these things: wash your hands and then Eat, go to a toilet and then wash your hands. (I was a bit tired back then...)

ps. Correct answer is: go to a toilet, wash your hands, eat. That way you have to wash your hands only once!

Is the code for Div1 C really the correct? http://ideone.com/vZrnSF For me that seems like Div1B code.

Do you think 4-5 min is much? :P

well, some people are just too lovely...

Sounds great! I love cute boys (and girls)!

My solution uses Heavy-light decomposition and segment trees. Complexity is O(N log^2 N). http://codeforces.me/contest/342/submission/6999318

About the O(N log N) solution for 372D: Does the dfs order mean something like preordering or postordering? I guess it doesn't matter which you use?

If I have a subtree with nodes {1, 5, 7, 9} and then I add a node 6, then t = 5 and u = 7? But shouldn't it then be: current size + (distance(s, t) + distance(s, u) — distance(u, t))/2?

If I have understood correctly, I still have one problem that I couldn't solve: What to do when there is no node with a greater or a lesser value than s?

Is it possible to construct order-statistics tree quickly or use something like emplace_hint?

Here are many good convex-hull trick problems (also in the comments): http://codeforces.me/blog/entry/8219

I mean these: http://www.usaco.org/index.php?page=contests and http://tjsct.wikidot.com/usaco You can google the editorials and test cases for those older competitions.

Duplicate of the previous comment...

I'm not red (QAQ), but maybe this will help you at least a bit:

If you are able to solve the problems with pen and paper, then you should also implement it. It might sometimes feel very hard but you should just do it. That's the only way how you can learn. Also training just mechanical coding with very easy problems might help you (like if you get a lot of runtime errors etc).

I'm also facing the same problem: what is the best amount of time to spend solving one problem. I think sometimes it's a good idea to think something for a long time. But if you have feeling "I have no idea and I cannot concentrate to this problem anymore" then you should just read the editorial and go on.

Sometimes editorials on Codeforces are not as clear as they could be. You said that you have done USACO, have you also done old USACO competitions? In my opinion, those editorials are very good. Unfortunately you have to download test cases to your computer and check them manually. :/

No, the function should be first strictly increasing and then strictly decreasing or vice versa.

EDIT: increasing/decreasing --> strictly increasing/decreasing

As long as you have enough memory it will be a lot of more efficient.

YuukaKazami, we have missed you so much... QAQ But still, I love you <3

p.s. you are very cute ^^

If you compile it with -pedantic flag it says something like warning: ISO C++ forbids variable length array ‘p’ So instead of p[n] you should do something like p[3000].

For some reason I cannot open the links with firefox because they go over the Top Rated table.