Автор awoo, история, 8 лет назад, По-русски

Привет, Codeforces!

15 апреля в 17:35 MSK состоится Educational Codeforces Round 19.

Образовательный раунд проводится в рамках инициативы университета Harbour.Space. Это уже второй раунд, проведенный при поддержке Harbour.Space. Подробности о сотрудничестве Harbour.Space и Codeforces можно прочитать в посте.

Учебное направление Data Science университета Harbour.Space несомненно интересно большой части аудитории Codeforces. Вот несколько слов об этом направлении от Сергея Николенко, преподавателя Harbour.Space и старшего научного сотрудника математического института имени В. А. Стеклова РАН (СПб).

Раунд будет нерейтинговый. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. После окончания раунда будет период времени длительностью в один день, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

Вам будет предложено 6 задач на 2 часа. Мы постарались сбалансировать проблемсет таким образом, чтобы было интересно как новичкам, так и опытным участникам.

Раунд вместе со мной готовили Иван BledDest Андросов и Михаил MikeMirzayanov Мирзаянов.

Надеюсь, вам понравится, и желаю удачи!

UPD: Разбор

Поздравляем победителей:

Rank Competitor Problems Solved Penalty
1 Reyna 6 214
2 tqyaaaaaaaang 6 230
3 nuip 6 303
4 W4yneb0t 6 341
5 lexuanan 6 457

Поздравляем лучших взломщиков:

Rank Competitor Hack Count
1 step_by_step 40:-7
2 halyavin 44:-17
3 STommydx 20:-5
4 yp155136 18:-2
5 FlierKing 24:-15

Было сделано 234 успешных и 308 неудачных взломов.

И, наконец, поздравляем людей, отправивших первое полное решение по задаче:

Problem Competitor Penalty
A Lewin 0:01
B 300iq 0:04
C fanache99 0:09
D Reyna 0:21
E Vladik 0:08
F skywalkert 0:40

  • Проголосовать: нравится
  • +134
  • Проголосовать: не нравится

»
8 лет назад, # |
Rev. 4   Проголосовать: нравится -29 Проголосовать: не нравится

It overlaps with GoogleCodeJam round 1A !

UPD: It doesn't overlap .. thanks for yinanzhu and KieranHorgan

»
8 лет назад, # |
  Проголосовать: нравится -42 Проголосовать: не нравится

is it rated?

»
8 лет назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

Why not all the contests have clear problem statements like this one. Thank you for this interesting contest.

»
8 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

How to solve F?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +31 Проголосовать: не нравится

    I don't know the time complex of the std. But the time limit makes me think that the std have the time complex of O(n2).

    My solution's time complex is , and it costs 858ms.

    First it's easy to come up with the DP of O(n3). Then let's look at the programme carefully, and we can find out that it's very similar to Knapsack problem. And this classic problem have a classic way(divide each original item into items) to optimize it to

    We can use the same way to opimize the original problem. Then we solve the origine problem in

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

very interesting problem set. I hope to see more problem set like this! :D

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone tell me why im getting TLE on E. My idea is precompute for every k below 1000 in O(N) each and just simulate all k bigger than 1000 (worst case scenario is 100 operations if im correct) 26393091

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Did someone pass TL42 with mincost maxflow on F?

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Never thought I could make more points than some reds or oranges. Strange contest =)

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve C ????

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain to me why in the second test for E the 8th number is 2?

10
3 5 4 3 7 10 6 7 2 3
10
4 5
2 10
4 6
9 9
9 2
5 1
6 4
1 1 <-
5 6
6 4

p = 1, a[1] = 3, k = 1, n = 10;
Initially p = 1. After first operation p = 1 + 3 + 1 = 5. After second operation p = 5 + 3 + 1 = 9 < 10. What am I missing?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    In the first operation p = 1 p = p + a[p] + k p = 1 + 3 + 1 p = 5 In the second operation p = 5 p = 5 + 7 + 1 p = 13 p > 10

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Ah, I see. Thanks! I completely missed the fact that when p changes the array element chages as well.

»
8 лет назад, # |
  Проголосовать: нравится +40 Проголосовать: не нравится

Please discuss the approach for problem F.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    You can solve it using dynamic programming. Let DP[j][i] denote the minimum cost to assign the first i mice to the first j holes. For each state, iterate over the leftmost mouse you will assign the jth hole to. This takes O(m*n*n) time.

    But notice that for a fixed j, the optimal left-point is non-decreasing for non-decreasing i, i.e. optima[j][i] <= optima[j][i+1]. So you can speed up the DP using divide-and-conquer optimisation.

    Code

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      How do you deal with hole capacities and the fact that contiguous mice are not necessary assigned to the same hole?

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +4 Проголосовать: не нравится

        The group of mice assigned to some hole is always contiguous, i.e. there will never exist a situation that a,b,c are three consecutive mice (in increasing order of coordinate) but a and c are assigned to hole-1 but b is assigned to hole-2.
        And what do you mean by how I deal with hole capacities? If I have to assign some suffix of the first x mice to hole j, then I can assign atmost the last capacity[j] mice to hole j.

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Just a moment after I posted, I realized sorting was enough to assign contiguous mice to a hole.

          As for the hole capacities, yep, I meant that (and I missed it's as simple as that!)

          Thank you :)

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can someone please help me in finding mistake in my Solution for problem C.

»
8 лет назад, # |
Rev. 4   Проголосовать: нравится +3 Проголосовать: не нравится

Can someone tell me where I am wrong in D?

I made a fucntion checkValid which takes node,l,r as arguments. And marks true if value[node] lies between l and r both inclusive. Then, I call checkValid with left[node], and with the intersection of (-inf,value[node]-1) and (l,r). The same process is repeated symmetrically for right node.

I am getting WA at Test Case 20. And my answer differs by 1 from expected answer.

Submission Link: 26396243

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    There were two mistakes.

    One was a syntax error at line 92. Second mistake was I was remembering the nodes which are visited instead of values.

    AC solution: 26398128

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

No successful submissions on E in Python 2 or Python 3. I tried to rewrite one Java solution to Python, it TLE-ed on test 7. Isn't the time limit of problem E too tight for Python?

»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

It's my first time to try hacking here on CF. Not sure how it works. It seems to be just stuck loading forever. Is this supposed to happen?

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anybody tell why my code is failing in one of the tests ?? https://pastebin.com/GC45xUAa

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

That's how you try to cheat even in an unrated round!!

ScreenShot

»
8 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

That's how you try to cheat even in an unrated round!!

ScreenShot

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

I noticed that if I submit a solution after a previous solution got hacked, then my new solution runs only the original system tests, and not the hack(s) that caught my previous solution(s). That's too bad, because that way I can be "Accepted" again without fixing my problem (in fact, I have no idea whether I fixed my problem unless the hacker is kind enough to keep trying the hack on my new solution).

UPDATE: Appears to be fixed now.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone please help me in finding mistake in my Solution for problem C.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

http://mirror.codeforces.com/contest/797/submission/26402069 why this submission always wrong at 25th test case???who can help me ??

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

I'm unable to submit a solution for the contest. It shows that System Testing is going on, while it was over hours ago.

On clicking the submit button, it shows the message "Practice is allowed only for finished and unfrozen contests".

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Is it normal that problems B and C now have duplicate tests? For example, there is the test #48 "1 // 1" that repeats further as #50, 51, and 54. Problem C also has such tests, e. g. "a" by #40, 41, 42, 45, 47, and 51.

»
8 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Хотелось бы увидеть разбор.

  • »
    »
    8 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится +5 Проголосовать: не нравится

    Извиняюсь, не добавил ссылку на него в анонс, сейчас будет

    UPD: Не будет, почему-то кф при попытке публикации изменения блога вылетает в "страница недоступна"

    UPD2: Преодолел, с другого браузера нормально получилось

    Разбор