Всем привет!
Скоро, 10 ноября в 21.00 MSK состоится Codeforces Round #210 и его автором буду я.
Это мой первый раунд на Codeforces и я очень надеюсь, что все пройдет хорошо. Спасибо Геральду Агапову (Gerald) и Виталию Аксенову(Aksenov239) за помощь в подготовке раунда.
Удачи!
UPD.
Разбалловка в первом дивизионе: 500-1000-1500-1500-2000.
Разбалловка во втором дивизионе: 500-1000-1500-2000-2500.
UPD.
Поздравляем победителей!
Первый дивизион:
Второй дивизион:
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
Поздравляю с дебютом!
Среди львовских авторов — пополнение) Надеюсь, все пройдет гладко.
4 соревнования для div2 почти за неделю — супер! Так держать!
новый автор = интересный контест)) ура!!!
Glad to see a very full 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 contest will 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... :S
This 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.
Как решать Д (див. 2)
я пытался бин поиск по ответу пропихнуть... но под конец понял, что проверяю правильность ответа не правильно. Скорее всего идею с бин поиском можно реализовать
Бин поиск по ответу, проверка ответа динамикой...
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)=1
Each 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 :)
Обидно одним из первых решить А и завалить время на В. :(
Аналогично. На первой минуте сдал А и пока возился над всеми задачами по очереди, вернулся к В на 55-ой минуте и за 25 минут решил.
Never Do this mistake! Never do! NeveR! [A div 1, segment tree instead of FORs]
P.S: i'm so Idiot!
Не в моем случае жаловаться конечно, но diff WA10 на контесте и OK в дорешке вызывает прилипание руки к лицу.
А что там? За О(1) не нашел, многобукаф.
Граф ориентированный. :(
Can someone tell me how they solved Div2, A?
Oh wait, we could output any matrix right?!
yes>
Прочитал в B "сумма" вместо "максимум", весь контест решал не ту задачу. И даже почти решил.
Все-таки три контеста в день -- это слишком.
Аналогично. Только после прочтение этого комента это заметил(
Ребят, после решения задачи А (DIV 2), стало интересно,
Дано число n и k
Нужно вывести любую последовательность из n чисел, что бы их сумма была равна k
Например:
n = 7; k = 10;
1 + 0 + 2 + 1 + 1 + 3 + 2 = 10
у меня не получается так сделать, помогите пожалуйста.
ах да, забыл добавить, что цифру 0, можно использовать только 1 раз.
Заметим, что минимальное число, которое мы можем получить из n слагаемых равно
0 + 1 + 1 + ... + 1 = 0 + 1 * (n-1) = n-1
тогда, если k < n-1, то решений нет, иначе построим ответ так:
0 + 1 + 1 + ... + 1 + (k-(n-2)) = n-2 + k-n + 2 = k
Слагаемые: [0, 1, 1, 1, ..., k-n + 2]
Еще, наверное, надо рассмотреть отдельно случай n = 1
Может кто-то объяснить С(Div2)? Как её решать не за n*m?(без деревьев)
How to solve problem DIV2 D / DIV1 B ??
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).
Can you tell me how to solve div2-D problem????
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