Hi codeforces,

For Chinese users and anyone who has been in China recently, can you recommend a VPN that works decently in China?

How to solve this problem?

Consider a sequence s1, s2, ..., sn of n infinite binary strings (that is, consisting only of zeros and ones), where each character of each string is generated uniformly at random independently from others. Denote f(s1,s2,...,sn) = max LCP(si,sj), 1 ≤ i < j ≤ n where LCP is the maximum common prefix of two strings. Compute the expected value of f(s1, s2, . . . , sn).

Input

The only line of the input contains one integer n (2 ≤ n ≤ 10^4).

Output

Let the answer in the form of an irreducible fraction be P/Q. Then output P · Q^−1 mod (10^9 + 7).

So recently I was trying to solve this problem 100965F - Polynomial, the following blog contains spoilers.

The first approach was trying to represent the polynomial as x * (x + 1) * ... * (x + m — 1) and get the result using divide and conquer and FFT multiplication in which didn't fit in the time limit. So the second approach is to print just the polynomial which will give 0 but only for x coprime with m, but surprisingly it got accepted.

So how is this correct? and also how the checker for this problem is written?

Hey Everyone,

I have a problem since yesterday, I can't open Codeforces website (I'm using a proxy to write this). I've tried to open it from Incognito mode, another browser, even another device (on the same network) but still it doesn't work.

I've asked friends using the same ISP and the website works fine for them, any idea why this would happen? :(

I've noticed this issue a lot. When I solve some problems in a gym contest (without coach mode), open the coach mode and then view any submission in the contest, all my solutions disappear from standings, status and from my submissions. And I have to open the coach mode to find them in the standings. Also the problems are marked as unsolved (They are not green anymore) and this particularly is really annoying.

Did anybody notice this issue before? And is it a bug or this is intended to happen? I hope it's a bug :D

I was wondering what is the number of chess games modulo 2? Is it one, zero or is it impossible to know the answer without knowing the number of chess games itself?

Hello Codeforces!

The last codeforces round was one of my worst. It took me a very very long time to code A. Then I read B, got an O(Nlog²(N)) solution. I thought it maybe too much (ironically after the contest some magical O(N²) solutions passed) and I spent the whole contest trying to optimize it to an O(NlogN) solution but failed. At the last 10 minutes I thought to give it a shot but it was too late to write a quick bug-free solution. I didn't even read C which was a problem I've faced before.

Anyway, after the contest I've submitted both an O(Nlog²(N)) and an O(NlogN) solutions 12199582 12199737, The O(NlogN) solution passed in 46 ms which was pretty okay, but, the other solution passed in 78 ms! which is about 1.7 times of the O(NlogN) solution. I've faced some problems before where O(Nlog²(N)) was too much (e.g. 514D - R2D2 and Droid Army). Even when an O(Nlog²(N)) passes it takes a lot of time (e.g. 11843275).

First, how does the O(Nlog²(N)) passes in such small time? and generally how to determine whether the O(Nlog²(N)) approach is good for a problem or not? (without coding and testing of course).

558A - Лалаландия и яблони

Let's divide all the trees into two different groups, trees with a positive position and trees with a negative position. Now There are mainly two cases:

1. If the sizes of the two groups are equal. Then we can get all the apples no matter which direction we choose at first.
2. If the size of one group is larger than the other. Then the optimal solution is to go to the direction of the group with the larger size. If the size of the group with the smaller size is m then we can get apples from all the m apple trees in it, and from the first m + 1 trees in the other group.

So we can sort each group of trees by the absolute value of the trees position and calculate the answer as mentioned above.

Time complexity:

Implementation

Hello Codeforces!

I'd like to invite you to Codeforces Round #312 (Div. 2). It'll be held on Tuesday, July 14th at 18:00 MSK.(notice the unusual starting time) and as usual Div. 1 participants can take part out of competition.

This is my second round after Codeforces Round 287 (Div. 2). :)

Great thanks to Maxim Akhmedov (Zlobober) for his great help in preparing the contest, Maria Belova (Delinur) for translating the statements into Russian, Mike Mirzayanov (MikeMirzayanov) for the great Polygon platform and Polygon's developers team for their hard work in enhancing Polygon system.

The scoring distribution will be announced later.

Good luck everyone and I hope you'll find the problems interesting. ;)

UPD1 Scoring distribution will be 500-1000-1500-2250-2500.

UPD2 Contest is delayed 10 mins. Sorry for inconvenience.

UPD3 Contest is finished. Thank you everyone!

UPD4 System testing finished. Congratulations to the winners.

You can find the editorial here.

507A - Amr и музыка

Problem: We have to split the number k into maximum number of elements of a_i such that their sum is less than or equal to k.

Hint: To maximize the answer we have to split the number into the smallest numbers possible.

Solution: So and since the limits are small we can pick up the smallest element of the array and subtract it from k, and we keep doing this n times or until the smallest number is larger than k. Another solution is to sort the array in non-decreasing order and go on the same way.

Time complexity: or

Implementation: 9529124

Hello Codeforces!

I'd like to invite you to Codeforces Round #287 (Div. 2). It'll be held on Friday, January 23rd at 19:00 MSK. and as usual Div. 1 participants can join out of competition.

This is my first round so wish me luck! :)

Great thanks to Maxim Akhmedov (Zlobober) for helping me preparing the contest, Alex Fetisov (AlexFetisov) for testing and giving useful tips regarding statements, Maria Belova (Delinur) for translating the statements into Russian and Mike Mirzayanov (MikeMirzayanov) for the great Polygon platform.

The scoring distribution will be announced later.

Good luck everyone and I hope you'll find the problems interesting.

UPD #1 Score distribution will be standard 500-1000-1500-2000-2500.

UPD #2 Contest finished, hope you enjoyed the problems. :)

UPD #3 System testing finished.

Winner of the contest is going to be disqualified due to "Do not use harsh, rude or misleading handle." part of Codeforces rules.

So congratulations to the winners:

chickennethsnow

qcrqgx175

mikeyue_tc

Dennord

KilluaZoldyck

UPD #4 You can find the editorial here.

Hi everyone, I'm looking for some good detailed from scratch DP tutorials.

Any help would be appreciated.