Привет всем!
Сегодня состоится 106-й рейтинговый раунд Codeforces для участников Div 2. В нем могут принять участие все желающие. Вам представится возможность вместе с Петей отдохнуть от родителей, узнать несколько интересных фактов о марсианах и конечно порешать, как мы надеемся, интересные задачи для вас.
Этот раунд подготовлен командой из трех человек: Gerald, NALP и Polichka. Мы выражаем огромную благодарность за помощь в подготовке раунда и переводе задач Артему Рахову (RAD), Михаилу Мирзаянову (MikeMirzayanov) и Марии Беловой (Delinur).
Распределение баллов за задачи: 500-1000-1500-2500-2500.
Всем удачи и высокого рейтинга!
UPD: Разбор задач
Люблю контесты) Без них мир бы стал унылым) Спасибо!
I love this normal Score distribution, last contest is really unfair ...
However, i mean 500-1000-1500-2500-2500, not participants rating distribution.
А когда уже будут Div1 раунды?
думаю, фиолетовым и чуть-чуть желтым не стоит возмущаться, так как они врядли решают больше 3х первых задач
Видимо, если бы не Див1 раунды, каждый был бы максимум "фиолетовым и чуть-чуть желтым".
А так Див1 раунд позволяет "фиолетовым и чуть-чуть желтым" доказать, что они нечто большее.
я имел ввиду — 1 раунд можно потерпеть
Прошлый раз, я решил всё за 1.15. Всё зависит от задач.
Видимо он имел в виду первые 3 задачи div-1.
Насколько я понимаю, на Codeforces сейчас очень странная ситуация с раундами. Только я знаю о 4 или 5 группах людей которые что-то делают, а я явно знаю далеко не о всех. При этом видимо нет ни одного раунда в более-мене готовом состоянии.
Может хватит присылать уведомления в 4 ночи/утра? :-)
Их вам приносят и отдают лично, и это вас будит? =)
Приходит на почту письмо, от которого реагирует телефон/будильник. И да, будит.
Гораздо полезнее отправлять письма в момент начала регистрации: и не рано, и зарегаться не забудешь.
а если регистрация начинается в 4 ночи/утра вы опять попросите что-то поменять?
Зачем вы усложняете мою простую идею?
Вот как будет регистрация с 4 утра, так и рассылку будем делать после её открытия, в те же 9.
Выключи спам-рассылку и спи спокойно!
daftcoder дело говорит!
Даешь daftcoder'а в президенты!
good luck everybody
good luck :)
жадность по С проходит?
Если проходит, то не понятно чем эта задача сложнее А
да. но наверно быстрой сортировкой
дабл пост
Скажите, пожалуйста, почему одно и то же решение в g++ даёт TLE, в то время как в Visual C++ заходит? UPD: Имеется ввиду задача B.
Да чёрт возьми! Почему на 14-й тест ("0000P:0000E") локально ответ правильный, а на сервере ВА?
Ясно, возвращается мусор. Прошу прощения за засорение комментариев.
Кто-нибудь взломал что-нибудь по А-С?
в моей комнате был взлом B
4 взлома по А: 12 1 1 1 1 1 1 1 1 1 1 1 1
Можно было ломать B на том, что некоторые проверяли системы счисления только до 35.
ух е-мое... как я про это забыл... столько взломов было потеряно =(
3 взлома по B: ZZZZZ:ZZZZZ, у многих было переполнения int-a при проверке систем счисления до 100.
а я так удачно взломал С, сам не ожидал: начал ломать на быстрой сортировке, сгенерил 10^5 чисел, неверный тест, смотрю, числа до 10^4, а у меня числа от 1 до n, решил на 10^4 чисел попробовать, подумал что успет по времени, но решил рискнуть... по времени все ок — но ва, повезло однако)
Рассудите правильно, в задаче Е написано: "Более формально, марсианин выбирает четыре числа a, b, c, d (1 ≤ a ≤ b < c ≤ d ≤ n) и открывает все глаза с номерами i такими, что a ≤ i ≤ b или c ≤ i ≤ d. После того как марсианин открыл нужные ему глаза, он читает все видимые символы слева направо, получая тем самым какое-то СЛОВО.". У меня в голове только один акцент, на это "слово", т. е. дальше я читаю Выходные данные, где написано: "количество различных красивых СЛОВ", но где он возьмет эти слова, если перед глазами у него слово, мм?
выбирать a,b,c,d он может по разному, получая соответственно разные слова
Подскажите идею динамики в D?
я написал [L,R] динамику, еще 2 параметра: цвета на концах слева и справа
I like the problmsets, thank you, Gerald NALP and Polichka. Wait for the editorial.
How to solve problem D and E? Would someone give me a hint? Thanks.
D: f(i,j,x,y) = number of possible coloring sequence i..j, with i having color x and j having color y
How to deal with the conditions? condition 2: A matched pair can have exactly one color. condition 3: No two neighboring colored brackets have the same color.
In short: when you found some neighbor brackets, check them. When you found 2 matching brackets, check them.
A bit more details (I may forgot some cases): When i and j are matching brackets, f(i,j,x,y) = sum( f(i',j',x',y') )
--> you consider x & y, x & x', y & y' if they satisfies conditions
When i and j are not matching brackets, f(i,j,x,y) = sum( f(i,j',x,x') * (f(j'+1,j,y',y))
--> you consider x' and y' if they satisfies conditions.
for D, my idea was a DP. Scan from left, chose matching brackets. Color them in colors which are allowed, Now rest of string are divided in two parts. Solve them recursively.
Example : (()()()())()()()()(()) gets divided into ()()()() and ()()()()(())
Очень многое узнал для себя на этом раунде. Оказывается, если сабмит получил вердикт "ошибка тестирования" из-за подвисания проверки, то он позднее, после ее возобновления, будет проверен. Это правильно? Потерял из-за этого 2 попытки, так как отправил заново то же самое неверное решение в надежде, что его проверят.
Аналогично. Только совсем такое же самое решение ведь не даст отправить — я добавлял пустую строку.
Ну да, разумеется. Наверное в данной ситуации надпись "в очереди" была бы корректней.
Тоже самое произошло. Возможно ли тогда отменить последнюю отправку, если никаких изменений в коде больше не было?
Как такое теоретически может работать? Динамические массивы инициализируются неинициализированой переменной.
this contest I have the same problem, as last div2: after I submit my hack, nothing happens, and even page doesn't reload, but hack is submitted well
Firefox 10.0, Ubuntu 11.10
Same here (Firefox 11.0 beta, Windows 7).
I failed to submit solution to A at the first time, i.e. I did submit but it seems the server didn't receive it.
Most points from hacks in this round (800)? =D
You were lucky with the room.
Really? I see 10 (more than my successful challenges) unchallenged solutions for problem 2 which failed the system tests (including yours) in your room =)
You are right, I'm just kinda dumb :\
Hey, I didn't mean it like that =/ Also, there were 6 solutions that failed system tests in my room, so I missed a large number of them, I can say I had some luck to have 14 wrong solutions in my room, in that specific problem.
Btw, at first I submitted a solution that gave the wrong answer for 0:10 but it passed pretests, that's why I managed to make so many hacks, because I knew where to look for a specific mistake =)
No, I'm seriously, also, I failed A and B because of time pressure.
Yeah, that happens. It's important to keep calm to make sure we don't slip on the "easy" problems.
What tricky cases (not covered by the pretests) were there in B?
00:10
Not a few people overlooked the fact that the maximum possible base is 59.
Well, I did ;) but failed pretests.
I used Integer.parseInt(String,base) .It failed.Does it check for only bases <=36.If yes,how can I modify it??I know the other approach of finding it by evaluating it bit by bit.Only tell me if I can use the parseInt() function
See this page: http://docs.oracle.com/javase/6/docs/api/java/lang/Integer.html#parseInt(java.lang.String, int)
It does check base <= 36 (Character.MAX_RADIX == 36 in Java 6), and you can't modify it.
I did all my 8 challenges in problem B, the most common one was 0:10 for people that output -1 when it works for base 36 (or some other base < 60). There was one person in my room that checked minutes <= 60, that wasn't covered in the pre-tests either.
EDIT: evima beat me to it =P
отличный раунд (хоть я и посвятил его взломам). отличные задачи. спасибо автору!
Контест непройденного финального тестирования
контест взломов)
и это тоже)
можно было в Е и не включать в претесты случай, когда одна из красивых строк длины 1. было бы весело :)
Two bugs: 1. After hacked i got javascript alert "Undefined" instead of "your solution have been hacked" 2. When i tried to hack other solution nothing happened after giving input and after 10-15 seconds it showed "the solution have been hacked or resubmitted", later in hack page i've seen that my hack was successful.
I experienced the second bug twice. In my case, the first hack was successful, but the second one was ignored (someone was faster).
I got the same message "the solution have been..." regardless of whether the hack was successful.
I got bug1 too. It happened to me last round too I posted it on my blog and nobody replied to me and now same problem still exists.
BTW, there is an O(n log n) algorithm for E. I see that most passed solutions are O(nm). Waiting to see which one is in the editorial ;)
Can anybody please tell more about your O(n log n ) approach for E ?
Let me sketch both approaches.
Let's call the long word s. For every short word w: we are to say whether there is an i such that w[1..i] and w[i+1..end] both occur in s, and w[1..i] occurs before w[i+1..end] (so that they don't overlap). It only makes sense to consider the leftmost occurence of w[1..i], and the rightmost occurence of w[i+1..end]. So we are interested in the values f[i] and g[i], where f[i] is the position of the leftmost occurence of w[1..i] in s, and g[i] is the position of the rightmost occurence of w[i+1..end] in s. Once we have f and g, we can easily check whether there exists an index i such that g[i]-f[i] is large enough (larger or equal to i, I think). And if we have a method of computing f, then we can use it to compute g (it's pretty much just f for both strings (s and w) reversed). So we're left with how to compute f.
The O(nm) approach: search for every word w in s, using KMP. During matching, we virtually get the f[i] array as a byproduct (this is clear if you know how KMP works).
The O(n log n) approach: we use a Suffix Array for s (and s reversed to compute g). There are fast algorithms for SA construction (even linear-time). We also precompute a Range-Minimum-Query structure for the SA. Now how to compute f: for every prefix (starting from i=1), we find the range [a,b] such that sa[a..b] corresponds to the indexes in s which begin with w[1..i]. We compute this range from the previous one using a binary search. We then run an RMQ query on sa[a..b] to find the minimum index (which is the f[i] that we want).
The details can be seen in my solution ;)
You must have come from a parallel universe. Most accepted solutions I saw so far has O(M+N) complexity
Edit: Sorry, I miscalculated :(
O(M+N) really? All I saw ran KMP (or some string matching) for each small string and that would be O(MN)
Is it possible to delete I comment? now my older comment makes no sense :D
You can edit it and write ignore
suffix array?
O(N*logN) is also not a feasible solution since you HAVE to examine the words. So it is at least O(N*logN + M) or more likely O(N*logN + L), where L is the sum of characters in all M words :) (yeah, I know M is usually much smaller than N*logN, just making a note). My solution uses hashes instead of Knuth-Morris-Pratt and also has time complexity of O(N * M). To be honest I'm also curious about the logarithmic solution.
Also, if you use suffix array and then do a binary search in it for each word wouldn't you get time complexity of O(N + M * logN * 1000) or something?
Yes, my algorithm is actually O((n + L) * log n). I'm just treating the value in parentheses as n, since in the problem, L is also <= 100000 ;)
The algorithm can even be made linear-time using very advanced techniques. Not that it would run faster ;)
Задача B почему на тест "0:1N", ответ "23 24 25 26 27 28 29 30 31 32 33 34 35 36 37" — неверный? в тест кейсах ответ "24 25 26 27 28 29 30 31 32 33 34 35 36" не догоняю...
N = 23 -> минимальное основание = 24
Потому что основание системы счисления должно быть строго больше самой большой цифры(а N = 23)
Я дебил просто... в алфавитной строке пропустил 'J' -> и у меня N = 22... UPD: и это закосячилось только на 63м тесте... кто бы мог подумать...)
deleted
Ваше решение выводит 36 чисел,а правильный ответ 58 чисел.
Спасибо, перепутал:)
Y U NO HACK ME :(
Thank you to the codeforces team for that contest. This contest has very good questions and very well pretests.
armin Riiiii*iiii
I would suggest enabling cookies and checking the check-box "log me in for a month".
Hi...my submission ID for problem B is 1168221. My program gave correct output for 1st pretest on my system and also on Ideone.com but it is judged wrong on pretest 1. It is giving an additional output of 23 in the end. Please resolve the issue. :( :(
ignore
it is showing 23 at the end which is not required...please double check it.
Same thing has happened to me also. It has added 23 at the end resulting in pretest:1 failure.
кто-нибудь может подсказать почему в VS у меня ко второй задаче ответ верный выдает на 11 тест, а тут нет?
игнор
@admin . Hello, My submission for Problem B whose id is 1167928 gives correct answer for pretest 1 on my system as well as on ideone.com. My my submission has been judged to be wrong on pretest 1 itself. On codeforces for pretest 1 it outputs an extra 23, but 23 is not printed for the same input on my system and not even on ideone.com. Please look into the matter ans resolve the issue.
I got Judgement Error on my first try (1166157) of 149C - Division into Teams and after I submitted again the same answer, the two submissions were judged as Pretests Passed and I got a -1 because of the resubmission. Can anyone fix the score please?
Марсианские часы: 0000F:0002G
Ответ: 17 18 19 20 21 22
Почему 22?
G = 16 2 = 2; 2G = 22*2+16 = 60
22 не подходит!!!
это ваш ответ. ответ автора на этот тест
17 18 19 20 21
Ой, извините перепутал строчки) И знаки в 2-х местах) Эхх внимательнее надо быть в следующий раз)
@admin:My submission id : 1168245 : It is failing for Pretest1 for Problem B. I am getting correct answer on my machine (using g++ compiler) but when solution is submitted, '23' is additional printed in codeforce's compiler resulting in wrong answer of pretest 1. I see same thing has happened to other person also, who have complained in this forum. Is there bug in codeforce's compiler.Please check
I think it caused by roundoff errors and/or c++ optimization. Those who complained this problem in the forum use the cmath function pow(double,double), which can cause roundoff error in some environment, even though the parameters are integers.
And, when I ran dragonfire's code with some additional std::cout for debug, then extra '23' is disappeared (see my submission: 1170942).
This is sooo strange, but probably it suppressed the compiler optimization and the calculation became correct
What's the proof that makes the solution of taking the odd indexes in a team and the even in the other -after sorting the numbers- work in problem C?
Let a1 >= ... >= an. Then the difference between teams' strength is a1 — a2 + a3 — a4 + a5 — a6 + ... <= a1 — a3 + a3 — a5 + a5 — a7 + ... <= a1.
When will the editorial be available? I'm in very need to it :(
It is already available.
http://www.codeforces.com/blog/entry/3864
Thanks very much :)
You're welcome. :)
Is it possible to arrange some contests on weekends? Looks like the upcoming ones are either on Friday or Monday. Thanks.