Hello!

Codeforces Round #210 will take place on November 10 at 21.00 MSK and I am the author of the problems.

This is my first round on Codeforces and I hope everything will be well. I would like to thank Gerald Agapov(Gerald) and Vitalii Aksenov(Aksenov239) for helping me to prepare the round.

Good luck!

**UPD.**

Score distribution in first division: **500-1000-1500-1500-2000**.

Score distribution in second division: **500-1000-1500-2000-2500**.

**UPD.**

Congratulations to the winners!

First division:

Second division:

**UPD.**

Comments with a lot of positive votes requires a creativity that I don't have. :) So I just wish good luck for you with your first contest! :)

nice try :D

It worked up above. :P

Glad to see a

veryfull list of contests after a long time!!4 contests in 9 days! That's the best thing everyone wants!

New author — new type of problems!

Please, don't repeat your comments previous one !!!

OK, New type of problems — New author!

You fail on even the most fundamental principle of programming.

https://en.wikipedia.org/wiki/Don't_repeat_yourself

just use variable string str="New type of problems — New author!" and write variables ;)

Oh, thank you

I'm WET

(Don't repeat youtself = DRY) (Write everything twice = WET)

why so many only div2 contests?? Being in div1 seems to be a negative thing nowadays.

You can still participate in Div 2 contests, they just won't affect your rating. It's still good practice though.

u are 100% right that Div-2 contests are good practice, but the thrill that comes with doing a

rated contestwill not be there, which IMO is the most important thing during the round.Wow, two continuous Div-2 rounds !!! Hip-Hip Hurrey :D best of Luck :)

after more than a week, finally a contest! not just one, but this is the first of

4 rounds in 9 days! :)Wow! +180, 30 minutes before the contest! That's

awesome!MikeMirzayanov happy birthday to your daughter Tatyana. Hope see had a wonderful day today :)

funny to see lots of people misunderstood that sentence. :D

"Oh, St. Dijkstra, Tatyana is 2 years old!" ... ;-)

Why almost all of you think that her name is St. Dijkstra?? Dijkstra is a famous researcher in computer science, and his name was mentioned in the sense that he is a 'saint' in our programming world. How couldn't you understand such a simple thing?

Ambiguous sentences invite ambiguous interpretations. In many parts of the world, it makes perfect sense to name one's child in honor of some intellectual hero like Dijkstra. Also, check out this guy named Aristotle Socrates.

Offtopic — I wonder what is

(p1)at the bottom of the pages of Codeforces... :SThis contest is too late for Chinese coder...

problem d was dp right?

does the votes mean that problm d from Div 2 was dp?!! cant some one just reply? is it that hard?!!

Can anyone explain the solution ?

Why the standings are frozen during system test?

That's because during the contest the solutions are tested using only the pretests (which are simpler than the final tests). At the end of the contest, the results are frozen and all the solutions are reevaluated using the final tests.

It means that you can get accepted during the contest and at the end, if your submission fails on one of the final tests, your points for that problem are taken back.

How to solve Div1 E? The idea is Dijkstra in a layered graph with (k+1)*n nodes?

how to optimize dp in problem C?

In C(div2) example 1 input : 4 5

1 2 3 1

2 1 2 8

2 3 4 7

1 1 3 3

2 3 4 8

output: 4 7 4 7

why is a[1] equal to 4? when we know : line 2, a[1] is max 8 line 4, added 3 to a[1] so answer is a[1] = 8 cos we don't know any other change..

That example had multiple solutions, including yours. Even if a[1] = 4, a[2] will meet the max requirements.

both are correct, you have to output atleast one correct array.

in that case, a[1] can be any number, less or equal than 7

"4 7 4 7" is one of answers ! ( take care about multi answers ) ...

"по записям операций найдите хотя бы один подходящий массив."

Thanks, I had misunderstanding of a task.

What are the strings for the first and the second example of Div1 C?

in first example zT where T >= 'a' && T <= 'z'.

in the second example zy and zz

zz has beauty 0, since there is no i,j such that s[i..j] is strictly larger than t[i..j], because y<z.

Please check the change in the problem statement. It is written in bold.

Well, when this change in the statement has been done? I had no idea about this change until just NOW!

How to prove gcd(i, i+1) =1?

There are 2 cases : 1)if i is even, the i + 1 is odd, 2) if i is odd , then i + 1 is even gcd(even,odd) = 1

incorrect,sorry)

пусть i делится на какое-то простое p, тогда i+1 имеет остаток 1 по модулю p, и так для всех простых для обоих чисел => взаимно просты

because of 1*(i+1) — 1*i = 1

Note: a and b are co-prime if there exists x and y such as a*x+b*y = 1

According to property of

GCD:gcd(a+mb,b)=gcd(a,b)Let

a=1, b=i, m=1, you can get:gcd(1+i,i)=gcd(1,i)=1Each second number is divisible by 2 Each third number is divisible by 3 ...

So the two consecutive numbers can not be the same divisor Sorry for my english

I don't understand test cases in problem C. With input:

2 2 yz

We need strings t with beauty 2. These are ya,yb,...,yy (25 in total) plus az,bz,...,xz (24 in total). Thus, the answer should be 49 but the expected answer is 26. ???

in first example zT where T >= 'a' && T <= 'z'.

notice that only za...zz has beauty 2 lexicographical larger: the first compared char must be strictly larger than the other.

t is larger than s. See the change in the problem statement in bold.

Well, when this change in the statement has been done? I had no idea about this change until just NOW!

Can anyone give me a hint about how to approach problem C in Div2 please?

I would like to attempt to upsolve it, but, I'm totally out of ideas...

Best,

Bruno

Ahhh, Loved it !! #Needed some out-of-box thinking, throughout. #looking Forward.

really fast system testing..:)

Really interesting problems. I expect more contests from you RomaWhite :)

Like this Fast system testing !! :D

Never Do this mistake! Never do! NeveR! [A div 1, segment tree instead of FORs]

P.S: i'm so Idiot!

Can someone tell me how they solved Div2, A?

Oh wait, we could output any matrix right?!

yes>

Matrix with all zeros except on the diagonal, where you output value K

How to solve problem DIV2 D / DIV1 B ??

Plz anyone explain the process how can i solve it with binary search and the logic behind it.

Imagine we have a function f (returning true/false) that tells us whether it's possible to reach some c by changing at most k numbers (that means that after this change, the difference between every two consecutive elements is less than or equal to c). Obviously, when f is true for some c, it's also true for every c2>=c. That means, that we can use binary search to find the "cut-off", the first c for which f is true (which is what we are asked for).

So the last remaining step is to program such function f. We can use dynamic programming — denote dp[i] as the minimal number of changes in elements 0..i so that the difference of every two consecutive elements in range 0..i is at most c AND the last element remains unchanged.

We can calculate dp[i] as a minimum of i (that means we change every value before the currently considered element to the same value) and dp[j]+(i-j-1) for each j smaller than i with the condition that abs(a[j]-a[i]) <= c*(i-j) — that corresponds to remaining the j-th element unchanged and changing every single element in between of i, j.

Then we can determine the minimal number of elements that we need to change as min(dp[i]+(n-i-1)) for each i (we take i-th element as the last that remains unchanged, so we need to change the rest).

why min(dp[i]+(n-i-1)) ? How can we be sure that we need to change all the elements greater than i ?

Please, could anyone write a brief editorial of the contest, I could only solve problem A div1, I am trying to upsolve the other problems and I think many other coders too. thanks in advance.

With a little bit of delay — screencast