### gen's blog

By gen, 7 years ago, ,

Hello everyone!

Codeforces Round #142 will be held today at 19:30 in Moscow time, and it will take place in both divisions.

The authors of the problems are me, Evgeny Vihrov (gen), and Andrey Vihrov (andreyv). Both of us are students of the Faculty of Computing in the University of Latvia. This is our very first contest on Codeforces!

Big thanks for the help in preparing the contest go to Gerald Agapov (Gerald), and to Maria Belova (Delinur) — for translating the problem statements in English. Also thanks to Mikhail Mirzayanov (MikeMirzayanov) for the Polygon system, which we found to be great for preparing contest problems.

We hope that each participant will be able find a problem to match his taste. Please, consider reading all the problems!

We wish you an exciting round!

UPD1: The score distribution will be dynamic. The problems will be sorted in order of expected increasing difficulty.

UPD2: Due to the technical problems the contest was extended by 5 minutes. We are sorry for the inconvinience.

UPD3: The analysis of the contest is available. Enjoy!

The round is over! 5 contestants solved all the problems in division 1, and in division 2 only the top four contestants solved all the tasks. Congratulations to the winners!

#### Div II

•
• +175
•

 » 7 years ago, # |   -16 this is the last contest at the 'Contests' page. again:-( so, approximately in 7.5 hours the list will be empty. makes me sad so much!
 » 7 years ago, # |   -33 Плохо что добавили 5 минут, а сайт висел минут 10! + лаги
 » 7 years ago, # |   -7 я не пойму, С что ли баян какой-то??? почему многие сдавали ее в первые 20 минут, и некоторые с див2 на 11 минуте ее сдавали?? как она решается? и правильно я понимаю, что кто знал идею — немного додумывали и профит?
•  » » 7 years ago, # ^ | ← Rev. 2 →   -11 Nevermind.
•  » » 7 years ago, # ^ | ← Rev. 3 →   +2 Sorry, bug with language.C is cool, thx 2 authors.
•  » » 7 years ago, # ^ |   -17 dangerous, вы читаете мои мысли
•  » » 7 years ago, # ^ |   -6 Задача становится лёгкой, как только подумаешь, а не подсчитать ли количество разноцветных треугольников.(The task C is a easy, when you will try to count the number of colorful triangles.)
•  » » » 7 years ago, # ^ |   -24 разноцветных по ребрам что ли?
•  » » 7 years ago, # ^ |   -13 Я на месте придумал. Ответ — . Чтобы это понять, надо удвидеть, что бывают 4 картинки на трех вершинах. И в указанной сумме квадратов две нужные учтутся с коэффициентом 3, а не нужные — 1.
•  » » 7 years ago, # ^ |   0 все довольно просто же. сначала прибавим к ответу все треугольники. потом, для каждого ребра Элис вычтем из ответа n-2. Потом для каждой вершины прибавим к ответу C(cnt, 2). Можно убедиться, что его мы не посчитали ни одного разноцветного цикла, а все одноцветные посчитали ровно 1 раз.
•  » » » 7 years ago, # ^ |   -29 ля, ну баянистая же идея, как я не вспомнил подумать в этом направлении...
•  » » 7 years ago, # ^ |   +3 И вообще это английский тред, что и вызывает кучу минусов.(And this is an English thread, which is also the reason for minuses I suppose.)
•  » » 7 years ago, # ^ |   +2 Давайте решать так. Сначала посчитаем сколько всего треугольников в графе у Боба. Будем добавлять ребра по одному и смотреть, сколько треугольников даное ребро отняло у графа Боба. Пусть ребро исходит из v1 в v2, всего мы до рассмотрения текущего ребра добавили s1 ребер с вершиной v1, и s2 с вершиной v2. Тогда логично, что текущее ребро отнимет от графа Боба (n-2-(s1+s2-мощность пересечения множеств уже добавленных соседей для v1 и v2)). Заметим, что вот эти вот общие вершины образуют треугольники с v1 и v2 в графе Алисы, а больше никакие другие вершины не образуют(на текущем этапе). А значит, можно просто не отнимать их, но и в конце не добавлять треугольники в графе Алисы. Очень крутая задача, ИМХО.
 » 7 years ago, # |   -17 Very annoying contest.
 » 7 years ago, # |   -12 Итак. Задача D div 2 (B div 1). Писал Дейсктру. Обновлял путь таким образом: брал за растрояние минимальный момент времени такой, что "В этот момент времени можно вылететь с планеты", с учетом того, что в последнюю планету растоянием называлось "время прибытия". Что не так?
•  » » 7 years ago, # ^ |   0 2 1 1 2 1 2 0 1 4 0 1 2 3 
•  » » » 7 years ago, # ^ | ← Rev. 4 →   0 Спасибо. Именно это у меня и не было учтено. Будет совсем обидно, если в дорешке сразу зайдет с исправлением этого бага (не учел, что из первой вершины не всегда удается отправиться в нулевой момент времени)UPD. Не совсем обидно, схватил еще и тл. От которого легко избавиться
 » 7 years ago, # | ← Rev. 2 →   -9 Rating will be update?
 » 7 years ago, # | ← Rev. 2 →   +6 I want to thank codeforces for making me understand all sort of network errors that can happen :P This would help me in future.PS : Translation errors were like ice on the cake... One amusing error : "All those errors belong to me" , This was the real culprit.
 » 7 years ago, # |   +5 who can you tell me solution problem E div 2? thanks you
•  » » 7 years ago, # ^ |   +9 Look at what kuniavski said.
 » 7 years ago, # |   -22 Don't Rank this Contest due to System problems.
 » 7 years ago, # | ← Rev. 3 →   0 [user: dangerous]
•  » » 7 years ago, # ^ |   0 че за трэш?
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 как написать твой ник?how to write your handle?
•  » » 7 years ago, # ^ |   0 Yep, at least I can do so: _dangerous_ \_dangerous\_
•  » » » 7 years ago, # ^ |   0 it doesnt work
•  » » » » 7 years ago, # ^ |   0 Yes, that's why I said at least ;)
 » 7 years ago, # |   +40 Please tick "In Russian" if you don't write in English :)
 » 7 years ago, # |   +5 It seems that in problem C div1 (triangles) any solution using cin instead of scanf that doesn't have the line "ios_base::sync_with_stdio(0);" gets TLE. I thought timelimits were chosen to allow users using iostream... Is this true?
•  » » 7 years ago, # ^ |   0 I've just submitted a solution that got TLE during the competition and it has been accepted changing only cin with scanf.
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 When there is large I/O(About 100000 or more), you can't use cin/cout without ios::sync_with_stdio(false). Scanf/Printf are OK, but sometimes you should use "getchar" to make it faster.
 » 7 years ago, # | ← Rev. 2 →   0 Great contest! Does pretest 10 contain maxtest? I have 1.6 secs on pretests with solution with 10^6 vectors. Another 10 seconds and I would have submitted fast solution with lists. And I'm really nervous now :)
•  » » 7 years ago, # ^ |   +3 And after all, it accepted! Runtime is still 1.6 secs after systests
 » 7 years ago, # |   +8 Slow system testing :\ Great competition though, there were some techincal problems at the end but i think extending the contest was a wise decision :P
 » 7 years ago, # |   0
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 I suppose that it's cycles over array t.
•  » » » 7 years ago, # ^ |   -8 но это же всего константа. Очевидно, что он не более 1 раза пройдет по массиву t. итого: 10^5. Неужели для кодфорса это критично???
•  » » » » 7 years ago, # ^ |   0 It's O(n^2) when all edges are from vertex 0, and everebody comes to 0.
•  » » » » 7 years ago, # ^ |   0 In the worst case you will go over array t[u] for every edge v->u.
 » 7 years ago, # |   +5 I believe D can be solved in O(n log n), was it on purpose that the limit is low or the authors weren't aware of such a solution?
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 Isn't that the original solution? Using djikstra with Heap? (sorry thought its div2)
•  » » » 7 years ago, # ^ |   0 D in Div 1?
•  » » » » 7 years ago, # ^ |   +1 Nevermind i thought you meant Div2
•  » » 7 years ago, # ^ |   +11 It can be solved in O(n).
•  » » » 7 years ago, # ^ |   0 You don't use dijkstra with heap? Another solution? Can you share it?
•  » » » » 7 years ago, # ^ |   0 Sorry,i meant Div1. Towers
 » 7 years ago, # |   +90 LOL...It seems I'll back to IGM...I'm very happy... in addition I'm going to make my first CF round >.<
•  » » 7 years ago, # ^ |   +16 OTL, When?
•  » » » 7 years ago, # ^ |   +30 I have prepared the problem statement in Div I already...I need to make some Div II problems and generate the test cases...I think it will be done in this month,(I'm kind of lazy T_T)
•  » » » » 7 years ago, # ^ |   0 Orz..
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   +15 Guys, what does mean "Orz"? This word is used so often by the Chinese and I never know what does it express :).edit: googled it, nice :) http://www.urbandictionary.com/define.php?term=orz
•  » » » » » » 7 years ago, # ^ |   +13 I am sorry... ( I just didn't know how to express my Admiration, except "Orz" for a moment.. .
•  » » » » 7 years ago, # ^ |   0 Admire!!! If so, I might not have an opportunity to attend it. TAT...
 » 7 years ago, # |   +3 Lesson learned for today. Don't ever use Java's sqrt. Nice round :)
 » 7 years ago, # |   +10 I love these questions!
 » 7 years ago, # |   +2 When should we expect rating change?
•  » » 7 years ago, # ^ |   0 It will been publish soon, Maybe 5 mins later ... )
 » 7 years ago, # |   0 In div2 problem B, it was asked to avoid using lld. Why?
•  » » 7 years ago, # ^ |   0 It's a common thing for codeforces, codeforces doesn't work with lld, just use I64d, it's quite the same. This warning is not specific for problem B, it's usually written on every taks that requiers use of long long integers :)
•  » » 7 years ago, # ^ |   0 "%lld" format is used for Linux-based compiler. "%I64d" format is for Windows-based compiler. Codeforces is Windows-based. CMIIW.
 » 7 years ago, # | ← Rev. 4 →   0 I get confused by the statement of problem E. And I can't get the right meaning till now. For example, let's focus on this case: (Final Case #16):Input 2 3 (endl) 2 2 4 (endl) 1 2 (endl) 1 1 (endl)I think the answer is 1.0 since we can ask the gold fish to give us 2 gifts with name 1. So finally we could get gifts with value 2 + 4, which is maximal. But the answer is 0.75.Could you please tell me why I'm wrong? Thanks in advance!
•  » » 7 years ago, # ^ |   +5 "Besides, he isn't the brightest of fishermen, so if there are several such ways, he chooses one of them uniformly."So he'll choose 1,1 or 1,2 uniformly, and there's only 50% chance of getting maximal gifts if he choose 1,2, so the answer is 0.5+0.5*0.5=0.75.
•  » » » 7 years ago, # ^ |   0 Thanks! Now I understand it.It turns out that I should read the statement more carefully. By the way, I think examples are too weak (as well as the pretest) such that I can pass it with a totally wrong understanding.(P.S.: It looks strange that some "\n" disappear in my post, so the data is in a mess. Does anyone know how to fix this?)
•  » » 7 years ago, # ^ | ← Rev. 3 →   +5 I also misunderstood in the same way and just realized that "Besides, he isn't the brightest of fishermen, so if there are several such ways, he chooses one of them uniformly."It means he does not only choose the best strategy but any ones as long as it may get him maximum value.
 » 7 years ago, # |   +10 Finally Div 1! :)
 » 7 years ago, # |   +7 solved 4 problems,final tests passed only 1,rly bad contest for me,anyways problemset was nice
•  » » 7 years ago, # ^ |   +3 Bad luck :(
 » 7 years ago, # |   +4 I liked the non-oeis-problems :) Waiting for the new contest days :D
 » 7 years ago, # |   0 Can anybody teach me how to solve E div 2? Thanks for your help!
 » 7 years ago, # |   +5 nice problems. keep up the good work.
 » 7 years ago, # |   0 On Div-2 problem B, while contest I using (double)pow to get square root from n, and I get wrong answer, then I change into sqrt and get accepted. Whats wrong with pow ? I use this for pow : double temp = pow((double)n, 0.5); long long square_root = (long long)(temp);
•  » » 7 years ago, # ^ |   0 It is floating point precision issue, I guess.
 » 7 years ago, # |   +3 And where is the editorial?
•  » » 7 years ago, # ^ |   +5 We are going to publish it within 14 hours.
•  » » » 7 years ago, # ^ |   +7 We have just published the analysis.