Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов.
→ Обратите внимание
До соревнования
Codeforces Round 976 (Div. 2) and Divide By Zero 9.0
16:10:39
Зарегистрироваться »
Codeforces Round 976 (Div. 2) and Divide By Zero 9.0
16:10:39
Зарегистрироваться »
*есть доп. регистрация
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3839 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3612 |
| 7 | Geothermal | 3569 |
| 7 | cnnfls_csy | 3569 |
| 9 | ecnerwala | 3494 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 164 |
| 2 | maomao90 | 160 |
| 3 | -is-this-fft- | 159 |
| 4 | atcoder_official | 158 |
| 4 | awoo | 158 |
| 4 | cry | 158 |
| 7 | adamant | 155 |
| 8 | nor | 154 |
| 9 | TheScrasse | 151 |
| 9 | maroonrk | 151 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 29.09.2024 02:24:22 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
Seriously, why bother and hold a Code Jam World Finals every year? they can simply give it to tourist. Wouldn't that be easier? :D
It's for others to compete for the second place of course.
Well, now it makes much more sense :D
Then, kevinsogo is considered as the winner of the Codejam 2016 World Final! :D
Interesting things I noticed during the Live Stream :-
Anyway, the live stream was pretty bad!
The arena was dimly lit for some reason. Also, they only showed tourist's monitor throughout the contest, and said they didn't make arrangements for others' screens. Towards the end of the contest I really wanted to see what kevinsogo and Egor were working on since the scoreboard was so close! There were tedious and long breaks in the stream very frequently as well. They should really show somebody's screen during those breaks instead of playing pathetic music :P
Wut is weird with those things? Everyone sometimes needs a magic number and giving stupid names to files is also rather common. I for example sometimes name files like "ass.cpp" or "nothing" (but in Polish). Just because tourist did this doesn't make that fact extraordinary :P.
Sometimes I want to create a file
nic.cpp(what means "nothing" in Polish) but it already exists so I createnothing.cpp. I will burn in hell for programmers.I usually just give up after checking meow.cpp, meow2.cpp and meow3.cpp and realizing they are all in use.
Lol I use meow.cpp too. But now that I have meow, meow2, meow3 already in use, I type meowX where X is some random number as the file name xD
I think stupid.cpp is not just a random stupid name. It means a stupid solution (for a small input, for example).
Swistakk, I never said that it's weird or extraordinary. For E in the codejam finals, he was tweaking his MAGIC and staring at outputs. He submitted large input with only a few minutes to go. Most people (including the panel) did not expect it to pass, but it did xD
It's very common for tourist to submit his last solution with only a few minutes to go. It's a good strategy, he knows he doesn't have time to code anything else so he might as well make sure his solution is correct.
In this specific case, although his approach for problem E is the simplest (conceptually), it looks really difficult to get precise enough. He must have had a feeling for those magic constants!
The improvement in kevinsogo's performance is quite remarkable from 26th last year to 2nd this year
yeah 26th in GCJ finals is such a terrible result.
When your peers are like Egor and rng_58, it's motherofgod88 result!
As there was no analysis of the finals (sadly), I am asking here. Can anyone explain the idea behind the first problem? The statement is beautifully simple: given a regular expression describing integers, count how many integers there are <= N, which match the pattern.
I remember finite automata and regular expressions from CS classes fairly well, but haven't come up with a good idea to efficiently solve this problem, because N can be huge, up to 10^18. For small N I could just implement the RE as a FA and try one by one. For bigger N... maybe the pumping lemma comes into play, but I don't see how.
Just the main idea or even a hint would be great; I don't want to start reading solutions without trying a bit more first. Thanks!
The main idea is pretty simple: use dynamic programming over digits, and have one parameter denote the current state of the automata.
Edit: Also note that they gave solution ideas in the live stream: this problem.
Thank you! That tells me exactly what to do. Great idea.
Now I'm reviewing in my mind the process of (a) RE parsing, (b) RE->NFA and (c) RE->DFA conversion, which, although algorithmically straightforward, I cannot imagine how someone programmed all of those things PLUS the DP in about an hour.
RE parsing is simple in this specific case because all operators are necessarily grouped by brackets, so whenever you meet an opening bracket you just need to check if there's a * after the closing bracket and you know if the operator is * or |. NFA->DFA conversion is not complicated because all you need to do is keep a subset of states of the NFA you could be in and you automatically get the DFA without having to actually do the conversion.
RE->NFA is the really difficult part, and what I had to spend about an hour debugging during the competition -.-'
How does one ensure that the duplication is taken care of? For e.g., given a regular expression (12|34|56)*(123|456)* , there are two ways to arrive at 123456. Through the DP, we can be sure that the same number will not be arrived at through the same state more than once, but some other set of states could give the same result. How to avoid that?
This is only an issue if you're working with an NFA. But if you first turn it into a DFA (or keep a subset of the states as a DP parameter), then that won't be an issue. The length of the expression is small enough to allow 2^(number of states).
The trick is to count valid arrangements of digits using DP. A more detailed explanation of this approach: https://stackoverflow.com/questions/22394257/how-to-count-integers-between-large-a-and-b-with-a-certain-property/22394258#22394258