Hello everyone!

Codeforces Round #182 will take place on Sunday, May 5th at 19:30 MSK. This is my sixth Codeforces round and I hope not the last.

I'd like to thank Gerald and sdya 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.

Gl & hf ! :)

Because of technical issue the start of the contest was unsuccessful. Sorry about it. The contest will be UNRATED.

求轻虐！！！！！！

什么宝宝？

将加:)

Any info. about the score calculating rules? As usual?

I believe this will be a very level of the game!

all your round announcement posts look like the same :D

but i think problems are different :)

Can you tell me what about the score ? dynamic or 500-1500-1500-2000-2500 ?

Good look to everyone! :)

hope my friends and i can reach blue= =

yes sir in the next contest.

It is easter in the ortodoxal world. I hope a wonder happen and everything with the contest will be OK.

looks like the contest is delayed 10 minutes

May be system is experiencing some load. Request are getting timed out.

hope today's sever will be stable

Yestody, GCJ, Have your score arrived 22.

Hope Codeforces can fixt it .. the server cant breathe right nw :O

WTF IS THAT?!

The contest opened while the server was down and some people managed to get the problem statements!

THIS IS COMPLETELY UNFAIR!!

How you know that ?

One of my friends already sent me the statement for problem A

Problem A. Eugeny and Array

That's sad :-/

, Problem A. Eugeny and Array Input le: stdin Output le: stdout Time limit: 2 seconds Memory limit: 256 megabytes Eugeny has array a = a1; a2; : : : ; an, consisting of n integers. Each integer ai equals to -1, or to 1. Also, he has m queries:

What the....

If this is true, the contest need to be cancelled definitely. Please announce about the situation and stop wasting competitor's time.

..

Will the contest be rated? At some moment, contest once started.

Are you sure, you want to continue this contest ?

delay many times

Sereja strongly recommends you to

readALL the problems. I strongly recommend you toopenALL the problems :))its getting late 35 min wasted time yet.

No don't worry, take all the time you need. We have nothing else to do.

it's really unbearable !!!!!!!1

waste a lot of time

the contest is not started yet

Contest gonna start today???

Now I have missed my lunch because of this....

"Oops! This link appears to be broken"

"502 Bad Gateway"

"504 Gateway Time-out"

"Sorry, the server is too busy at the moment. Please try again later."

For 15 minutes these were the only problems I could see!

Hope system can be fixed as soon as possible. It's hard to not get the request of "502 bad gateway"...

If this round will be unrated, please tell us before the contest end.

`**Server Problem !!!!**`

`**Bad Gateway**`

Hope it'll be OK soon... :/Already 00:05 ! (East Asia)

The server problems are getting really annoying!!! at least could someone explain why the server is down lately??

LOL, they all had the problem statements and the code ready before the contest begins

good that the contest is unrated.

As this contest is unrated, I ain't interested anymore to write codes for this one :)

thank you for letting us know that the contest will be unrated.

waiting 35 minutes... and... unrated...

Sorry about the contest start. It was my fault: the main reason is — it was a non-production copy of Codeforces deployed before the contest (some experimental code + experimantal JVM settings + enabled profiler). Somehow the production copy was unable to start because of many requests :( It was started after some time, but it was passed about 0.5 hour and it was a moment of contests was started (so some users were read the problems).

The contest is unrated. I'm sorry about it. I hope you will like nice problems by Sereja.

===

Приношу свои извинения в связи со срывом старта контеста. Это по моей вине, основная причина — был запущен не-production вариант Codeforces (с некоторым экспериментальным кодом + с экспериментальными опциями в JVM + под профайлером). Почему-то production-сборка не смогла сразу запуститься под написком потока запросов :( Когда она была запущена (примерно через полчаса), был момент когда контест был доступен и некоторые из вас уже прочли задачи.

Контест будет нерейтинговым. Еще раз приношу извинения. Я надеюсь, вам понравятся красивые задачи от Sereja и вы получите удовольствие от их решения.

... The author is innocent ... We shouldn't blame on him. ... Sereja, Thanks for your work and problems.

PS: I wonder on this particular issue, does Codeforces will pay for the problemset? Does the author will write the Editorial as well as it been rated?

For sure we will pay to the writer.

AC fun girl lol

Problem C, Do the n elements for which we can change the sign needs to be consecutive ?

No. It's not necessary for n elements to be consecutive!

Something is definitely wrong with new Python 3 interpreter. Sorry for spoiling before the end of the contest, but anyway it's unrated.

So I feel I'm clever enough to make a solution for problem A, but it has TL on test 11. I do some stupid things sometimes so I checked here: http://codeforces.ru/contest/302/status and everyone fails on test #11 (no one solved it using python 3). The problem could be in reading input data, but it's not as big (10**5).

Also after direct translating my code to python 2 it was accepted, so I think something has to be repaired here.

It is true (at least for me) that CPython 3 is sometimes slower than CPython 2.

I wonder if Codeforces could implement support for PyPy?

Python 3 can be slower, but if it fails on this example what will be on examples with bigger inputs? I waited py3 really for a long a time, but in my opinion it's better to disable it in this state.

It would be good if admins add PyPy but the problem is that it's implemented, again, only for python 2

I tried Div2 A and B with Go language but both solutions got TLE in pretests. (my solutions: 3675888, 3676731) I feel more optimization is needed for those new languages.

It's strange that solution both in python 3 and Go fail exactly on test #11. I hardly believe they are equally slow.

I tried to run it localy. The result is "time consumed: 2.81 sec". Note, my laptop is much faster than judging machines. It seems IO in Go is a bottleneck.

I also ran it locally and it took 8.1 seconds... looks like the judge was correct and I should use faster IO functions if any. Thank you for pointing it out.

Right, Python 3 is slower than Python 2 in many cases. For example, on my laptop (i7, much faster than judging machines) you solutions work (on the test 11):

Also PyPy works not faster than Python 2:

I believe Python team should "repair" Python 3 to work faster. On the other hand you should know and understand pros and cons of the language.

Another conclusion that PyPy is not a silver bullet, this problem shows again that it doesn't work faster than CPython 2.

no need to complain about unrated contest, just practice in this contest, after all, this contest isn't offering any prize

the important thing is you doing well in that kind of contest, and this codeforces round is one thing to do to achieve that, higher rating doesnt mean always win

Div 1 C / Div 2 E Yaroslav and Algorithm is very interesting! Anyway thanks for the great questions by the author!

What a pity! It was a very interesting problem set. Thanks Sereja

The problems are so good. Thanks Sereja, sdya and Gerald. What was the 3rd pretest of Problem C!!!???

I think you understood the task of problem incorrect, read again, sorry for poor English.

comment deleted

2 ≤ n ≤ 100 ;)

input:

3

1 2 2 2 2

output:

7

Did you figure out how the problem works? I'm interpreting the problem as in a single operation you MUST change the sign of n numbers. In pretest 3, however, the solution would require changing the sign of four numbers while n=3, which I thought would be impossible...

It is possible using two operations:

Oh wow, thanks. Wasn't thinking like that for some reason.

O(m*n) solutions accepted in problem B Div2.

EditMy apologies, i misread the solutions. Is O(n+m) complexity, because they keep the last position found.

really? if so, not happy about this, as n*m should go up to 10^10 which should make O(m*n) solutions time out by a large margin. O(m*logn) is the way to go

read the constraints again

(It is guaranteed that vi < vi + 1)

solutions are O(n+m)

The worst test case is:

n = 10^5

m = 10^5

ci = ti = 1 for 1 <= i <= n

vi = i for 1 <= i <= m

Ops! you are right, i misread solutions... they keep the last position found.

you might be dont know two pointers :)

Ops! you are right, i misread solutions... they keep the last position found.

Thanks for brilliant contest. It could be a great rated contest if CF didn't crash, but as an unrated contest it was outstanding. GL & HF!

too slow system test :/

I'm waiting to add problems to practice.

Very nice problems!Especially problem C in div1!Thanks to sereja!

Weak test cases for problem B in DIV2

O(m*n) solutions pass the system test! m,n <= 10^5 !!

Okay I was wrong (It is guaranteed that vi < vi + 1) solutions are O(n+m)

show me the code. i think it's O(m+n) solution, not O(m*n), because variable j can not decrease:)

trying to figure out div1 problem D. i believe the number of divisors of a number n is no greater than 2*sqrt(n), is there a tighter bound?

Look at it as the number of multiples in the range [1,n]. Then you get:

n/1 + n/2 + n/3 + ... + n/n

Sum of numbers of divisors for numbers not exceeding

Nis .Also, number of divisors of

Niso(N^{ε}) for every ε > 0.Absolutely! except for the last thing :D

:D I tried to post a picture, but it won't show.

Hi there, a quick question.

In Div2 D/Div1 B, what should the output of the following test case be?

Should it be 1000? Because my program outputs 0 and passed system test. Thanks! :)

a_i<=1000

oh, I missed that one. Thanks, Sereja! I really enjoyed your problems :)

Would you mind returning pagination on the 'Contests' page to its normal state (slightly more than 4 contests per page)?

Already

So sorry to hear that...:(

The third topic what is thinking？

div2

In the problem "Yaroslav and Time", I define INF as 20000005, and get "pretest passed". However, "wrong answer on case 51" in rejudging. So Sad that INF shall be 2*20000005 or bigger. PS: If dijkstra algorithm is used in this problem, it's okay. But if dp is used, this test case should be concered: 5 1000 1000 1000 1000 0 0 0 1 1 1 2 1 2 0 What I mean is that we shouldn't just apply dp in just (sx,sy) to (ex, ey), but the whole (-100,-100) to (100,100).

Can someone tell me solution of problem C div 2

The problem tag is dp and math. However, I solve it in a more complicated way — bfs and greedy. First, I use bfs to get all the possible number of multiplying -1. For example, for n = 2, all the possible number are {0,2}. That's to say, I can multiply zero or two numbers in the array by -1. Then, sort the sequence and apply greedy algorithm. If I can make all the numbers positive, then do it. Else I make as more as I can. Be careful of occurrences of 0.

Here's another solution:

If there are any zeros inside the array, then you can ALWAYS make them all positive.

If you have n is an odd number, then you can ALWAYS make them all positive.

If you have n is an even number and there is an even number of negatives, then you can ALWAYS make them all positive. Else, you can ALWAYS make all but one of them positive.

Here is a rigorous proof of the "always"es frznlich said.

First, note that if

nis odd, we can change any single number. To see this, take the numberxthat we want to change, andnmore numbersa_{1},a_{2}, ...,a_{n}. We do an operation to each of these: (x,a_{2},a_{3}, ...,a_{n}), (x,a_{1},a_{3},a_{4}, ...,a_{n}), ..., (x,a_{1},a_{2}, ...,a_{n - 1}) -- basically every combination possible that takesxandn- 1 of thea_{i}'s. We can see thatxbelongs ton(an odd number) operations and hence changes sign, while everya_{i}belongs ton- 1 (an even number) operations so doesn't change sign.If

nis even, we cannot change a single number: The number of numbers we change is even (some number timesnwhich is even), and two changes equal null, so the parity of number of numbers we change is an invariant. So it will stay even. However, we can change two numbers. If we want to changex,y, take numbersa_{1},a_{2}, ...,a_{n - 1}and perform the operations (x,a_{1},a_{2}, ...,a_{n - 1}), (y,a_{1},a_{2}, ...,a_{n - 1}).This means we can change all negative numbers to positive except probably one, and this "probably one" only occurs when

nis even and there are an odd number of negative numbers.So what we should do is to determine whether the above condition occurs. Besides, we will also find out the sum of the absolute values of the numbers and to figure out the number with the least absolute value, which we will "sacrifice" as the single negative number if there is any.

So our approach is this:

Loop over all numbers. Compute the number of negative numbers in the input and call it

neg, the sum of the absolute values of all numberssum, and the minimum absolute value of all numbersmin. Ifnis even andnegis odd, outputsum- 2min, otherwise outputsum.EDIT: Removed double post (phone acts up at times), useless statement to find the largest number, and useless assumption that zero is negative.

A solution more suitable to a contest, however, is: notice the bound N <= 100 and do BFS on how many negative numbers there could be, since if you change x negative numbers and N-x positive ones in one step, then there will be N-2x more negative numbers (special case: if there's a zero, it's clear that they can all be made non-negative). You don't need to think about all possible cases, just use a simple algorithm to do that for you.

Can someone tell me solution of problem C div 1？ thanks！

One approach is this (works for any number):

For example, the number 6299:

6299, 62?99, 629?9, 6299?, 6299??, 629??0, 62??00, 6300

very tanks!

Just output the following:

The above is composed of five parts: End marker movers of 10 commands, end marker converter of 1 command, converter processes of 10 commands, converter finalization of 1 command, and end marker initializations of 10 commands.

At first, the string doesn't contain any question mark, so some of the end marker initialization commands (d>>??d) is encountered. There will be some double question mark, called end marker, inserted in the string.

Now, some of the end marker mover commands (??d>>d??) will be encountered. This basically moves the end marker one step to the right. As long as this end marker isn't at the end yet, the end marker will be constantly moved, so the end marker will eventually reach the end of the string. At the worst case, the end marker begins in the front of a 25-digit string, taking 25 iterations.

Next, the end marker converter (??>>?) is found, and the end marker becomes a converter sign (?). This converter sign's job is to add the digit exactly before it.

Next, some of the converter process commands (d?<>d) will be encountered, which changes the digit in front of the converter sign. If it's not 9, the addition will not cause any carry, so we're done. Otherwise, the special 9?>>?0 command is encountered, which marks that we need to carry and so we need to add 1 to the previous (more significant) digit. At the worst case, the converter processes need to go all the way to the front with the number 10

^{25}- 1 = 9999999999999999999999999, which takes 25 iterations.Finally, in the case the converter sign reaches the front of the string, we assume that there is an extra 0 in front of the string, and add 1 to it, hence the special (?<>1) converter finalization command.

This takes 32 commands and at most 53 iterations at the worst case, no matter what the actual numbers are.

To arrive at this solution, first you need to realize that 100 numbers is too much to handle by investigating the numbers; there must be some testcase that causes any submission based on handling numbers to fail. Too many numbers for too few commands. So there should be some easy solution independent of the numbers.

Next you need to figure out that you need to find some way to mark the end of the string (so you can start adding), you need to handle all digits, you need to handle 9s added, and you need to handle 999...9s.

The above is mostly trial-and-error after the above realizations.

Instead of last 10 lines you can output ">>??" :)

very tanks!

Because the contest was unrated, There wouldn't be any editorial for it?

There is an editorian on the Russian.

What about English version?

link of that one?

Can you paste the link to the editorial?

http://codeforces.com/blog/entry/7560

In problem B div 1, I failed at system test 52. There is some thing special in this testcase I couldn't find out . Can anyone help me? I think every station passed have to be inside the rectangle of point 1 and point n because when going out of the rectangle and returning, it will cost at least 2*d which is larger than any a[i]. However, it is inaccurate in test case 52 when the best route pass through outside points and then come to point n. For some more details

Test 52: 12 1211 1 5 7 1000 1000 1000 1000 1000 1000 1000 1 1 5 5 3 4 4 3 0 1 0 2 0 5 0 7 1 0 3 0 8 0 10 10 The best way: (1,1) -> (0,1) -> (0,2) -> (0,5) -> (0,7) -> (10,10)

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm О(n^2) or http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm O(n^3)

back to 1 (1,1)->(0,1), but get 4 additional bonus (0,1),(0,2),(0,5),(0,7)

I got caught in thinking that too, but it's not true. Consider the following situation:

where d=1000 and all ai=1000. You should pay 2000 to get out of the rectangle containing 1 and 9, because the gain is 7000.

As a rule of thumb, I would stick to not optimizing anything that doesn't need to be optimized during programming contest. You can improve algorithm after contest.