You can easily figure that out by checking his blog entries.

Fixed. Thanks :)

Sereja's contests like you too!!

Yes, thanks)

And now I should say I like Sereja's contests too!!
Because I improve my rate after a long time in this contest!!
Thank you Sereja:)

Неужели никак нельзя дела с вечера пятницы перенести на вечер субботы, например?

Div1 is for high ratings and Div2 for others ! Problems in Div2 are easier than Div 1 !

http://codeforces.net/help I think you'll find your answer in point #15(What are the rating and the divisions?). You can check the rest of the answers for information since you're new here, you'll find it very interesting.

Thanks Captain.

Just out of curiosity... But why is this comment being down-voted so much?

Это, как бы, не автор решает.

что бы накопить на новый самолетик;)

we will be having acm icpc regional qualifications this month hence the increased number of participants :)

Hope that doesn't affect on stability of the contest :)

Понятно, что на перестановку можно забить, важно только число инверсий. Пусть инверсий n, ответ — d_n. Тогда , это сворачивается в формулу, считающуюся за O(1).

Эм, а чего там доказывать-то? Что на перестановку можно забить и важно только количество инверсий? Это очевидно.

Initially round down all the numbers. Now, you have to round up 'n' numbers. Choose as many as you can so that difference becomes less. Next choose as many as you can so that this minimum difference remains (by choosing integers). If still you haven't chosen 'n' numbers, choose the rest. 4667241

It can be solved by DP:

• DP[i][floor] : In the i-th number having floor numbers rounded down, what's the best answer?

You should think how to calculate what's the best state as you just have two of them.

i solve it using greedy, sadly, after contest :)

we just need calculate the elements that have same value, whether rounding up or down, as this number have same value, it doesnt matter we treat this numbers as round up operation or round down operation, let's call this total of elements 'sama'

assume we have sum of all rounded down numbers, let's call this 'h',

then, iterate from i = 0 to n, and take the minimum difference of original sum and (h+i) that satisfy i+sama >= n

http://codeforces.net/contest/352/submission/4676368

sry for my bad english, hope you can understand

На низкую вероятность этого исхода мне намекают стрессовые 9000 запусков рандома для перестановок без повторений и >3000 запусков для перестановок с повторениями, которые не смогли сломать "очевидную фигню".

У меня есть некоторая очевидная фигня с доказательством правильности. Ты про какую из очевидных фигней?

Можно узнать, что за мистическая фигня имеется в виду?)

Что зашло у меня: В цикле (пока массив меняется), пытаемся изменить знак очередного числа(идем слева на право) на обратный, при условии, что число инверсий уменьшиться. http://codeforces.net/contest/351/submission/4660777

Потому что вы объявляете массив double a[n], а элементов у вас 2*n. Когда вы обращаетесь за предел массива у вас происходит рандомная фигня, иногда работает, а иногда — нет.

Он скорей перестарался с Е див1 ))

Там какая-то магия то с точностью что ли. Я очень долго вчитывался в решения других и искал ошибку в своем, но так и не нашел. Сама суть решения довольно простая и понятная. Мне кажется, многие просто, как я, неаккуратно написали и завалились.

You look for each number in which distance (according to indices) they occur. In the second test case, 1 is on the indices 0-2-4-6, means distance 2. 2 occurs on indices 1-5, means distance 4, and so on. If there would be a number that doesn't have a repeating distance (for example indices 1-3-6), then you shouldn't print it.

you need to check all the indexes of all distinct numbers can represent an arithmetic progression 2nd sample indexes of (1) are 1 3 5 7 arithmetic progression with diff =2 indexes of (2) are 2 6 arithmetic progression with diff =4 all other numbers are unique so print them with 0 as the problem states

It means you should output like this:

Whether the indexes of each number you choose in array meet arithmetic progression?

Yes, output the common difference. (output 0 when the number appears only once)

No, do not output this number.

You have to output all the numbers x in the array such that their indices (the positions at which x are located) form an arithmetic progression. If x doesn't appear, then you discard it. If it appears once or twice, it's okay. If it appears more than once, you determine if the indices (say the 1st, 3rd, 5th elements are x) form an arithmetic progression. (To clarify, this is the criteria for if you output x, not how you actually solve it).

For the second test case, only 1,2,3,5 appear so we only consider those. 1 appears at indices 0, 2, 4, 6 (0-based) and 2 appears at 1, 5. 3 and 5 appear only once. So all the numbers work. If 1 had also been at index 7, then it would not have been included as 0, 2, 4, 6, 7 is not an arithmetic progression.

I am surprised your submission worked on the first 10 tests, but I guess they are pretty simple. Anyway, the problem states that half the numbers must be floored and half must be ceiling, but you do not take this into account. Also, I don't think a greedy idea like what you are attempting would work anyway.

I thought it was hard, but I was wrong :)

I guess they may have a O(n^2) and hard solution and didn't come up with the O(nlogn) and easy one.

UPD. After reading rng_58's solution, I found what I said is wrong. The O(n^2) solution is much easier to implement :D.

Stupid question: why did all these solutions pass? It seems that for multiple equal elements we can take them with different signs, and this additional cost is not taken into account by straight-forward solutions. Is it possible to somehow exploit this effect and construct a challenge? Or maybe prove that this effect does not matter for some reason...

Upd: in russian thread people say that it does not matter, since if we take some element with "+", it is impossible to take some next element equal to this one with "-". I wonder how many people actually thought about it during the contest...

Well, another reason that this task is not good for E is that the following "stupid" solution passed:

1. Initally make all x[i] >= 0.
2. For i = 1 to n: if we change x[i] to -x[i] and the answer goes better then do it.

It will WA on test 11. But if we do the step 2 twice, it can pass the system test: 4673192

In these line

        String line=sc.next();

You only read one char and set it to the line string ...

So the length of line string is 1 ...

Run-time Error occur when you try to divide a number by zero or accessing a index less than zero or more than the size of array ...

Here when index goes more than the 0 Run-time error occurs ...

        for(int i=0;i<n;i++)
        {
            if(line.charAt(i)=='5') f++;
            else z++;
        }

But its not the only problem in your solution ... Find the others too ;)

Hint: Round down all elements and then see how many you need to round up.

http://codeforces.net/blog/entry/9056#comment-147487

I think sorting is not stable.

bool f(pii i, pii j)
{
	return (i.first<j.first)||((i.first<j.first)&&(i.second<j.second));
}

May be the left of the "or" condition was not intentional. I think the following was your intention

bool f(pii i, pii j)
{
	return (i.first<j.first)||((i.first==j.first)&&(i.second<j.second));
}

He made another submission on the same problem afterwards. For every problem, only the last submission is counted, and every submission before it (that doesn't get compilation error or WA on sample tests) gets -50 pts.

Because of Russian word "стандарт" which means the same.

and "т"is usually transliterated as "t"

its updated 10 minutes back :)

What is your algorithm? It would be easier to identify the source of the error then.

got my mistake, thanks!

Array overflow doesn't necessary mean wrong answer or runtime error. It means undefined behaviour.

But in my case , it correctly gave a runtime error : 4662420