| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | nor | 152 |
Разрешите от всей души поприветствовать вас на Codeforces Beta Round #11. Я основной автор этого контеста. Надеюсь, что вам понравятся подготовленные задачи :-)
Спасибо Mike Mirzayanov'у за то, что возможность проведения контеста и Ania Piekarska за тестирование задач.
Удачи, Jakub Pachocki
Это перевод оригинального поста, поэтому английский в комментариях приветствуется [примечание переводчика].
Анонс Codeforces Beta Round 11
везде "блог" написан 4 раза, даже наверху, где "главная"
в прямом эфире тоже всё по 4 раза :)
а, кстати, стоило бы запретить копипастить код другого участника
ибо образовательного процесса в копипасте ноль, а тупо перепечатывать код уже не так интересно (вряд ли кто-то этим будет заниматься), и потенциальный читер не поставит себе в голове галочку типа "я сдал эту задачу"
В чем проблема? Пусть ставит галочек, сколько хочет. Это ж в рейтинг не идет. Если кому-то хочется посылать уже готовые решения, это его проблемы.
А вот мне иногда хотелось бы прогнать чье-то решение на моих тестах.
а как же процесс "подумать"? он более чем полезен для начинающих
а чужой код не обязательно копипастить; для того, чтобы чему-то научиться, достаточно read only
I really liked problem E. I haven't solved it and maybe even far from complete solution yet, but solving it was very interesting.
after 6 years of you comment i want to said to you that i facing the same problem :D
Большинство на нем падали :(
Надо по-другому решить задачу. Я тоже на нем упал по-началу. Потом применил формулу суммы арифметической прогрессии и сравнивал с abs(x).
There seems to be no editorial for this round or description of how to do this problem, so I will post my solution here.
My solution involved adding X's so that every L and R in the original string was correct (if a character was bad I would add an X right before it). However, sometimes it is suboptimal to add this many. If I added two X's, and there was exactly one L or R between them, then removing them removes two bad characters (those X's), but changes one good character (the one between them) to a bad character, and leaves the rest of the string unaffected, which is a net decrease by one for both correct and incorrect characters, and this is a good move to make if the answer is above 50%. This can be done by just looking through the list of positions where I added X's, with a few extra checks to ensure that there are never two of the same step adjacent to each other. Code
does petr reply only to red coders ?
nope
Let n be a positive integer. Consider any k such that 1 + 2 + ... + k >= n. Then n is reachable in k jumps if there is a subset A of {1, 2, ..., k}, such that when we make all jumps from A go left and all jumps not from A go right, we reach n. This is equivalent to k(k + 1)/2 - 2 * (sum of numbers in A) = n. It's very easy to prove that the sum of numbers in A can be any number between 0 and k(k + 1)/2, so it's possible to reach n iff the difference between k(k + 1)/2 and n is even.
И никакой информации о изменении длительности контеста.
А информация о изменении времени начала и продолжительности, наверное должна быть хотя бы в теме посвященной контесту.
Хотелось хотя бы около 1.5 часов порешать)
Лично мне вчера пришло письмо, в котором оповещалось об 11-ом раунде. Там были такие строки:
"На сайте некоторое время назад было опубликовано, что продолжительность контеста составит 2 часа 30 минут, но после пересмотра заданий соревнования было решено не менять формат и сохранить "стандартную" длительность 2 часа."
Вроде и сегодня еще было 2:30 часа. Хотя может я был не очень внимательным, и просто не ожидал замены)
Странно получилось, за 2 секунды до конца отправил решение задачи C, но оно, как выяснилось не отправилось, при этом никаких уведомлений об этом не было. А потом, когда отправил в дорешивании, оказалось, что решение правильное... Обидно, что из-за багов системы не сдаются задачи...
На самом деле сайт достаточно часто виснет, за первые пять минут я даже не смог открыть условия задач, аналогичная ситуация наблюдалась в последние секунды контеста и сразу после него, на сайт просто не заходило, причем я пробовал с разных браузеров (Opera, IE, FireFox). Поэтому я думаю, что проблема все-таки не в таймере из браузере.
Сохрани сессию (сохранить сеанс), закрой все окна (не по одному, конечно =) =)) и работай в чистом окне на здоровье. =)
А потом сеанс сможешь восстановить.
На 12-ый раунд зарегестрировано несколько синих. Наверно, это вызвано тем, что регистрация на 12-ый раунд началась до завершения 11-го. :-)
Это который 12й? Или 14й? =)
Ну вот напишу 13й контест, попаду во 2й див и напишу 14й.
Хотя может он 13й и несчастливый и я не попаду во 2й див.
http://informatics.mccme.ru/moodle/mod/statements/view3.php?id=477&chapterid=77
и разбор:
http://informatics.mccme.ru/moodle/mod/book/view.php?id=489
а вообще весьма странно что подобные вещи плохо в инете находятся... или я плохо ищу))
самому что ли сделать доброе дело - накатать статью :D (а если потом ее кто нибудь переведет на английский - будет совсем замечательно)
I have problem in my head or codeforce has problem in its head....
my contest code of B got WA in test 4 using scanf and printf
but in practice same code got AC using cin and cout?
is there any explanation anyone can give?
here is my WA in test 4 code
http://pastebin.com/cbBH5nzz
if u replace scanf("%lld",&num)==1 with cin>>num and printf("%lld\n",i) with cout<<i<<endl; it gets AC ...
As you can see there is an 2005 MSVS compiler and it doesn't work with %lld, but with %I64d!
Or you can just make all variable int (it's enough) and use %d.
I tested it just now.
I'm wrong. (c)
From 2005 version VS supports both %I64d and %lld.
Также для нулей.
Теперь проверить, что у нас квадрат легко - просто сравниваем количество единиц. Проверить, что он не касается ничего тоже не сложно - проверяем, что вдоль наших сторон количество нулей достаточное.
Кодяки правда надо атата скока :о(
Этот - это мой
http://codeforces.me/blog/entry/331#comment-4127
Попробуйте отсортировать по разным параметрам. Например, по времени сдачи — обычно самые лучшие и сдают раньше.
Хотя это, конечно, хак. Должна быть возможность хотя бы перелистывать страницы и фильтровать по языку.
Thanks for the problems, but I'd like to pay attention to some inaccuracies in them.
1. B: "He can go either left or right with each jump." One may think that Jack can go either left or right from his point of view. For example, going left and then right would move him (0,0) -> (-1,0) -> (-1, 1). That will make the problem two-dimensional and thus much more complicated. A friend of mine spent much time until he realized his mistake. It would be better to write something like "He can go either back or forth with each jump."
2. C. What is a diagonal of a non-square matrix? It is a rarely used term, at least I've hardly found a mention of it only on the second page of Google's result. It would be much better if the definition of this term was given in the problem. It requires only a sentence or two, but clarifies the problem.
3. C. "a square must contain at least one 1 and can't touch (by side or corner) any foreign 1". What does "foreign" mean here? Is it a "1" which doesn't belong to this square or to any square?
4. Also "a square must contain at least one 1", but earlier "A square should be at least 2×2". I understand, that there is no contradiction, but why increasing the confusion?
Thanks.
For example: the authors should explain why the result is 1 for the 1st test case, 2 for the 2nd test case... for the problem C.
You mean explain withit problem statement?
If yes, I'll agree with you.
For example. If you want to reach 10^9 position, in some you'll be near it. Let it be a 10^8 position (of course the real position place will be close to 10^9, you can prove it yourself). So we need to compute 10^8 cells. It takes more than 1 sec time. :(
And you need about 120 MB to store billion length bool array.
Maybe there is a much better DP solution, and maybe even it got AC, but i solved that with little formula and very little bruteforce (most of participants use only brute).
If you request a code you can get it there - http://codeforces.me/contest/11/status/B?order=BY_ARRIVED_ASC
I am new to programming. The people have solved problem D quite easily as it is quite trivial for them. I am not able to understand how they are solving using DP. what is the subproblem. I have spent 3-4 days trying to understand the solutions but no success. Can anyone help ? I will be grateful for the same
#include<cstdio>
int main()
{
int x, i = -1, y, fl = 1;
scanf("%d", &x);
if (x < 0) x *= -1;
while (fl) if ((++i * (i + 1) / 2) >= x && (x + (i * (i + 1) / 2)) % 2 == 0) printf("%d", i), fl = 0;
return 0;
}
Can someone explain how to solve B? I saw people using logic
while (sum<x || (sum-x)%2==1) {ans++; sum+=ans;}, what is the logic behind(sum-x)%2==1?Let us suppose you take j jumps to reach some point y where y >= 0. Let us suppose you took some forward and some backward jumps. Clearly, we can write : 1. (sum of forward jumps) — (sum of backward jumps) = y ...equation(i) 2. (sum of forward jumps) + (sum of backward jumps) = j(j+1)/2 .... equation(ii)
Combine both to get: j(j+1)/2 — 2(sum of backward jumps) = y
The above equation is the key. [Note : sum of backward jumps -> is the sum of some elements from the set {1,2..,j} which can take any value between 0 to j*(j+1)/2 ..not too difficult to prove]
Hence, if (j(j+1)/2 — y) is even and (j(j+1)/2-y)/2 lies in the range [0,j(j+1)/2] then clearly we can reach y in j moves. Hope it is clear!!
I will try my best to explain the my approach on problem 11D without using sum of subsets dp. Denote
d[last][mask]as the number of ways to form a chain consists of every elements with its bit on in the mask, the first bit (first_bit) in mask is the head of the chain (we are fixing the order of the cycle) andlastis the last element in the chain. The transition is easy, take every possiblenextbit that satisfiesnext > first_bit,nextdoesn't appear in the current mask,nextandlastshare an edge andd[next][mask^(1 << next)] += d[last][mask]. Check through every dp state that there is an edge betweenlastandfirst_bitand add them to the final answer. Finally divide the answer by 2 as we repeated the calculation in the last step.My submission: 79403398.