Hello everyone!

Codeforces Round #204 will take place on Friday, October 4th at 19:30 MSK. This is my eights Codeforces round and I hope not the last.

I'd like to thank Gerald, yvasyliv, Cenadar and Zlobober for helping me to prepare the round. Special thanks to Delinur for translation of all problem statements into English.

I strongly recommend you to read ALL the problems.

Problem point values for the first division: **1000-1000-1500-2000-2000**.

Problem point values for the second division: **standart**.

Gl & hf ! :)

Maybe a bit weird my question, but anyway, which are the numbers of the other rounds you have prepared? I just want to see the style of your problems.

Thanks.

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

You are absolutely right. Thanks a lot :D

I think it is "Friday, October 4th".

Fixed. Thanks :)

Two matches in one week. I like it.

I like Sereja's contests!!

Sereja's contests like you too!!

i think you mean, Friday, October 4th at 19:30 MSK.

Yes, thanks)

One of my friends (SeyedParsa) likes Sereja's contests because he improves his rate rapidly in Sereja's contests and I wish I can improve my rate in this contest too:))) Good luck everyone;)

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:)

Static or Dynamic problem weights?

Hope the problems would be fun!

a question what is different of Div1 and Div2?(i am new here!) and how can i register for them?

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

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

reading all problems strongly recommend :D

Thanks Captain.

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

Maybe because the same is written in the blog post itself? That makes the post sort of a spam. At least I downvote exact cliches (those that don't have anything unique) unconditionally.

Plus, the grammar's bad.

I rather thought that these down-votes kind of ruin the harmony here at Codeforces... Most of the down-voted comments are posted by newcomers, they may simply want to express that they're here, that they want to be part of the Codeforces community... Maybe what they say contain nothing important but that's not a reason for down-votes... I would think that down-votes are for those who insult people or are impolite... Furthermore, about grammar... As there are people from all over the world, with most of them are from non-English-speaking countries, I think bad grammar is very understandable...

I don't see many comments that are rude, but still not in the "should be deleted by admin" region. There are so few of those that if we really limited the reason for downvotes to be rudeness, the downvote button would just become a tool for trolls and it'd be better off removed. And that'd be weird.

While I realize it's a bit cruel, writing can be good or bad, and I try to vote accordingly. It's also unfair if someone writes a good comment, and gets around as many votes as someone who copies a sentence from the text on top of the page.

You're totally right... I just find it quite uncomfortable to see a lot of comments getting down-voted for no obvious reason... I really hope everyone can think before they vote like you do...

thx...I hope everyone will get high score;

Best author's (in my opinion) contest exactly on my birthday, really awesome present :) GL &HF everybody )

We have a national level university contest in Bangladesh tomorrow. Hope it would be a good warmup.

Good Luck for all~..

What about the score distribution? :)

seens to be a little bit hard? well, hope everyone can figure out all the problems && enjoy every contests:)

first time writing div 1 round

Wow... More than 4000 participants :D What is the record, by the way? :)

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 :)

Looks like no 500-points problem for Div 1 ... It may be thought round for me, first time participant @ Division 1 ... ;-)

Hope better results 4 everyone!

How solve problem C?

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:

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

I thought of this, but I thought that somehow the sign of the difference would matter. So I added another state and I calculated the maximum from the negative differences and the minimum from the positive differences. Can anyone explain why the sign doesn't matter? Especially when you can reach a state with both x and -x. Thanks!

It can be solved linearly. Unless a_i=0 (discarding the integer part), it doesn't matter whether you round a number up or down. If you round up, you add 1-a_i to the difference. If you round down, you add -a_i. So you end up with the total difference being n-sum(a_i). Now, when a_i=0, rounding up gives 0, not 1. So you count the number of a_i=0 and count how many of those to round up. Subtract this number from n-sum(a_i) and you get the answer.

Thank you for the answer! But it's still not clear for me: in the test case

`0.000 0.500 0.750 1.000 2.000 3.000`

theN-suma_{i}becomes 1.750, which can't be transformed to the answer of 0.250 by substracting 1s...Sure it can. Note that at the end you have to take absolute value of the answer. As cfk said you need to count how many a_i=0 you round up. In this case 2, so |1.750—2|=0.250.

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.com/contest/352/submission/4676368

sry for my bad english, hope you can understand

I guess many submissions (including mine) for Div1-A will fail because of small array size (2000+etc) :(

Liked the problem set (y)

I'm ready !!

There are 644 contestant in Div. 1 and there are almost 200 contestant who have no point.

My 2nd Div1, I am very happy with 57th. Thanks for the problems, I really liked them. If only I didn't do A so slowly!

What I am wondering is how people hacked A. I noticed that many people got caught on system test for A, but when I was trying to hack I couldn't find anything! So does anyone know common mistakes in A?

The contest is over and I still can't understand the statement of problem B. An explanation for the second test (not for the one with a single number in the array) would have been great ... Could somedody explain it?

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.

Well, I really wonder can Problem C in Div.2 be solved by greedy algorithm?

Why did my solution come out like this in Test #11?

4671464

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.

Thanks for answering. My negligence.

Why was E E?

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...

If we choose signs greedily, -x will never appear after x.

Well, if you have multiple elements with same absolute value, in optimal solution they will have minus sign until some point and plus sign after that point. So there will be no inversions between them.

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

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

Is it actually correct solution?

If in step 2 we take

"answer does not goes worse"instead of"answer goes better"then we even don't need to repeat this step twice)And why does it WA, when we do it just once?

Because it's totally wrong. We could need to change several

x[i], which would make the answer larger, and then change several other ones that would make it smaller. It just shows the weakness of tests.Someone can prove, that if there are no i, such that if we change ("update") x[i] to -x[i] the answer goes better, then we could'n improve the answer.

This is such a natural type of statement, but in this particular case it's hard to believe in it. Of course, there is no guaranty, that after step 2 in our solution there are no such x[i] that we can update.

The idea of proof: Call the operation "inverse" of x[i] is multipling it by -1. Assume the contrary: there are no such i, that if we inverse x[i] the answer goes better, but we could improve the answer inversing number x[i] = a and x[j] = b to -a and -b (in a general case we have to inverse k numbers, but for more clearness we take k = 2). Let us consider numbers ka and kb. ka = (number of inversions in initial array — number of inversions after inversing a to -a). The definition of kb is analogous.

By assuming ka >= 0 and kb >= 0. Put the number of inversions = inv Case 1: ka > 0. When we inverse a and b, inv_new = inv + ka+kb. But we don't take in account pair (a, b), that can be "bad" (i.e. this pair is inverse), but (-a, -b) is "good". Then the number of inv_new >= inv + ka + kb — 1. Hence inv_new >= inv. A contradiction Case 2: ka = kb = 0. Let inverse a and b not simultaneously, but one by one. Then we can choose the correct order of chain of inversions (we inverse a, and then b OR b and then a), so that inv_new >= inv (Note, that a > b (elsewhere we have a contradition the same way as in case 1). Assume, that -a < b. First inverse a. inv_new = inv + ka = inv. Then inverse b. Since the pair (-a, b) is already "good" (and (-a, -b) too) and kb = 0, we have inv_new = inv. Again a contradiction. If -a < b is false then we will first inverse b, and then a)

I did step 2 just once (with "answer gets better") and it passed. And I think that it is correct. Reason:

We don't care about equal elements, as discussed here http://codeforces.com/blog/entry/9056#comment-147490 .

If we have

P_{a},P_{b};|P_{a}| > |P_{b}|, then |P_{a}| > |P_{b}| ≥ - |P_{b}| > - |P_{a}|, so if we changeP_{b}to -P_{b}, the "inversness" (whether they made inversion, or not) of these two numbers doesn't change. Thus inversness of two numbers can only be changed by inverting greater of them. That means that effects of inverting numbers on total number of inversions are totally independent. So we can do it greedily.while(true){ System.out.println("THANKS SEREJA"); } contest very-very good.

A question: when i run problem A(in Div2) in custom test, it works fine without error but when i submit it, it shows runtime error! what is wrong?

In these line

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 ...

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

it works fine on netbeans, next() read a string. i will try to find why index goes less than zero or more than length,

thanks,

It reads one string but until the space .The numbers are separated by space so it reads only one number.

You can easily check it by printing.

Anyway you need better debugging , Asking such questions may consider as spamming here.

Can somebody hint towards the solution for Div 2 C?

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

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

Can anyone help me on Div2 B Why my code outputs negative numbers in Test#11 4670950

I think sorting is not stable.

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

A friend of mine made a correct submission for Div2 B during the contest but he found out it was "Skipped". What's wrong? This is quite unfair.

Here's the link: http://codeforces.com/contest/352/submission/4665780

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.

He did make a submission later but it was post-contest. During the contest that was his only submission. You can clearly see that here: http://codeforces.com/submissions/mahmouder

Oh, right. Sorry, I didn't notice. I have no idea why, then.

Why do contest writers offen misspell "standard"? I'm not blaming anyone, I'm just curious.

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

and "т"is usually transliterated as "t"

Oh, I understand. Thanks.

When will the rank be updated ?

its updated 10 minutes back :)

hey, can anybody tell me why my submission 4674576 for Div-1 A is giving wrong answer? thanks in advance.

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

got my mistake, thanks!

I wonder why this input (n = 2000 and 4000 zeros) was unsuccessful in hacking this code : 4663057, because the size of array in this code is 2010!

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

Exactly. It "doesn't

necessarilymean WA or runtime error". It's undefined behaviour.Screencast

where is the editorial ?