Hello everybody)

Today is coming regular Codeforces round #163 for Div.2 participants. Traditionally the others can take part out of the competition.

The problems were prepared by authors: Rakhov Artem (RAD), Kudryashov Igor (Igor_Kudryashov), Pavel Kholkin (HolkinPV) and Gerald Agapov (Gerald). Traditionally thanks to Michael Mirzayanov (MikeMirzayanov) for Codeforces system and Mary Belova (Delinur) for translating the problems.

**UPD**: It is decided to use **dynamic scoring system**. The problems will be sorted from low difficulty to high by authors' opinion.

We wish everyone good luck and high rating)

**UPD2**: the contest is over, hope you enjoy it)

Congratulations to winners:

1) Aharon

2) marcoskwkm

3) ChaosLogic

4) Imsbuno

5) Conny

**UPD3**: the editorial can be found here)

Im first, so i need most of neg votes.

; )

: )

last CF round of this month :(

I wouldn't be so sure:)

Considering Petrozavodsk training camp will start shortly — quite probable

I wish everyone good luck and high rating too! ;)

u will surely get some positive votes for this :P

everyone's waiting for score distribution. wish well for all participants.

what do you mean by dynamic scoring system??

dynamic problem scores

Its like asusual.. am right??

No, usually max. problem scores is static.

Points depend on number of solvers.

good luck evryone! :)

Ithink some of people from countries expect iran doesnt like iranian people:( becausa they give all iranian people negetive mark!

Don'be so nationalistic-thinking! first of all, that's international community. Secondly, there's no flags around your ava — that's is not the main question! :)

almost 2800 Registered participants (including ones who are not in the competition). I think this round is the one having the highest number of participants (counting people registered before contests only). anyway good luck

Does that include people who are from Division 1?

it is based on number of Registered participants, so including division 1 people (but they are out of competition)

i just count for div 2 contests only, excluding rounds with div 1.

it was a awful contest x(

always pessimistic, aren't you? :)

Worst contest ever,

Top 30+ solved only A, B

and guess what?! from top 30+ down to the last ranked contestant, all have solved A, B only!

i think problems are very interesting, but hard.

It is not the worst contest ever! It just too hard to Div2, but problems were realy interesing.

So when the first two problems are fucking easy and the rest three focking hard is normal?:D

I think too. It`s not worst, but for most of Div 2 participants not interesting, because they compete only in speed of coding.

`It is not the worst contest ever! It just too hard`

Looks like the very definition of the worst contest (ok, ok, not worst ever, just very bad)

Why am I unable to see the pretest values in which my submissions failed? Did i miss something in the newsfeed?

Because the contest is still running

In the last contest I was in, I could see the test cases for which my code fails even while the contest was running.

Maybe it was practice, not contest?

It is always unable to see pretest values except tests from the problem during the contest.

Seems my memory has failed me. Thank you guys for clarifying.

2200 participants during the contest with 0 Successful hacking attempt,system testing will be so fast :)

I saw one around 5th page in standings (althrough that was from Div 1 coder)

Congratulations for the contest, the difference between place 1300 and place 100 is less than a 100 points.

A-B-E-E-E...

I think that hardest problem was div1 E level.

Not really. Quite straightforward interval tree, but requires some coding. Good for Div 1 D

I don't know how can we multiplicate all numbers by (i-l+1)^k quickly. That numbers are distinct and they are not some good sequence, as for me.

Actually if we calculate for all j up to k, we can then calculate required sum

Would you please explain this problem in more detail?? Thanks!

Let , and . Then (you can do calculations yourself)

Thanks very much!

I think C, D, E have the correct letters assigned, but for Div 1.

Can anyone tell the algorithm for D? Be free to answer in English as well as in Russian

Интересует тот же вопрос. Вначале я просчитывал путь от каждой вершины до каждой Флойдом, затем пытался расположить кафе на всех дорогах наилучшим способом. Сначала тернарником. Работал медленно + ВА10. Потом написал вычисления наилучшего способа вручную. ВА9

Тернарник не работает, потому, что функция не выпукла. Там получается кусочно-линейная функция (зубчатая). Я думаю, что мое решение достаточно понятно для чтения

Ясно, спасибо

Traditionally authors wish Successful Hacks .. Is this the first round I am seeing with no successful hacks ??

Hats off to the author for problem C. Looks so interesting and yet is so difficult to think.

Unexpected difficulty level was unexpected.

yeah! from rank 200 to 2000, all of them solved 2 problems and they have been sorted by their typing speed!

and reading speed!

actually in problem C we just need to sort all rows as increasing amount of 1's and sort the columns as increasing amount of 1's

note that sorting columns won't change any thing in rows and vise versa

so we don't need more than 2000 move

I missed a really important constraint no of cells having ones are no more than n — 1. :(

Sigh, I missed the second part...

Actually you can not sort in O(n) time , you have to also tell the positions which were swapped. For the second part , you can sort by any trivial algorithm for sorting in O(n*n). Note that I was missing one important thing , No of ones in columns won't change if I swap the rows. So I can just count no of ones in columns also and do the same thing as done to rows.

i think we don't need more than n-1 moves.

do not be so accurate!

I only wanted to show that sorting won't exceed the limit 10^5

it has been sorted, but it's not a correct answer.

You have to take care of equal case , If equal then do the sort lexicographically decreasing.

Why ternary search is incorrect in D?

Read above Egor's comment

Because function within edge is not convex. It is segment-linear, with segments alternating y = x + b and y = -x + b

Please explain the second part y = x + b and y = -x + b ??

Function for each edge is segment-linear (i. e. edge can be divided into segments, and on each segment function would be linear). Generally linear function is y = kx + b, but in this case k is always either 1 or -1, and this values alternate throught edge

I think these div2-only contests are not really for div2 participants, only. I mean, they're more likely generic ICPC contests, with very easy problems and very hard problems. The final scoreboard today clearly shows that problems C,D and E are not equivalent to div1-A,B and C, as they usually are in regular, div1&2, 7-problems contest. For instance, problem D, that should be equivalent to a div1-B, was solved by 8 coders only — 6 of them were div1, out-of-competition ones. Although we know most div1 coders don't register for div2-only contests, we won't see only 6 coders solving problem B in a regular contest. So I think these div2-only contests are not really equivalent to div2 regular contests. Should they be?

edited

Yupp exactly same :P

Same codes?

http://codeforces.com/contest/266/submission/2992482 http://codeforces.com/contest/266/submission/2989351

Indentation spaces are not same :P

Nop, there is not the same count of '\t' on the two codes ;) Edit: too late :/

请使用英语。

He just asks to use english! Why so many negative??? Whats wrong with you, guys??

^ ^ Thx.I just comment for fun.

ჰე ჰეი მეც მიყვარს ეგეთები :დ

не надо ничего взрывать

Эта шутка совсем не смешна.

No, you are not allowed to drink vodka here!

Нет, здесь нефти нет.

http://translate.google.ge/?hl=en&tab=wT#auto/en/%E8%AF%B7%E4%BD%BF%E7%94%A8%E8%8B%B1%E8%AF%AD%E3%80%82

How long does it usually take for ratings to update?

It's a matter of high blood sugar, or rather it's gonna be.

I think this contest is really a coding speed test for div 2 participants. I finished the first two problems less than 10 minutes. After that, I read the description of problem E. At the first glance, I thought it had something to do with segment tree. However, right after looking at the sigma notation, I just gave up. I played 2 games of League of Legends.

And surprisingly my rating still increased after the contest.

And i played 2 games of Dota :D

Could anyone tells me, why dis the problem D can not use Ternary Search Algorithm ? I alawys get wrong answer on test 36 ! Many thanks ! this is my

my code links : http://codeforces.com/contest/266/submission/2993280

You should read egor's comment.

You should divide each edge into several segments, and use ternary search on every segment. Just like what Egor have mentioned above. And you can also see more details in my submission. 2995464

No need for ternary search, actually

Yes, you are right. I found the function within each segment is unimodal, so I used ternary search to find extreme points, but I did not realize that it is possible to get extreme values by direct calculation. Thank you so much. I will correct my solution.

There is a grammar mistake in problem C. Some cells (n - 1 cells in total) of

the thematrix are filled with ones, the remaining cells are filled with zeros. We can apply the following operations to the matrix:please give me some hint about problem D ?