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

Автор HolkinPV, 12 лет назад, По-русски

Всем доброго времени суток)

Рады приветствовать вас на очередном раунде Codeforces #141 для участников Div. 2. Как обычно, остальные могут поучаствовать в нем вне конкурса.

Задачи для вас были подготовлены группой авторов в составе: Павел Холкин (HolkinPV), Иван Фефер (Fefer_Ivan), Игорь Кудряшов (Igor_Kudryashov) и Геральд Агапов (Gerald). Как обычно, хочется поблагодарить Михаила Мирзаянова (MikeMirzayanov) за прекрасную систему Codeforces и Марию Белову (Delinur), которая переводила условия.

Распределение баллов по задачам стандартное.

Всем участникам соревнования мы желаем удачи, успешных взломов и высокого рейтинга!

UPD: контест завершился, надеемся вам понравилось) Поздравляем победителей:

1) AntiFate

2) alicechennan

3) honeyofsistercha

4) Fride

5) bla_bla_bla

UPD2: разбор задач опубликован, его можно найти здесь

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

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

Какая будет разбалловка?

Все, вижу...

»
12 лет назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится
Комментарий удален по причине нарушения правил Codeforces
»
12 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

When you decide which type of score distribution to choose, what do you base your decision on?

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

    already mentioned. "Score distribution is standard." that means in ascending order.

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

    I am guessing it is based on how confident the authors are of the difficulty level of the problems. If they are very confident then standard score distribution otherwise dynamic.

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

Популярный будет контест — за 40 минут — x2122 зарегистрированных!

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

Всем счастья ^^

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

Надеюсь задачи будут решаемы для меня ! Всем удачи)

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

Немного надоели радостные посты о всеобщем счастье на контесте, созданные для прокачки вклада. Не по понятиям поступаете, господа.

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

20 деревьев отрезков авторское решение или мне надо отдохнуть? (Задача D) UPD Даже прошло...

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

    У меня было 72 дерева Фенвика =) Почему бы и нет, теоретически должно проходить. Но я не успел =(

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

    А как затолкать эти деревья в память? У меня решительно не лезли.

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

      Примерно так:


      const int N = 100500; long long tr[8][15][N];

      Это если деревья Фенвика. Деревья отрезков так же проходят. Но там уже надо все ограничения ставить в упор.

      Что-то типа


      const int N = 100001; const int Z = 6; long long tr[Z - 2 + 1][2*(Z - 1) + 1][4 * N];
      • »
        »
        »
        »
        12 лет назад, # ^ |
        Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

        У меня упало при 30*4*10^5 интов О_о. Я определённо что-то делаю не так.

        UPD. Epic Fail. Забыл отключить freopen("input.txt","r",stdin). Поэтому программа читала n = 0 и уходила в бесконечную рекурсию в попытке построить дерево на отрезке (0, n-1).

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

      Ловкость рук и никакого мошенничества :)

      UPD Люди не понимают иронии =(

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

Растолкуйте остолопке, отчего в задаче В div2 -1 -1 — это правильное решение, а 60 60 — нет? Ведь сдвиг и так и так получится 0.

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

    Там по модулю не берут.

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

    Если мы сдвинем нижний квадрат на -1 -1, то две единицы совместятся, и стоимость будет 1. При любом другом сдвиге стоимость будет 0.

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

В Е была 2-SAT?

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

    Нет, один dfs. Действуем как в алгоритме разбиения графа на двудольность с той лишь разницей, что когда мы проходим по ребру, на котором есть асфальт, две вершины, связанные этим ребром, должны быть в одной доле.

    UPD: Заходит.

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

У меня одного были проблемы с претестом №11 в B?

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

    При тупом переборе нет проблем на претестах

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

    Мой анализ всех посылок выявил примерно триста сорок три (прописью: 343) посылки с таким вердиктом. Подробную статистику по каждой из посылок вы можете сделать, перейдя по этой ссылке.

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

First off, great problem set. Seems like many people managed to solve E (grats), I would like to know the trick!

I reduced the problem to finding a sequence of nodes (with repetition allowed) that by using XOR, and including the initial state, would yield only ones. If i'm on the right track you probably understand what I mean, if im not please ignore. Anyway, can somebody hint for the solution?

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

    Not a sequence, but a set (doesn't make sense to paint a city twice, and also the order doesn't matter). Color blue the cities you're going to paint, and the other ones red. Now an asphalted edge means the colors of the cities it connects must be equal, non-asphalted — they must be distinct. Then see 2-coloring of graphs.

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

Как E решалась.Скажите пожалуйста.

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

    Я решал так:

    1. Каждый город надо ремонтировать не более одного раза.

    2. DFS.

    Не знаю, насколько это правильно:-)

    UPD : WA-43

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

    я решал через двудольный граф. (если дорога без асф. то города в разных частях если с асф то города в одной и той же части) — если нельзя так разбить, то сразу есть ответ, затем выбираем одну из частей и выписываем (в том как выбирать я не уверин :( — посмотрим по тестам)

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

Lame...I totally ignored the alert that an all white fractal and an all black fractal are valid fractals.

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

И все-таки, надо признать, авторы жестко ошиблись с разбалловкой и сложностью задач. Самая жирная Е решается в разы больше, чем С... Мир встал с ног на голову

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

    Почти на каждом раунде мир аналогичным образом переворачивается. Так что половину времени с миром все норм.

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

    С на самом деле тоже очень просто решается. Динамическое программирование: z[mask][depth][x][y] — совпадает ли подматрица (x, y) - (x + 2depth, y + 2depth) c фракталом паттерн которого равен mask(маска из 4-х битов) и получен через depth шагов алгоритма.

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

      это проще Е, все ок?

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

      mask же незачем включать в состояние динамики, можно просто перебрать.

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

        даааа... вообще можно вообще не хранить depth, x, y — хэши)

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

Привет 43 тест! :)

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

Regarding the rule: "_He divides the sheet into four identical squares. A part of them is painted black according to the fractal pattern._", I think the example for C is not illustrative enough...

I thought "a part of them" means one of the 4 parts... And it takes me quite a while to understand why a "2x2 black" square is a valid fractal pattern.

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

В задаче С есть анти-хэш тэсты, или у меня кривые руки?

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

    Специально мы их не делали. Там просто много разных тестов. Вообще она без хэшей решается. Я писал выше.

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

    Если хеш по маленькому модулю, тебя просто парадокс дней рождения валит, т.е. обычный рандомный тест. Я с пятого раза запихал такое решение :)

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

      ну видимо как хэшировать, я сдал 10^9+7, видимо зависит от того, двумя простыми числами или одних хэшируешь еще

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

        Может еще и второй ник свой подскажешь? :) Очень уж хочется решение посмотреть.

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

        У меня сразу зашли хэши. Само собой, по вертикали и по горизонтали нужно брать различные основания. Модуль — 2^64. Я за две минуты не смог построить антихэш тест и бояться не стал.

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

    с модулем 2^64 зашло

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

      нет на вас Zlobober

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

      Да, кстати, по модулю 2^64 должно заходить: ведь чтоб тот самый тест работал, нужна длина 2048.

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

        Вообще непонятно, как можно в этой задаче антихэш тест применить.

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

      по модулю 232 зашло

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

I am bit confused about sample given for Problem E(probably I am misreading problem).

example had

4 4 1 2 1 2 4 0 4 3 1 3 2 0

if road build go to first city 2 and then to 1, it would asphalt all roads?? after it go to city 2=> 1st road would unasphalt and 2nd/4th road would asphalted after he go to city 1=> 1st road would be asphalted

hence after 2 step it should get asphalted, can someone help me where I am misinterpreting the problem

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

    You are absolutely correct, 2 1 2 Is an answer, however it's not said you should print the minimal answer so 4 3 1 2 3 Is also an answer.

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

    When multiple solutions exist, print any.

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

    You are right.
    2
    2 1
    is valid answer for the first sample test.

    In this problem you can output any solution that need less than n steps.

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

    I'm also confused about the sample, but it says

    he asked you to make a program that determines whether you can "in some way" asphalt Berlandian roads in "at most" n days.

    you don't need to output the minimum number of days, so 4 3 1 2 3 in the sample is also a correct answer.

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

I hope editorial will be available soon.

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

научите писать дфс, а то Е упала потому что написал


for (int i = 0; i < n; ++i) if (!use[i]) dfs(0);
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Меня секунда отделила от взлома решения, в котором подразумевалось, что граф связен >_<

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

      да нет, я это понимал, там я просто перепутал, dfs(i) нужно было

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

        Да, я понимаю, просто вспомнился один из фейлов этого контеста именно когда увидел этот комментарий.

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

    там вместо dfs(0); не dfs(i)?

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

My solution to task E First we notice that doing the operation (asphalting) on town X will XOR all the roads coming out of it, so it's obvious that you don't need to do the operation (asphalting) on the same town more than once. (XOR-ing a road 2 times, is the same as XOR-ing it 0 times) So as we know that, we know for every town, we either asphalted the roads coming out of it once, or we didn't at all. Now let's take a set of connected towns (you can reach each town in the set from each town in the set) , Now if we know for one town if we asphalted it, then we can find out if we asphalted for each of the towns in the set. Example : We take a random town in the set and say we didn't asphalt it, we check every town he is connected to with a road that is not asphalted, obviously the other town must be asphalted if we want the road to ever be asphalted, and we check every town he is connected to with a road that is asphalted, obviously the other town shouldn't be asphalted. This way we repeat for every new town we find and because it's connected graph, we will find out for all of them. Now if we get for a town, that it should be asphalted and at the same time not asphalted, we got impossible situation. Then we repeat the whole thing but saying we asphalted the random town we took. So if both cases return impossible, we print impossible, in other case , we stop looking at this connected graph and say we managed to do it , then we proceed and take another connected set, doing the exactly same thing. If we end up doing all the sets without problems, we print the towns we asphalted from (we memorize them). Since we said a town can be asphalted at most once, the limit, to asphalt at most n towns, doesn't really do anything (asphalting all towns will result in n asphalts).

Sorry if i didn't explain it quite well, just thought i'd share my idea with you, it worked and i got 54th place :)

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

Nice problemset, but one question. How did you define a "fractal pattern"? naturally thinking, why a pattern with 0 or 4 blocks in black grids is vaild, with exactly 1 also works, but doesn't for exactly 3 black grids? It has just gone beyond my imagination..

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

    Why doesn't it work for 3 black grids?

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

      I'm still confused... can you list out all "fractal pattern"? easy job for there will be at most 16.

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

        There are exactly 16 fractal patterns. Every cell can be either black or white regardless on other cells.

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

          Thanks. Finally I realized that "A PART OF THEM" means arbitrary instead of exactly one of them.

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

Can you update the rating please so I can sleep well ?

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

контест два два восем рулит.два два восем есле в архиве

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

Мне в Е на ум сразу только кинулась система линейных уравнений. Там вроде все просто — обычный Гаусс по модулю 2. У меня зашло. По времени — отлично.

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

Did anybody model the problem E with 2-SAT my solution failed in test case 43

if c == 0 then either of a or b can be taken but not both so i did this: (a or b) and (!a or !b)

if c == 1 I initially did (!a or b) and (a or !b) and (a or b)

It gave Impossible in first case

Why it did not work?

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

    Intersting. I tried to solve this problem by creating a linear equations system with m equations and n variables, taking XOR (or plus %2) on everthing.

    This approuch is different from yours but I think the idea behind them are the same (you are modeling that a XOR b = NOT c like me, althogh you maybe want to remove the clause (a or b) for the case c==1, to make (!a, !b) possible).

    I also failed in test case 43, so I think it was probally for the same mistake. Does someone know why this idea could fail?

    UPD: Got AC. My code just contained bugs, not related to this ideia. It must be correct.

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

    I think this formula is not correct: "if c == 1 I initially did (!a or b) and (a or !b) and (a or b)"

    The part (a or b) is wrong, because when (a = 0 and b = 0) it return 0, but actually in this case it should return 1.

    The correct formula should be: if c == 1 then (!a or b) and (a or !b)

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

      Thank everyone. @pele yah you are right i did not handle when both of them can be 0. deleting (a or b) got AC.

      Again thanks.

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

For those who are seeking for non dfs/2SAT solutions in E:

Actually it is a system of Boolean equations with 2 variables each, the condition is to set the edge connecting i and j to be colored, with given color condition k (either 0 or 1). So we get for each edge, an equation like

and can be rewritten as

You will get m equations for n variables. Note that there is no unique solution (if it exists) since there are no two different equations with the same pair of variables with different coefficients on LHS (it's just 0 or 1 anyway). It means that if solutions exists, there is at least one slack variable, and the solution size is always less than n.

Solving the equation can be done using Gaussian Elimination in O(mn2) time. A faster approach is to utilize the property that each equation has exactly two variables. when doing elimination, the row being update always contains exactly two variables as well. Suppose we pick the equation

with i < j. Now we want to eliminate

where i < k. WLOG assume j < k. You get

Steps to consider.

(1) We saw an equation being set with (xj, xk) such that

(i) if w = w', this is a redundant equation, we forget it and process next edge.

(ii) otherwise, contradiction occurs, no solution.

(2) If we haven't seen such pair (xj, xk), and there is no equation with pairs (xj, xp) with j < p, we set up this new equation (that xj relies on xk for backward substitution).

(3) If we have an equation with pairs (xj, xp) with j < p and p ≠ k, we eliminate the obtained equation with it to get a new one with pair (xp, xk) (assume p < k). Then go back to step (1).

Hence we see that step (1) to step (3) would go at most n times, so we obtain at most n - 1 equations after processing m edges, and do backward substitutions. It takes O(mn) time.

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

Can anyone help me find the wrong in my submission?Because it's right when running on my own computer.thx.2261761

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

    Make sure to fix these warnings first:

    x.cpp: In function 'int main()':
    x.cpp:83:93: warning: format '%c' expects argument of type 'char*', but argument 2 has type 'int*' [-Wformat]
    x.cpp:88:93: warning: format '%c' expects argument of type 'char*', but argument 2 has type 'int*' [-Wformat]
    x.cpp:90:13: warning: declaration of 'x' shadows a global declaration [-Wshadow]
    x.cpp:55:5: warning: shadowed declaration is here [-Wshadow]
    x.cpp:91:17: warning: declaration of 'y' shadows a global declaration [-Wshadow]
    x.cpp:55:8: warning: shadowed declaration is here [-Wshadow]
»
12 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Why hasn't the editorial yet been published???