hahahah!!!!!!!

On the dashboard, click the padlock icon for locking a problem (Note, that you can not send your solution for a problem after locking it). Then go to room results, where you can see roommates codes for the problems you've already locked (you can see a certain solution by double clicking on it in the room results table). After you've opened someone's solution, you can consider it and then hack it. When hacking a code, you're entering some testcase on which that code is most likely going to fail (it may be wrong answer, or running out of time/memory limit). When you want to enter a large testcase, you can send test generator instead of typing it. Test generator must be your program which produces a file with a testcase in it. After hacking a code, you can see hacking results. There are two possible outcomes: "Successful hack" — it means the code failed, and you're rewarded with 100 points for that. Otherwise, it's "Unsuccessful hack" (the code did not fail) and you get minus 50 points for that.

In div.3/educational contests, you can not hack any solutions during the coding phase. In the hacking phase which follows the coding phase and lasts for 12 hours, you can hack any solution. Just double-click somebody to view his/her submissions and then click "hack it!" button.

there will be no points for successful hacking attempts and no penalties for unsuccessful ones in div3/educational rounds.

[DELETED]

Yeah have the confidence that i will never be a specialist ever :'(

It's rated for Newbies, Pupils and Specialists. It is also rated for Experts who have taken part in at least two rated rounds (and solve at least one problem in each of them).

But in last div-3 contest there was 9000+ participants!

But they can take part out of the competition. It won't decrease the happiness of doing a contest. So Div.3 is very nice since it's easier and more people can have fun!

But I don't have enough money to donate.Actually I am hungry, for I don't have money to eat rice.

No.

Since you are above 1600 your rating will not change by Div3 rounds like this one.

Short answer:

No it doesn't, it just is basically something that makes your score for that problem worse.

Long answer:

Basically in Div3 (and Educational Rounds or any other rounds that follow ACM-ICPC format), your score is calculated a bit differently from normal CF rounds. Participants are first ranked by the number of problems they solved. After that ties are broken by a so called "penalty".

This penalty has two parts to it:

• The sum of times of your submissions.
• The wrong answer penalty times the number of wrong answers on problems that you solved afterwards. (that is if you get a wrong answer on a problem and don't get accepted till the end you wont be penalized for those wrong submissions)

A person with a lower penalty is ranked higher.

Consider for example the following contest with 3 participants — A, B and C and a wrong submission penalty of 10 minutes:

• A solves 2 problems, the first at 5 minutes and the second at 30 minutes, with no wrong submissions on either.

• B solves 2 problems, the first at 5 minutes and the second at 25 minutes, but makes a wrong submission on the second problem before submitting the correct solution.

• C solves 3 problems, the first at 10 minutes, the second at 40 minutes and the third at 1 hour 20 minutes.

So A has solved 2 and has a time penalty of 5 + 30 = 35 minutes,

B has solved 2 and has a time penalty of 5 + 25 + 10 = 40 minutes, and

C has solved 3 and has a time penalty of 10 + 40 + 80 = 130 minutes.

As we sort them first by number of problems solved then by penalty, so the final standings will be:

• C (3, 130)
• A (2, 35)
• B (2, 40)

Fix B.Find A and C greedily.

you find all pair of a and b from 0 to 10^4(maybe more for safety) for every pair of a and b you find suitable third number nearest to original c. it probably cost you about n*log(n) for every test case.

Make all the possible combinations (A, B, C) with for-loops and compare them with the given (a, b, c)s.

The key is that neither of these three should exceed 10^4. (If they did, they would in itself be not the efficient solution) I have found just a bit fewer than 5X10^5 cases which satisfies (A, B, C). Thus, given that the test cases are 100, 5X10^7 seems like a good deal.

Brute force, if applied properly, can be a very powerful tool.

You are running the outer loop 4 times,your solution will fail,If more than 4 swaps will exist for a test case. https://codeforces.com/contest/1311/submission/71814830 Here I just changed your solution a little bit and it got accepted.

I'm also want to know it :(

The non-integer part is really helpful here — distance between points i and j will be either 0 (if they overlap), or starting distance (if they diverge). You can easily see, that for i < j if vj < vi then distance is 0. So, for each i we can find sum of xj such that vj >= vi (I scaled speeds to fit in a segment tree) in logarithmic time, then we can calculate everything in O(n log n).

Hint:

Here's how you would find the sum of the differences between all pairs.

Sort the array. Set sum = 0. Note that for every number, it will be subtracted from the sum a (number of numbers greater that it) of times, and added to the sum a (number of numbers lower than it) of times, so you can solve the problem in O(NlogN).

I think NlogN can be achieved with PBDS or compression with segment or fenwick tree, just use contribution technique.

If for every i, you consider all j<i, won't you do 1+2+3....(n-1) = n(n-1)/2 number of operations which is O(n^2) ?

Was able to locate the problem, this code works better.

Seek some damn therapy instead of asking random internet strangers.

Yes there are. it's called editorial

I also got a runtime error once. Mine was because the array size I declared was 10e5 (not sufficient). I changed the array size to 2*10e5 + 5 (according to the constraints), and it got accepted.

Там сумма размеров поддеревьев, а тут сумма глубин

Very strong tests in problem C! (see announcement)

probem D. I went over B from 1 to 1e4, and of course I was hacked. who hates this feeling..

According to codeforces... Hacks will be open in ~10 minutes.

I made the opposite: first construct a balanced binary tree (parent of x is x/2), then on each iteration take two deepest leafs v1 and v2, and attach v2 to v1. On the last iteration, maybe, you should attach v2 not to v1, but to some its parent.

Each vertex is moved at most once, so it is N^2. Looks like it is possible to do it in NlogN, but we don't have to do it.

It passed stress test for n, d <= 50, I think it is correct.

What the fuck is that though?

Why -1

I don't have proof(maybe someone can hack it), and use a random method(pretty fast).

first prep lower_bound&upper_bound of n. it's easy to note $$$ub[n] = n*(n-1)/2$$$. while $$$lb[n]$$$ can be find recursively, each time you divide $$$n$$$ almost half. i.e. $$$lb[n] = n-1 + lb[x]+lb[n-1-x]$$$, where $$$x=n/2$$$.

then try divide&conquer, for random $$$x$$$ and valid $$$n_x$$$, and so other son should valid. Since in intuition there should be many valid partition.

It works from the submission page. It can be opened by clicking on '#' in solution preview

Me , What does it mean ??

if you use vector instead of set it is O(n)

        for(int i=0;i<n;){
            
            int j=i;
            while(pos.find(j)!=pos.end())j++;
            sort(a.begin()+i,a.begin()+j+1);
            i=j+1;
            
        }

Are you sure it is O(n log n) ?

how to prove it ?

I think that is because of at some moment hacks were disallowed but uphacking was allowed. So, it seems like you hacked this solution during the uphacking phase and it is considered as correct (but uphacked) solution.

And I don't know what I have to do with it.

Probably because they changed the accepted condition

Wow, this is new to me too

haha :D

Most people considered A,B,C <=1e4 including me which lead to hacking :(

Face reality, the whole universe is not a fair thing. It is a competition.

Зачем тебе рейтинг, ты его опять на опечатках уронишь. Будь внимательнее

ну -100 из-за того что ты думал о идейной стороне задачи а не о том, что нужно писать ll вместо int (особенно когда в задаче ограничения вроде как на первый взгляд предполагают, что можно и интом обойтись, как в прошлой бэшке например) это всегда дичайшая дизмораль (и так черная полоса с рейтом, так тебе еще -40 вместо +60 дают блин)

имхо вообще без разницы как-то, можно и не спасать, а можно и спасать.

решили спасать, ну и ладно.

спасли и спасли, так сказать.

please stfu, like you didnt even participate in the contest, what is your problem?

cyan revolution is only a matter of time..

We changed only C because we had a bug in author's solution. I didn't have overflow tests (both mistakes in C and D are mine and I'm very sorry about that) and only one of three solutions considered overflow with #define int long long. So we considered to change the constraints in such a way that this issue will not affect participants because I had a problem in my solution.

The problem D issue is that it has very bad tests and I wonder how I don't have at least one test case (of hundreds test cases) with $$$C > 10^4$$$. It was really surprising for me and I don't even know how to generate such tests in advice (the only way I understand is to write such a wrong solution and stress it).

Anyway, this is just an excuse and I blame myself for these mistakes. Sorry everyone who was affected by my poor brain work.

UPD: And for all who think that I'm silent and don't want to accept my mistakes or describe you the situation. I'm so silent because now I just trying to do all I can: write the editorial as soon as possible and I trying to do that right now.