gen's blog

Codeforces Round #142
By gen, 12 years ago, In English

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 I

  1. YuukaKazami
  2. peter50216
  3. kelvin
  4. takaramono
  5. Martin

Div II

  1. coquelicot
  2. llj_bash
  3. kb.
  4. niukuo
  5. Petar
  • Vote: I like it
  • +175
  • Vote: I do not like it

Comments Comments (76)
| Write comment?
»
12 years ago, # |
  Vote: I like it -16 Vote: I do not like it

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!

→ Reply
»
12 years ago, # |
  Vote: I like it -33 Vote: I do not like it

Плохо что добавили 5 минут, а сайт висел минут 10! + лаги

→ Reply
»
12 years ago, # |
  Vote: I like it -7 Vote: I do not like it

я не пойму, С что ли баян какой-то??? почему многие сдавали ее в первые 20 минут, и некоторые с див2 на 11 минуте ее сдавали?? как она решается? и правильно я понимаю, что кто знал идею — немного додумывали и профит?

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it -11 Vote: I do not like it

    Nevermind.

    → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 3   Vote: I like it +2 Vote: I do not like it

    Sorry, bug with language.

    C is cool, thx 2 authors.

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it -17 Vote: I do not like it

    dangerous, вы читаете мои мысли

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    Задача становится лёгкой, как только подумаешь, а не подсчитать ли количество разноцветных треугольников.

    (The task C is a easy, when you will try to count the number of colorful triangles.)

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it -24 Vote: I do not like it

      разноцветных по ребрам что ли?

      → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    Я на месте придумал. Ответ — .

    Чтобы это понять, надо удвидеть, что бывают 4 картинки на трех вершинах. И в указанной сумме квадратов две нужные учтутся с коэффициентом 3, а не нужные — 1.

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    все довольно просто же. сначала прибавим к ответу все треугольники. потом, для каждого ребра Элис вычтем из ответа n-2. Потом для каждой вершины прибавим к ответу C(cnt, 2). Можно убедиться, что его мы не посчитали ни одного разноцветного цикла, а все одноцветные посчитали ровно 1 раз.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it -29 Vote: I do not like it

      ля, ну баянистая же идея, как я не вспомнил подумать в этом направлении...

      → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    И вообще это английский тред, что и вызывает кучу минусов.

    (And this is an English thread, which is also the reason for minuses I suppose.)

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Давайте решать так. Сначала посчитаем сколько всего треугольников в графе у Боба. Будем добавлять ребра по одному и смотреть, сколько треугольников даное ребро отняло у графа Боба. Пусть ребро исходит из v1 в v2, всего мы до рассмотрения текущего ребра добавили s1 ребер с вершиной v1, и s2 с вершиной v2. Тогда логично, что текущее ребро отнимет от графа Боба (n-2-(s1+s2-мощность пересечения множеств уже добавленных соседей для v1 и v2)). Заметим, что вот эти вот общие вершины образуют треугольники с v1 и v2 в графе Алисы, а больше никакие другие вершины не образуют(на текущем этапе). А значит, можно просто не отнимать их, но и в конце не добавлять треугольники в графе Алисы. Очень крутая задача, ИМХО.

    → Reply
»
12 years ago, # |
  Vote: I like it -17 Vote: I do not like it

Very annoying contest.

→ Reply
»
12 years ago, # |
  Vote: I like it -12 Vote: I do not like it

Итак. Задача D div 2 (B div 1). Писал Дейсктру. Обновлял путь таким образом: брал за растрояние минимальный момент времени такой, что "В этот момент времени можно вылететь с планеты", с учетом того, что в последнюю планету растоянием называлось "время прибытия". Что не так?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 

    2 1
1 2 1
2 0 1
4 0 1 2 3
    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      Спасибо. Именно это у меня и не было учтено. Будет совсем обидно, если в дорешке сразу зайдет с исправлением этого бага (не учел, что из первой вершины не всегда удается отправиться в нулевой момент времени)

      UPD. Не совсем обидно, схватил еще и тл. От которого легко избавиться

      → Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it -9 Vote: I do not like it

Rating will be update?

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

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.

→ Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

who can you tell me solution problem E div 2? thanks you

→ Reply
»
12 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

[user: dangerous]

→ Reply
»
12 years ago, # |
  Vote: I like it +40 Vote: I do not like it

Please tick "In Russian" if you don't write in English :)

→ Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I've just submitted a solution that got TLE during the competition and it has been accepted changing only cin with scanf.

    → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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 :)

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    And after all, it accepted! Runtime is still 1.6 secs after systests

    → Reply
»
12 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Почему тл?

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I suppose that it's cycles over array t.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      но это же всего константа. Очевидно, что он не более 1 раза пройдет по массиву t. итого: 10^5. Неужели для кодфорса это критично???

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It's O(n^2) when all edges are from vertex 0, and everebody comes to 0.

        → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        In the worst case you will go over array t[u] for every edge v->u.

        → Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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?

→ Reply
»
12 years ago, # |
  Vote: I like it +90 Vote: I do not like it

LOL...It seems I'll back to IGM...I'm very happy... in addition I'm going to make my first CF round >.<

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    OTL, When?

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +30 Vote: I do not like it

      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)

      → Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Lesson learned for today. Don't ever use Java's sqrt. Nice round :)

→ Reply
»
12 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I love these questions!

→ Reply
»
12 years ago, # |
  Vote: I like it +2 Vote: I do not like it

When should we expect rating change?

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In div2 problem B, it was asked to avoid using lld. Why?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 :)

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    "%lld" format is used for Linux-based compiler. "%I64d" format is for Windows-based compiler. Codeforces is Windows-based. CMIIW.

    → Reply
»
12 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

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!

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    "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.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?)

      → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 3   Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
»
12 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Finally Div 1! :)

→ Reply
»
12 years ago, # |
  Vote: I like it +7 Vote: I do not like it

solved 4 problems,final tests passed only 1,rly bad contest for me,anyways problemset was nice

→ Reply
»
12 years ago, # |
  Vote: I like it +4 Vote: I do not like it

I liked the non-oeis-problems :) Waiting for the new contest days :D

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody teach me how to solve E div 2? Thanks for your help!

→ Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

nice problems. keep up the good work.

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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);

→ Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

And where is the editorial?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    We are going to publish it within 14 hours.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      We have just published the analysis.

      → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good contest

→ Reply