Всем привет!
Очень скоро, 19 мая в 17:00 MSK, состоится очередной Codeforces Round #184 для участников Div. 2. Как обычно, Div. 1 участники смогут поучаствовать в этом раунде вне конкурса.
Задачи были подготовлены группой авторов в составе: Гриднев Виталий (gridnevvvit), Игнатьев Александр (aiMR). Это наш второй раунд, и мы надеемся, что не последний. Выражаем благодарность Геральду Агапову(Gerald) за помощь в подготовке задач, Михаилу Мирзаянову(MikeMirzayanov) за замечательные системы Codeforces и Polygon, Марии Беловой(Delinur) за перевод задач на английский язык.
Мы надеемся, что Вам понравятся наши задачи, и вы получите удовольствие от их решения.
Настоятельно рекомендую Вам прочесть условия всех задач!
Всем удачи и высокого рейтинга!
UPD1: Распределение баллов будет стандартным: 500, 1000, 1500, 2000, 2500.
UPD2: Разбор задач
UPD3: Поздравляем победителей:
I like the previous contest of gridnevvvit. i hope this contest is similar to previous.
window is open, you can easily jump out.
I think it will be interesting. :)
I hope that contest would be easier than last time(181 round)
I'm hope too :D
"Настоятельно рекомендую Вам прочесть условия всех задач!" плагит взятый в Sereja :)
Во-первых, Sereja пишет
Настоятельно рекомендую прочитать условия ВСЕХ задач, что всё-таки отличается от призыва в этом анонсе. Во-вторых, подобные призывы встречались и до того, как Сергей начал проводить контесты. Например, здесь.Даешь динамическую оценку и расположение задач не в порядке возрастания сложности!!!
А чего мелочиться-то? :-)
Даёшь контест без задач!
Шутники разошлись.
two successive rounds that starts at 17:00(MSK) I hope this starting time keeps on.
ухты! Неожиданно!)))
Это уже с Testing Round 6
Ну вот зачем такие огромные скрины делать, растягивая страницу и залазя на прямой эфир? Уменьшил бы в размерах хоть...
Наверно лучше сделать это автоматически, с возможностью увеличивать по клику?
"pretest 3" what a pretest!
Problem A ?... i can't imagine what is wrong in my code :(
in problem A,
it means you cant get sum of (10, 20) but you can get sum of(1,0), (100, 11), ... Maybe it's the 3th test
it says at least so I assumed that if both numbers had a digit that was 0 we could add them.
also what exactly does this refer to?
For each digit p in number a and number b, at least one of a_p and b_p has to be 0.
e.g.: a = a_2 a_1, b = b_2 b_1 => a and b can be added if a_1 equals 0 or b_1 equals 0 (or both) AND [same condition for a_2, b_2] (=> a and b both have 2 digits, so a_2 and b_2 are non-zero => they can not be added)
In problem A, the maximum number of the chosen integers is between 0 & 4. Because if you choose a 2 digit integer, you cant get another one( If you choose another 2 digit number, the first digit of both of them is !0 & you cant sum that pair). And you cant choose more than one of 1 or 3 digit numbers with same reason. So in maximum case, Vasya can choose 4 numbers a,_b_,_c_,_d_, a=="0", b = a one digit integer, c = a 2 digit integer, d = a 3 digit integer & d = "100" Sorry for my terrible English!
this is not always true. what about the input
1 0 0 0? he can choose all the 4 integers!UPD: just re-read the problem statement. the input i mentioned is invalid, because all the integers must be distinct! sorry about that!
I_Love_WJMZBMR
This handle made my day.
Jump from the window.
I do not understand problem A's statement!!! Can Anybody explain to me what problem A means? Thanks in advance.
Problem A is weird.
Can you please explain this test case:
Can you explain with an example?
I thought that having two numbers A and B, then if and only if either of those numbers has at least one digit that is equal to 0, then the two numbers can be added.
So for example 90 18 can be added, 11 99 can not be added and 10 100 can be added.
actually 90 and 18 cannot be added because at 10's place there are 9 and 1 and none of them is 0.
Yeah, this was my worst contest ever, A problem was very strange
It seems like I will never understand what the author wants to get in Problem A. Problem Statement: "...pairs of integers (a, b), such that for any decimal place at least one number has digit 0 in this place ..." Step 2 of tutorial: "If we got number greater than 0 and less than 10, we take it." I really do not understand then test case 2.
The Round #184 is displayed "finished" here. What happen?
The Round #184 is displayed "finished" here. What happen?
what was the pretest 3 in problem A?
Horrible !!!!
What a case is pretest 3 !!!! :/
Очень, очень крутой проблемсет. Давно не получал такого удовольствия от Div. 2 контеста.
В задаче 3 во вкладке "ЗАДАЧИ" контеста отображается TL 0 sec и ML 0 mb **UPD: **уже исправлено
Это значит, что еще не протестировалась.
Нет, здесь http://mirror.codeforces.com/contest/305
This was a hard contest.
Что интересно. Задача B опять заходила на питоне с минимальными усилиями. В комнате у себя видел такое.
worst contest ever for me.... :(
I can't connect to "yandex.st" website. This issue increases time of loading each page to 4-5 minutes for me. I should have waited a long time for reading problems or to see the result of my submitted code during contest. Anybody else having the same problem? Can the moderators fix this?
What? yandex.st?
Codeforces get js from jandex.st. You can view the source code of this page and you can find yandex.st there.
Iraninan users have the same problem, but today I used mozilla and I didn't have the problem
I think in these cases, you should go to codeforces.com through a proxy, just a simple proxy could be fine since we don't need any JS in codeforces ;) : here is mine : www.jabeja.tk/p/index.php
http://saveimg.ru/show-image.php?id=31a2f20b88c0b681a46d99ce0314ec9a Что это за баг по задаче С по времени и памяти???
Ссылка кривая
исправил
ideas for solving C ??
Think of the binary representation of the sum and the binary representation of a 2^v -1 decimal number.
2^V-1=2^0+2^1+2^2+...+2^v-1 if array consist of distinict elements ans=MAX(a1,a2,...an)+1-n; there is only one problem if you have same powers in array.In this situation you need to transform your powers in such way that get distinict powers, for example: if you have 2^8,2^8,2^8 you can tranform it and get 10^8,10^9 if you have 2^4,2^4 you can tranform it and get 2^5
sorry for my poor english
2^0 + 2^1 + . . . + 2^n = (2^(n+1)) — 1 Your task was just to find the biggest power of 2 and count how many of the powers from 0 to the biggest are not shown in the sequence. but dont forget to change two a s to one a + 1 for example : 2^3 + 2^3 = 2^4...
During system testing it showed that my C got accepted. Now, it shows that it failed on test case 26. What happened?
It was retested, but i don't know the reason
Maybe they saw my solution and decided to add a new case. :(
Dynamic scoring would work better!
How to use long arithmetic in this solution?
Don't think you eally need it. What about d=gcd(p,q); p=p/d;q=q/d? :)
WA43. I think that we need long arithmetic because of p = big prime number and q = big prime number => their gcd equal to 1 and it doesn't change our p and q.
I am not talking about overflow. For example you have p=100, q=50. And your algo will find Pn=2 and Qn=1 which is quite the same.
And another question. Why thistakes AC and WA43? What is the difference?
In first one you use BigInteger by default so it is OK.
Can someone please explain this testcase for problem A: Input: 2 1 2 Output: 1 1
consider answers: (0), (1 1), (1, 2), if you can choose (0), you can choose(1 1), in both answers you couldn't choose two numbers that can add together.
Could someone, please, help me? I can't find mistake in my solution for C problem. Here is my code.
I think you need to delete (or count) elements that become 0 again.
Oh, damn. You're right, thank you! Such a stupid mistake :)
cool bug in the codeforces! http://nic.p.ht/up/c70903297fe1.png
it means that your solutions is in a queue and not now accepted :)
But I didn't pass the pretest of problem C :(
Jump from the window.
Conteste fogholade chert!! Maskhare bud...
what!?!?
http://translate.google.com/
Kudos to problemsetter for D. A really nice problem, in how a lengthy statement with many conditions can be visualized in a way that leads to a simple solution (although with several special cases to be checked).
To explain what I mean, my solution:
it's clear that the original graph, as well as any target graph, must be a DAG without multiple edges
the first condition for the target graph means that it contains a directed path through vertices 1->2->3->...->N; then, the 4th condition means that between any 2 corresponding vertices, there is no other (shorter) path, so "any edge from vertex i must lead to vertex i+1 or at least i+K+1"
the 5th condition boosts this to "any edge from vertex i must lead to vertex i+1 or exactly i+K+1"; you may view the graph as an incomplete cycle with additional "bowstring" edges
the 5th condition also implies that if there's a vertex i (with the smallest possible i) in any target graph that there's a bowstring edge from i to i+K+1, then all other bowstring edges may only lead from vertices i+1..i+K to the corresponding +K+1 vertices (if these exist); these conditions are also sufficient for any target graph
so if the input graph contains an edge from i to neither i+1 nor i+K+1, the answer is 0; similarly if there're 2 bowstrings i->i+K+1 and j->j+K+1 such that j >= i+K+1
if those conditions aren't satisfied, we must add all edges i->i+1 and then we can choose a suitable first bowstring edge (if the first bowstring in the original graph is a->a+K+1 and the last one is b->b+K+1, then the chosen first one must start at vertex at least b-K and at most a, inclusive, but also at vertex at least 1 and at most N-K-1, obviously); iterate over all those possibilities, or over all vertices from 1 to N-K-1 if there's no bowstring in the original graph
if we've chosen the first bowstring from i to i+K+1, the answer is 2^(maximum number of bowstrings we can add-number of bowstrings already starting at vertices between i+1 and i+K in the initial graph); the second part of the exponent is fixed due to all bowstrings having to start at vertices i+1..i+K, and the first is simple min(K,N-K-1-i) when indexing vertices from 1
precompute powers of 2 up to 2^K; then simply iterate over all possibilities and add them to get the answer
Details are skipped, feel free to ask if you find something lacking. Code: 3746010
Thanks. I am a setter of this problem, but there was another statement. There were no initial edges in graph. But Gerald gived idea to add initial edges in graph
Не совсем понятное условие в задаче А.
for problem a test 3, the array of my output is :
[70, 40, 30, 100, 50, 60, 0, 16]
why it's get WA, if we sum from 70 until 0, the total is 350, and 350 + 16 is valid operation, i think...
thx
30, 40, 50, 60 and 70 can't be in the same output. Vasya can only sum pairs of integers (a, b), such that for any decimal place at least one number has digit 0 in this place
In the second decimal place, none of them has 0
You cannot sum 40 and 30, for example
why ? isn't one of them has digit 0 ?
"Vasya can only sum pairs of integers (a, b), such that for any decimal place at least one number has digit 0 in this place."
oohhh, took so long to understand that important sentence,
at first glance what crossed in my mind is, vasya can sum pair of integer (a,b) if a has at least one 0 or b has at least one 0
I made the same mistake and got two wrong answers. Two of my friends also misunderstood the statement. I think it would be better if there were more clear examples or sample tests
I wonder why updating ratings takes a lot of time!
Checking solutions is a way easier problem than updating the ratings I guess
You know, they have to change colors of nicknames at every single subdirectory. Manually. It takes time.
In Problem A. How can a single number form a pair?
We're looking for such numbers that if we choose any pair, their addition is allowed. But if there's just 1 number, there are no pairs, so we never get a situation which is not allowed, so 1 number is a valid output :D
Vasya wants to choose some integers from this set so that he could sum any two chosen numbers.
But the set dosn't contain two numbers! So the output cannot be a single number i guess.
Read "so that he can sum any 2 chosen numbers" as "there are no 2 chosen numbers that he can't sum". 1 number satisfies that.
I think sometimes CF expects us to read the mind of the problem setter. :/ no more arguing.
Sorry, but that's the standard convention in mathematics. I've encountered it several times (once with the warning that the problem statement uses strict mathematical logic :D).
hang yourself
taking long time to update ratings!!!
Congratulations!:)
Rating?
The contest time is too early for me! It's better if the contest starts two or three hours later.
Yeah, For me too!
Пора ввести регистрацию с прикреплением номера мобильного телефона к аккаунту, надоели эти бесконечные черные с одинаковыми никами.
The best contest ever... Problem C was easier than A!
Повесься
what does it mean?? "Повесься"
Дорогие организаторы! Обратите внимание, что в задаче А было написано, что все числа разные, но были успешные взломы используя такие тесты. 3 0 100 100. Решите эту проблему. Спасибо!
Приведите пример, пожалуйста.
UPD: Если вы про взлом # 71197, то 3 0 100 100 — это вывод участника, а не тест.
Извиняусь!
hang yourself