Ripatti's blog

By Ripatti, 7 years ago, In Russian

Всем привет!

В этом году Чемпионат Урала пройдет в Уфе 30 апреля на площадке Уфимского Государственного Авиационного Технического Университета.

Официальный сайт соревнования.

Правила отбора можно найти здесь.

Хочу обратить внимание, что отбор команд, не входящих в списки приглашенных, будет проводиться на базе этапа Открытого Кубка (OpenCup) ГранПри Польши, который пройдет 26 марта 2017 года.

Оргвзнос не предусмотрен.

Дополнительная информация будет появляться на официальном сайте по мере поступления.

UPD. Обратите внимание на изменение правил отбора.

UPD. Регистрация открыта.

UPD. Регистрация продлена до 16 апреля! Также отдельная просьба тем командам, которые приглашены, но точно не приедут — сообщить мне в личку.

  • Vote: I like it
  • +62
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Was this GP of Ural? Does any one have a better solution for D? Our one is kind of optimized dp

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

    Yes, exactly. In D we have this: if m ≥ 2n + 2, we construct the answer as a rectangle 1 × x and a number of unit squares. Otherwise if m < 100, do a straightforward dp. Otherwise iterate for possible rectangle a × b to obtain m ≥ 2n + 2 in remains. We checked that this works on the contest by a straightforward dp for reasonable values of n, m.

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

    I have O(n^2*logn) DP.

    We need to take a set of pairs a,b such that sum(a*b)=x and sum(a+b)=y. a=1,b=1 adds 1 to x and 2 to y, so our DP can be: for a given parity of y, and a given value of 2x-y, what is the smallest possible y? We have O(n) states and O(nlogn) possible rectangles for transitions.

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

    OMG. Stupid knapsack in with bitsets works 0.2 seconds.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve L?

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

    We need to choose for each cell if it's covered by row or column, and in the end for each row or column with 2 different symbols multiply the answer by 2. Do dp[row][mask], where row means that we already chose cells for first row rows and mask stores for each column how many cells in that column we did not choose yet(it's  ≤ 2, so there are only 3n masks).

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What about M? Using custom bigint (c++) gives tle, later we had to optimize it to non bigint for deep nodes to get ac.

Also F/I?

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

    M: Sum of depth of subtrees for all vertices is O(n). So you can do whatever you want if it is linear with small constant. Looks like problem with bigints is that constant isn't so small.