Всем привет!
Совсем скоро начнется соревнование Codeforces Round #146. Этот раунд был приготовлен YuukaKazami, MinakoKojima. Я сделал задачи для Div I, а MinakoKojima — для Div II. Как обычно, Gerald очень сильно помог нам в подготовке раунда, давая много советов по задачам. Спасибо ему за это. Традиционно спасибо Михаилу Мирзаянову (MikeMirzayanov) за прекрасные системы Codeforces и Polygon, а также Марии Беловой (Delinur) за перевод задач. Также хочется сказать спасибо donehl за тестирование задач и за его ценные комментарии к задачам.
В обоих дивизионах будет использоваться стандартная разбалловка 500-1000-1500-2000-2500.
Надеюсь вам понравятся задачи! =)
Это перевод оригинального поста автора с английского языка. Английский в комментариях приветствуется.
Прошу прощения за 10-минутную задержку. Мне очень жаль за доставленные неудобства, которые я вызвал. В качестве компенсации, я напишу хороший разбор =)
Orz .. .
sorry for the trouble
Orz WJMZBMR & xiaodao
That would be interesting to participate in contest made by you but unfortunately we have our Moscow ACM ICPC Quarterfinal today at the same time :-(
made in China... hope i can become yellow...
xwlj
Orz
"давая" О_о??? Разве такое слово употребляется?
А что такого? Главное, смысл ясен
Обычное деепричастие. Google не даст соврать.
Мне училка по русскому полчаса на мозг капала, когда я произнес это слово при ней. Это получается как "победю" или "побежду"
Требуй увольнения своей училки. Деепричастие "давая" вполне себе правильное. Нет у него ничего общего с несуществующими словами "победю" и "побежду". Чушь какую-то несешь.
((( заминусили меня
Вроде как ты не прав. UPD. Найдено, что не прав я.
http://gramota.ru/slovari/dic/?lop=x&bts=x&zar=x&ag=x&ab=x&sin=x&lv=x&az=x&pe=x&word=%E4%E0%E2%E0%F2%FC нет, давая есть по второму источнику
Да, ты права. Извините.
Ждем с нетерпением!)
orz
orz！！！！！！！
Надеюсь задачи будут интересными.И хочется пожелать всем удачи и высокого рейтинга.
why isnt the time again as usual ?
Because there is a contest in Codechef tonight, Check here to see more details.
i guess you are right but its a little hard to attend contest in this timing i wish they run in in another day but in the usual time
Usually, contests end at 1:30 Am in China, as I see. Not good for any day :)
2500 people think that time is ok.
3:30 AM in FLorida — US, and it is good for me.
despite this there are a lot of contesters !!
Может хватит "Orz" писать? 5 комментов на одну тему — не много ли?
чувак это китайский контест.
И правда.А я не заметил.
Orz
This time is right!
Good luck to everybody. Have a nice exam.
orz
orz!!
What do these mysterious letters mean? Is it a Chinese word?
http://www.urbandictionary.com/define.php?term=orz
Read here.
Those characters are to depict the begging man, who is standing on his knees and touching the gound with his head.
There are a group of hieroglyph chracters, means "admiration". It is popullar and have been general used in BBS or Microblog around Japan and China.
Thx guys. I found this meaning in wikipedia, but didn't understand. Silly me =D
Now I can see a man.
Let the battle begin
Orz
OMG again 10 mins delay :(
Hey CodeForces, it's 4AM in Brazil and i've been awake since yesterday. =/
I made an alarm to wake up, coz here is morning, if I knew I would'we made it 10 mins later, it would mean a lot to me :D
I suppose it's not so easy to maintain the server. Be patient :)
It is not easy to wait!
I'm very sorry about it...But everything is fine now
That was Snooze
Hope I can become purple.Good luck everyone!
You are purple now.
нельзя так просто взять и не отодвинуть начало
orz....
OMG!!1 Is YuukaKazami a girl?
Sure not.
...Can you see my avatar?...I hope I could be a girl, though...
There are 6 distinct characters in "wjmzbmr". These characters are: "w", "j", "m", "z", "b", "r". So YuukaKazami is a female and you should "CHAT WITH HER!".
lol...So this guy will be fell in love with me again and see a "thin man" in real world~~~
it's a trap.. :p
It's hard to judge whether you're a girl or not through the avatar. ^.^
Too mathy for this morning...
Many many many math to night, I am in american here is 5:55 am.
A, B, C, D — math. E — strings. Very nice problemset, xiaodao, thank you.
UPD: It's not a sarcasm :D
Before end of contest, it was incorrect when you told even so rough classification...
Автор недооценил уровень участников. Не надо нам давать такие легкие проблемсеты, мы не тупые и можем решать задачи посложнее.
толсто)
B слишком сложная для B, но классная
Looks like Petr and tourist couldn't solve Div 2 problem
Maybe they just worked on other high score problems, or challenging.. As a result, they earned more points than anyone who solved C.
Просто праздник взломов! Я взломал 9 решений по С на тесте "12".
16 взломов.
Респект таким парням.
А как решать Б?
Я писал что то ужасное, считал для каждого числа сумму длина отрезка который ее покрывает*веряотность, эту шнягу разбивал на две части, там еще 4 случая есть. Но видимо есть решение попроще.
Да, я тоже пытался вывести пять динамик, считающихся одновременно, но довести это до конца мне не удалось =(
Переход
Где s1 — сума
q_j*j^2s2 — сума
q_js3 — cума
q_j*js4 — сума
q_j*dp[i-j-1]cp — вероятность угадать все
P — вероятность угадать текущую,
где
q_j— вероятнось угадать последних j и не угадать предыдущую.Пусть мы угадали с i-м кликом. Тогда мы добавляем 1 + 2 * (кол-во предыдущих кликов подряд, которые мы тоже угадали). То есть мат ожидание от i-го клика — это pi * (1 + 2 * pi - 1 + 2 * pi - 1 * pi - 2 + ...). Ну а как это пересчитывать за O(1) на клик — очевидно
Храним матожидание количества подряд идущих букв О (обозначим E) и текущий ответ (обозначим А). Переход к следующей клетке делается так. С вероятностью p ответ нужно увеличить 2 * E + 1 (потому что мы уже учли отрезок длины E в ответе, а теперь он стал E + 1), а матожидание на 1. С вероятностью 1 — p мы ничего не делаем.
О, все, теперь понял. Спасибо. Как-то я не с того боку подошел к задаче =(
Так люблю это ощущение — придумать правильное решение за 25 минут, но не быть уверенным в его правильности; написать его с багом; подумать "ну естественно, оно ведь не правильное..." и начать думать в другом направлении; после контеста узнать, что оно правильное, и опять подумать "отлично, у меня была правильная идея, я не совсем тупой"... Наверное, я мазохист.
Спасибо за разбор, в такой формулировке понятней всего.
It seems that system testing hasn't started now.When will it start?
UPD: It has started.
UPD: It seems systest today is very slow.
I love when somebody plays in "Captain Obvious" game for contribution only so much.
Maths Everywhere!
Thank the authors for this intense thinking contest, great work! I wish the editorial would be done soon.
It'll come just today.
Раньше у Codeforces были две традиции: переносить начало контеста и по два часа обновлять рейтинг. Теперь появилась третья: откладывать системное тестирование на неопределенный срок.
Anyone can teach me how to solve "how many times does a string x occur in a string s" as mentioned in the description of Div2 E?I sucked at that point already.
The fastest way is to use Knuth–Morris–Pratt algorithm. Article on Wikipedia
In this problem KMP wouldn't run in time (if you get 10^5 "a" queries on a 10^6 string your running time is 10^11). You need an Aho-Corasick automaton or a suffix array. Or something using hashing.
Nezzar didn't ask, how to solve this problem. He asked just, how to calculate the number of occurences of one string in another.
Just saying that either Aho-Corasick or a suffix array is an out-of-the-box solution for the problem as stated, but without the cyclic rearrangements. To find one string in one other string just once you could certainly use KMP.
systest in 3600 .. 3599 .. 3598 .. 3597 .. 3596 .........
UPD : 3595 .. 3594 .. 3 .. 2 .. 1 .. 0. Systest!
it's better than 7200 .. 7199 .. 7198 .. 7197 ..
3.. 2.. 1.. 0.. -1.. -2...
going back to blue again >_<
Well, I wish to be blue like you.
Me too T_T
When is system testing?I'm worried that my C(Div2) will fail.......
It seems that your solution is correct, because it's identical to mine and I've proved my solution.
Here it is!
Don't worry . It will pass.
Thank you,it got an AC.
Well people system test in two hours, american people go to sleep!!!!
Я осознал, что 1-ую все делали не так как я... Разве не правда, что ответ или n*(n-1)*(n-2)/((n + 1) & 1 + 1), или (n-1)*(n-2)*(n-3)/((n & 1) + 1)?
Input: 10
Answer: 630
Ну в первом случае, я зафиксировал n и n — 1, а затем прогнал 3-е число)
Вроде что-то типа 12 даст 12 11 и 9, но 12 и 9 имеют тройку общую, а значит...
для 12 оно выдаст 11 * 10 * 9
finally starts
Правда ли, что длительность тестирования напрямую зависит только от количества тестов в первых двух задачах?
Seems I just have to wait for the editorial then :D
Is this the slowest systest ever?
That's because there are 100+ test cases for Div.2 B and C
But the number of test cases in each round before are also 100+.
It is.(
ну нахрена в первой 100+ тестов..
А вот как раз за тем, чтобы мы немного подождали.
Very slow judge :(
it's good that problem E & D had less than 3 AC ,so we can imagine there is an end time for this slow system testing !
Problem D Div 2, I has just read some solution, but i can't understand :( Anyone help me please :D
Let E[i, j] be the excepted score for clicks from i to j(inclusive). Let L[i, j] be the excepted 'o' s starts from left, of clicks from i to j. Let R[i, j] be something like L[i, j]. Then we have:
, for any i < k < j.
Think about: If we got x 'o's in clicks [i..k], y 'o's in clicks [k+1..j], then score x^2 is calculated in E[i, k], y^2 in E[k+1, j], and we actually need (x+y)^2 = x^2+y^2+2xy. And since R[i, k] and L[k+1, j] are independent, the 2xy part is calculated as 2 * R[i, k] * L[k+1, j].
Now we take k = j — 1, i = 0, and let e[j] = E[0, j], r[j] = R[0, j]:
What an amazing solution :D
Thank you :)
what a amazing! I only come up with a O(n*n) dp solution.
Me too! I try to DP it but failed :(
I get a TLE in 68th case :(
Of course :D
I have never think like this solution :)
It helps me so much, thank Ray again :)
I got this solution 5 minutes after the contest, saddly. Then I waited hours for the system test to end. Finally I got 1AC.
The evil test case 61 of LCM Challenge :|
8 раз сдавал С, так и не сдал. Оказывается, она падает на n=4. facepalm
В следующий раз потести брутфорсом. На моем компе за секунду получал ответы для n = 1..80. И вообще, полезно иногда потестить там, где реально можно потестить + всегда сомневаться даже в собственных мыслях. + если позволишь, еще совет: когда несколько частных случаев для 4 и более последовательных чисел — заводи массив, чтобы выводить ответ по индексу:
res[n]Ура, хоть какая-то динамика будет в моем рейтинге!)))
2 раза 0, это как?
Как-то так.. http://cs4549.userapi.com/u189814/docs/b49c022129c1/img1FZtiL.gif
А теории графов почему не будет?
sorry for the slow judging...I put too many test in Div2B and Div1A...I didn't expect some solution are too slow T_T...anyway...the judging is done now...
Anyway,I think it's a good contest.I would like also thanks to MinakoKojima for the problems in Div.2.
This contest is very valuable, thanks to YuukaKazami and MinakoKojima. :D
Try to refresh the rating as quick as possible.
I suppose the system is calculating the rating change.
Then why does it take 30 minutes to recalculate it for 2000 people? The complexity is O(n).
good question ! :D
You know how it works? 'Cause i don't.
How slow is that :( I think it's n^3 :)))))
Even it is n^3, it will be done in just one minute.
:-? 2000^3 calculations in just one minutes
Oh yeah, may be n^4 :))))
Ha~~~
But usually it is done in about ten minutes, I think.
Sure it is :D and the rating update has done :D
Egor — the luckiest man of this contest
His E's submission 2402930 is only 14s to the contest end and runs 16ms to the time limit.
Well,He use some interesting strategy to reduce the time, It is just...very good job to do this cool stuff.
I optimized my solution until last possible moment. Actually it runs between 2950-3050 ms on server, so I got lucky indeed
Ratings are now updated. Log off and on to see them.
Can anybody tell me why Div2.C 2398837 is Runtime error on pretest 1. exit code: 13131313 It is at least not throwing any exception in my system. I suspect BigInteger#isProbablePrime but don't know why?
It even shocked me .. The same code run at IDEONE is also throwing Exception http://ideone.com/7efDIa
i don't know java but use throws exception will lead u to correct runtime
you mean main method throws exception like this 2405543 it didn't help ... still same issue. I don't know want is wrong. java experts please help.
I am quite shocked. My following simple Brute Force solution for DIV 2 Problem C:LCM Challenge got Accepted.. :D
This problem is very easy if you think carefully :)
It include 3 cases
1: n odd => result = n * ( n — 1 ) * ( n — 2 );
2: n is not odd and ( n mod 3 = 0 ) => result = ( n — 1 ) * ( n — 2 ) * ( n — 3 );
3: n is not odd and ( n mod 3 <> 0 ) => result = n * ( n — 1 ) * ( n — 3 );
Brute force is quiet "buffalo" for this problem :)
nice observation but can you please provide proof of it
Hi A short-solution programming contest will hold on October 24 at gpac.blog.ir
the link for the tutorial is: http://codeforces.net/blog/entry/5592
Я вот только одного не могу понять в выступлении hariprasath в виртуальном контесте — как можно копипастить коды rng_58 , Petr и hpfdf целых 10 минут, да ещё и ошибиться при посыле задачи А, послав её на В?
А если более серьёзно, я конечно понимаю, что это виртуалка, и никого не волнует, но может принимать какие-то меры против ярковыраженных случаев?
Да, вы как тренер можете перенести его участие в дорешивание. Повторится, будем принимать меры.Ступил, показалось речь о тренировке.А можно поподробнее, как, пожалуйста? Всё что я нашёл, это что я могу так делать в тренировках, но не нашёл как я это могу делать в виртуальных контестах официальных соревнований.
Тесты к задаче B Div2 не всё проверяют.Например: моя программа работает медленно на тестах с большими значениями, но как только я написал тест 100 100 100 как исключение задача прошла.Вывод:тесты к задаче не проверяют её полностью.Можно было бы добавить такие тесты как 99 99 99.Тогда бы участники придумывали более рациональные решения, что несомненно сделало бы задачу более полезной.
А я могу прописать, чтобы на тесте "98 69 83" программа выдавала "-1" вместо ответа. Это авторы тоже должны учесть?
Это учтут ребята из твоей комнаты.
Речь, очевидно, идет о дорешке.
Нет.Я имел ввиду, что если бы авторы добавили тесты с большими значениями, то написать для них ответ было бы трудно.И такие решения как моё не прошли бы.
what does orz mean? and when when will you write editorial? I'm waiting for that :)
Editorial and orz
Before, thinking by myself what could it mean, I realized that orz denotes admiration and they thank the author in this way. But I was wrong, and now I still cannot understand why they are in a quick depression because of the round. Can anybody explain it?
а что такое orz???
Orz