Блог пользователя MikeMirzayanov

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

Уже сегодня состоится четвертьфинал ACM-ICPC в Саратове. От лица жюри и организаторов желаю командам порадовать своих тренеров и руководителей. У вас всё получится!

Наблюдать за текущими результатами соревнования можно будет по ссылке https://contest.sgu.ru/monitor/1.

А уже в воскресенье (23-го октября) в 11:00 здесь состоится неофициальная трансляция прошедшего соревнования. Вас ждут интересные задачи, которые жюри постаралось сделать интересными как для начинающих, так и опытных участников. К участию приглашаются как команды из 1-3 человек, так и индивидуальные участники. Контест не будет влиять на рейтинг Codeforces.

Конечно, контест будет нерейтинговым. Рекомендуется командное участие. Скорее всего, позже он будет перенесен в Тренировки.

Председатель жюри MikeMirzayanov.

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

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

Т.е. задачи сегодня во время соревнований нельзя будет посмотреть?

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

    Если вы находитесь в Саратове и являетесь тренером/руководителем команды, то задачи вам раздадим в печатном виде. Иначе получить доступ к задачам по время соревнования, увы, не выйдет.

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

      До трансляции в электронном виде распространять не стоит. Потом — пожалуйста.

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

        Эх... придётся идти за валидолом в аптеку.

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

Good luck for all!

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

Не знаю, на каком уровне произошла опечатка (baylor, локальная регистрация, заполнение базы вручную), но в таблице есть "Belgorog State U #1".

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

    А в чем ошибка? Действительно есть команда Белгородского государственного университета.

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

Желаю участникам!

Так себе пожелание)

Fixed

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

it's not a hard contest for an IOI man like me =))

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

Good luck to all especially CF users who are participating in NEERC. make us proud :3

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

Где-нибудь есть фотографии с основного тура, которые демонстрировались перед награждением?

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

There seems to be a typo on the contests page; the contest tomorrow is named "2015-2016 ..." instead of "2016-2017 ...".

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

The contest will not affect Codeforces ratings.

For sure, it will be unrated contest.

that moment when the author no longer can put up with "is it rated" comments so he repeats the information twice to make sure no one will ask it.

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

Contest clashes with Code Festival.

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

Are problems going to be shuffled since we can see the results?

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

Great contest! Is there something like official slides with solution outlines? I remember those are available for other ICPC contests like NWERC.

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

For Problem D, with this input :

5 2 10 5 4 1 7 14 10 12 4 10

Why this output is considered as wrong answer? 5 8 10 12 46 48

while jury's solution is

5 8 10 12 40 42

i think it is possible for my solution.

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

    According to your answer, you'll begin to cross the final bridge at time 34, not 40. Did you add t_i instead of actual crossing time?

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

Разбор задач: https://www.youtube.com/playlist?list=PLSqW9Jap9R88u6Yoch5XhlMmUmm1PvZlt

Ставьте лайки, подписывайтесь на канал.

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

How did some people pass I with min cost flow? Wouldn't it TLE with these constraints?

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

    In my case, I didn't know how to solve the "right" way so I decided to give it a try (and I had good reasons since I had seen someone pass this problem with a min cost max flow solution — the flow model is basically the same as problem I)

    The Big O notation is mean to flow functions, in practice they are usually faster than they seem. If you consider my code which uses SPFA (which has O(E) average shortest path) the code would be average O(V * E) still and I think it might be hard to create an O(V * E) SPFA case for the nature of the question

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

    What is the expected approach for I?

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

      we solved problem "I" with a greedy approach with O(n2log(n)) complexity.

      code: http://codeforces.com/contest/730/submission/21712213

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

        My greedy approach for problem I is O(n^2) 21710921 and can be optimized further to O(n*log(n)) using two priority queues.

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

          Do you care to describe your approach? I always like to see what people's reasoning was for a specific algorithm, beyond just the code :)

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

            Sure, sorry for my bad code. I'll explain how I get my idea step by step:

            • For simplicity lets define F(p,s) as maximum total strength by choosing p programming students and s sport students

            • Immediately, I found very simple DP solution but O((n^3)/6) is surely TLE, so I tried to find if there is greedy approach

            • At this point I think about easy case, for example what is F(p,0), it can obviously be solved by using greedy and sorting.

            • To print the answer easily, I also define A[x]:

              • A[x]=0 if x-th student is not chosen
              • A[x]=1 if x-th student is chosen for programming team
              • A[x]=2 if x-th student is chosen for sport team
            • Next I asked myself if I can easily compute F(p,0) and A[x] for F(p,0) could I find F(p,1) and update A[x] for F(p,1), and if I can could I do it again for F(p,2),F(p,3),... until F(p,s)?

            Spoiler Alert: the answer is yes; here's how
            • Total complexity is O(n^2), you can optimize it to O(n*log(n)) by using two priority queues one for keeping maximum of S(x) for x in group 0 and one keeping maximum of S(x)-P(x) for x in group 1.

            Took one full hour to write this, now I feel how hard CF contest author to prepare editorials for 5 to 7 problems. It make me appreciate it even more :)

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

              Oh yeah, it's very hard to write good and intuitive algorithm explanations. And you killed it at this one! It's very much appreciated!

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

It would be great if someone write a solution outline for this contest. Currently I am stuck on problem A and I will appreciate a hint.

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

    The best way to lower the points of the player with most points is: Lower him at the same time as other players that have most points.

    So you need to lower him until there is at least a pair of players with most points and the rest is easy because you can lower all the players with same points at the same time by grouping them in a smart way without ever lowering the player with least points.

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

Great contest!!!

I have a question in problem "I" I found a dp solution with the DP state (position , needed_sportsmen , needed_programmers) but that would give TLE and MLE because it's 3000 * 3000 * 3000

I think the solution is dp with some optemization but I couldn't find it can someone give a hint please !!!

thanks in advance.

:)

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

WTF problem A : Toda 2 ~ Dota 2...

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

What is the expected approach for E?

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

Can anyone prove why greedy works for E? Apparently we just have to consider the teams who will have their score decreased after freezing (call these down teams) and the teams who will have their score increased after freezing (call these up teams), and start unfreezing from the up teams in ascending order of a[i], then unfreeze the down teams in descending order of a[i]. If there are only up teams then unfreezing them in ascending order of a[i] will be the optimal strategy and similarly when there're only down teams. However, why can we consider them seperately when we have both types?

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

    If you have two teams, one of which has positive delta and the other one has negative delta, it doesn't matter in what order they are unfrozen. Answer is increased by the same value in both cases. So it's enough to consider positive and negative teams separately.

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

People didn't get AC 7 problems must be mentally retarded :))

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

People didn't get AC full must be mentally retarded =))

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

I want to ask something about the complexity of the min cost max flow it runs so fast

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

    O(N^2 logN).
    Because you need to run Dijkstra's algorithm N times, and the number of edges in the graph is O(N).

    And it's russian thread.

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

How to solve Problem A (Toda 2)?

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

Don't understand dp solution for problem I on Codeforces (C in the editorial). Assume that sorted students by decreasing of a[i].

We have 2d dp[i][j] with states: i — length of prefix we already processed, j — size of people who goes to team A.

And we have following dp formula (it is how I see it):

dp[i][0] = b[i]
dp[i][j] = max(dp[i-1][j] + b[i], dp[i-1][j-1] + a[i])

But it will give correct answer only if total number of students is same as sum number of contestants in both events. In other case we can latter optimize and make swap of people we take. But I don't get what I am doing wrong.

Test case where given strategy will not work:

5 2 1
5 5 3 1 1
6 6 3 5 5
»
7 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Is there English Editorial/solution sketches available for this contest?

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

How to solve J (Bottles)?