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

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

Всем привет! :)

Рад пригласить Вас на очередной Codeforces Round #148. Я (Hamed Valizadeh) автор этого раунда.

Я благодарю Gerald (Геральд Агапов), MikeMirzayanov (Михаил Мирзаянов), Delinur (Мария Белова), и Saeed_Reza (SaeedReza Seddighin) за помощь в подготовке этого раунда.

Распределение баллов по задачам стандартное в обоих дивизионах: 500-1000-1500-2000-2500.

Надеюсь задачи Вам понравятся.

Good luck and have fun ;)

Update. Соревнование закончилось. Мои поздравления победителям обоих дивизионов! :)

Div1:

  1. tourist
  2. cerealguy
  3. Dmitry_Egorov
  4. RAVEman
  5. UESTC_Nocturne

Div2:

  1. LiWenHaoTianXiaDiYi
  2. goooooooopan
  3. jthread
  4. kolina
  5. xcodevn

Поздравляю участника Endagorion — единственного, кто решил задачу 238D - Ленточное Программирование.

Кстати, я надеюсь, что вас не сильно расстроила скучная задача!

Update 2. Разбор готов. Прошу прощения за задержку. http://mirror.codeforces.com/blog/entry/5765

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

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

Two consecutive contests with Iranian authors, very good :-)

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

questions are going to be VERY hard :|

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

    Why do you think so ?

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

    fahmidan sualasham sakhte che berese be hale suala

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

      may be the only reason why he's taken this low rate is that he's written it in phinglish(in farsi means writing persian in english).it's the translatoin: even understanding the questions is hard so how U wanna solve it??!

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

Thankyou -- Good luck and have fun — -

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

Codeforces Round #148 will lucky for div 2, :)

148 div 2 = 74

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

be Sure that Question will be So hard ! :) Do not Put your Rating in Danger !!! =))) GL everyone !

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

I think there's going to be a lot of math in this contest.

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

When the lags will be fixed?

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

    When the first contestants will give up ;) (seriously, I hope that the lag will not alter too much the contest :/ )

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

Again it is — the crash!

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

This is not the first contest which gives me "**Bad gateway**" errors (502 — 504) instead of a contest start. I understand that is not supposed to be so, however, I would want to hear what exactly goes wrong with the server. Moreover, I believe there are plenty of nice guys over here who could probably be very experienced and helpful in configuring network/servers. Why don't we post some CodeForces issues as a public discussion? This kind of a solution would allow CF users to help the platform somehow.

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

Pressing the F5 Key all the time...

Hope this is getting fixed soon!

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

    Maybe the servers work has worsened because of you and some other users pressing F5 all the time?)

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

Isn't it better to start on the 5 PM than 4.55 PM ?

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

nooooooooooooooooooooooooooooooooooo

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

всем удачи!!!

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

В шапке сказано, что CF поддерживает VK. В чём заключается поддержка? У них то уж точно есть опыт в работе с high-load проектами.

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

I think Codeforces should use safe mode during contest time as they did few times in past. Server down before contest is ok but this may happen in contest time too. Topcoder also closes practise rooms during contest.

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

Friends, nothing is perfect!!!!

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

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

Блин, не успел зарегистрироваться — сайт лежал... В таких случаях обычно контест минут на 10 откладывают, чтобы все успели зарегаться

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

The server needs to be upgraded.

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

Почему последовательность (0, 1, 3) не является корректной нешерстянной последовательностью?

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

    Потому что в ней есть подпоследовательность (0).

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

    l = r = 1

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

    Потому что число 0 как подстрока дает xor = 0

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

      А что насчет 1 2 3 4 5 ? При l = 2, r = 5, получаем 2 ^ 3 ^ 4 ^ 5 = 0

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

        Имеется ввиду, что вместо исходной последовательности мы рассматриваем последовательность частных xor-сумм:
        b[0] = 0
        b[1] = a[1] = b[0] ^ a[1],
        b[2] = a[1] ^ a[2] = b[1] ^ a[2],
        b[3] = a[1] ^ a[2] ^ a[3] = b[2] ^ a[3],
        ...

        Ясно, что a[l] ^ ... ^ a[r] = 0 равносильно b[r] = b[l-1] (играет свойство ксора a ^ a = 0). Кроме того ясно, что b[i] все лежат от 0 до 2^m-1. Кроме того, по b[] можно восстановить a[] как a[i] = b[i] ^ b[i-1]. И для любой b[] с элементами от 0 до 2^m-1 восстановленная a[] будет с таким же свойством.

        Поэтому задача равносильно подсчету последовательностей длины n с элементами от 1 до 2^m-1 (0 нельзя так как b[0] = 0), все элементы которой различны.

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

Div 2 — B is not well defined. When we erase a character at position n and cp points to the character at position n+1, does it still point to that character (now at n) or does it remain at n+1?

Why the negative votes and no replies? Is there any place where we can ask questions to the organizers?

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

Very easy problems. Thx!

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

Looks like its going to take a while to reach division one :s

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

In problem D, div 2: I think just care the case n==3, another case the anwser is "2 2 2 2 2 ...". Is it right?

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

    no but there are only two options: two smallest in one subsequence or each in a different one. there is no way to decrease the maximum value of F so we have to increase the minimum of F.

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

    No, the answer is without doubt "2 2 2 2 2 ..." only when n==2. In other cases we should check more conditions.

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

it looks problem E,DIV 2 was easier than D...:D

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

    and it was the opposite in div 1 !!!!

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

    I recall a similar problem, at least on the surface, which also asked the minimum number of edges which direction you had to change. Maybe some people solved that problem and chose this instead of D, since it looked very familiar.

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

    You can't erase your comment, prepare to receive minus by the non-contestants who will not get it now that the system test phase is ended ;)

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

Are the pretests of С (div1) strong enough? I wrote solution 5 minutes before the end and realized that sometimes it can't find solution. So I just put line: if (best == INF) cout << 2. And it passed pretests! I'm 99% sure my solution is wrong but maybe someone can prove it? :)

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

    It depends on your algorithm ... Maybe you can always find a solution?

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

      I think it doesn't work on bamboo graphs (e.g. O-O-O-O). Idea is the following: Choose one vertex i = 1..n and run DFS on tree to mark for every vertex: is the parent edge forward or backward. If this edge (to vertex j) is backward, we claim pair (i, j) to be good. If both pair (i, j) and pair (j, i) is good, we can relax answer with number of backward edges on the way from the root minus one.

      P.S.: Ouch, looks like I deleted some lines and now it relaxes just if pair (i, j) is good :)

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

I liked the contest. At the beginning problems confused me a lot, especially problem A. But when I thought a bit about them, they turned out to be solvable.

Unfortunately my Div 1 C failed...

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

    I can't agree more ~ The problems are all interesting and skillful.

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

ahhh... at last system test started. hope it won't take long time to finish.

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

Judging in not working!

Edit: Now working

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

I missed a hack on problem B :( Someone in my room outputs "1 1" if n == 2...

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

B Div 2 много у кого упала ...

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

I did not spend much time on the problem E because of the following test:
7 8
1 2
2 4
1 3
3 4
2 5
5 7
3 6
6 7
3
1 4
2 7
3 7

The answer is 2 but if we consider only stops reachable in any case for each bus route we don't find a solution. I am wondering how many of those who submitted this problem know about this test?

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

Very nice problems...But I'm lack in experience and my solution of B got FST...TAT

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

I'm unluky :( ;(

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

Pleeeease, don't make us wait, update the rating.

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

Can smb explain to me how to solve problem C(Div2) or A(Div1)? Thanks in advance

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

    hey, count how many number you can put in the place of a1, then how many number you can put in the place of a2 and so on .

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

    2^m — 1 ways for the first number, 2^m — 2 for the second etc.

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

    f(n) = f(n-1) * (2^m — (n-1) — 1), f(1)=2^m-1. Here 2^m — (n-1) -1 means you have this number of ways to append a number to the valid sequence with length n-1. "-1" since you cannot use 0.

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

      I don't understand.

      Why can you simply add unused numbers (apart 0) to a sequence of length n-1?

      Look at this sequence (n=3,m=3): 5 (101), 2(010), 7(111)

      All numbers are different, but 5^2^7 = 0.

      So it is a wool sequence: l=1,r=3

      Why am i wrong?

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

        At begining you have only "0" as foribbden element.

        After first addition, you have one more foribbden element (the added one).

        After second addition, you have next foribbden element (first ^ second). And so on.

        So, you must look at "accumulate xor" not (simply) values.

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

          Thanks for your explanation.

          I had misunderstood the meaning of "n-1".

          And you can also be sure that all of the "n-1" accumulated XORed values will be different, so that there are exactly n-1 distinct numbers to be excluded:

          Else, it implies the previous n-1 elements would be a wool sequence:

          If XOR (1 -> x) = XOR (1 -> y), y>x would imply that XOR(x+1->y) = 0, implying it was a Wool sequence.

          Impressive how some people solved it within minutes =|

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

I wish this contest were the Elimination Round for BAYAN ... Thank you for the good contest :)

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

Finally "Expert"! :)

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

Nice Contest :D hope to see the Editorial soon..

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

Контест просто класс!

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

Задача E, Почему ответ на третий тест — -1? 4 8 1 4 1 2 1 4 2 1 2 3 3 1 3 2 3 4 4 1 2 2 1 2 4

Тут же есть маршрутка, которая равновероятно ездит по маршрутам 2-1-4 и 2-3-4. Значит, когда-то она приедет к первой вершине, и парень поедет на свидание без пересадок.

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

    В понимании авторов задачи худшим случаем может быть событие вероятности 0 видимо. Не понятно правда зачем тогда написано слово случайно.

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

      Чтобы не формализировать понятие "Автобусы играют против нас".

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

      Понял. Обидно, опять не понятно условие задачи без вмешательства других участников. F на прошлом раунде еще прекрасней.)

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

    В условии в нескольких местах написано "в наихудшем случае". В твоем примере наихудший случай имеет вероятность 0, но от этого он не перестает быть наихудшим.

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

    Слово "случайно" там не к месту. Имеется ввиду, что надо рассматривать худший случай. А это значит, что она может никогда не приехать к первой вершине. Я, конечно, не рашил задачу. Но отсутствие слов "выведите ожидаемое число автобусов с такой-то точностью" и присутствие фразы "на какое наименьшее количество автобусов ему придется сесть в наихудшем случае" намекает на мое понимание.

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

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

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

Can someone explain why in the sample test for div2 b: 7 4 1>3>22< 1 3 4 7 7 7 1 7 the answer for call l = 1 and r = 7 is 2 3 2 1 0 0 0 0 0 0.

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

    1>3>22<

    last 6 numbers are ignored for convenience

    1-> CP=1 DP=R MAP=0>3>22< X= 0 1 0 0

    2-> CP=2 DP=R MAP=0>3>22< X= 0 1 0 0

    2-> CP=3 DP=R MAP=0>2>22< X= 0 1 0 1

    2-> CP=4 DP=R MAP=0>2>22< X= 0 1 0 1

    2-> CP=5 DP=R MAP=0>2>12< X= 0 1 1 1

    2-> CP=6 DP=R MAP=0>2>11< X= 0 1 2 1

    2-> CP=7 DP=L MAP=0>2>11< X= 0 1 2 1

    2-> CP=6 DP=L MAP=0>2>10< X= 0 2 2 1

    2-> CP=5 DP=R MAP=0>2>00< X= 0 3 2 1

    2-> CP=5 DP=R MAP=0>2>0< X= 1 3 2 1

    2-> CP=5 DP=L MAP=0>2>< X= 2 3 2 1

    2-> CP=4 DP=R MAP=0>2> X= 2 3 2 1

    2-> CP=5 END

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

If i can solve 3 problems in div2 & 2 problems in div1...Whose 1 will be better???

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

    It may vary between man to man. But according to my opinion, solving 3 in div II is only better confirming that any 2 of these 3 also appear on div I(Like 2 from (C-E))

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

I see some ppls failed Problem B (div1) on test 6, giving the same wrong answer 190 (P.S. correct answer would be 200).

Is that a coincidence?

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

    Many people have the same, good, algorihtm. Similarly, many people have the same, but incorrect algorithm :P Just coincidence :)

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

      ;) But when you think carefully, there is no way you can come up with a combination which is even better than the best case, even with an "incorrect" algorithm.

      What you can do with an "incorrect" algorithm, is to get a worse answer. Am I right?

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

    Oh no I got WA on #6 and my answer was 190...However,I don't know why it's wrong = =

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

      I would suggest that you might have calculated the minimum value of the maximum value and the maximum of the minimum value separately while they might not be achieved at the same time.

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

        eh..no..I have thought about this — -...It's so kind of you to view my solution 2500928 (cause my poor english I cannot describe it TAT)

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

          int min1=a[0].first+a[1].first+(i==1?h:0);

          This give me accepted. thx

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

            oh no I misunderstood the problem,I thought f(i,j)=Ai+Aj+h if at least one of i and j is in the first subsequence!!Ahhh terrible~~~~~

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

Where else can i find the current contest questions being discussed????????

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

Сложный раунд=(

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

    if this was an answer to my question then sir plzzzzz give link coz i dont understand Russian............plzzzzzzz provide the link.......

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

      You should use translator or simply skip comments in Russian ;)

      He wrote something about 'complex round =('

      And... here is right place to discuss this round's problems

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

Почему в С не заходит такое

  • Переберем одну из вершин ответа, посчитаем все достижимые из нее
  • Недостижимые вершины распадутся на деревья внутри них посчитаем для каждой вершины стоимость достичь все вершины данного дерева (кол-во ребер, котрое необходимо повернуть)
  • Посчитаем стоимость достичь все вершины каждого поддерева из корня этого поддерева (если дерево подвешено за фиксированную вершину из пункта 1)
  • Переберем вторую вершину ответа, посмотрим, как ее выбор улучшает ответ.

ВА8.

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

    Не очень понятно, но ошибка скорее всего в том, что от второй вершины может быть много достижимо вверх по дереву если исправить некоторые правильные ребра при данном корне на обратные. Пример
    9
    1 2
    3 2
    4 3
    5 4
    5 6
    7 6
    8 7
    9 8
    1 10
    1 11
    1 12
    1 13
    При фиксированной первой вершине 1 можно выбрать второй вершину 9 и исправить только одно ребро 5 6. Не знаю валит ли этот тест все решение в целом если перебирать остальные вершины, но надеюсь, это то, что нужно.

    Вот еще один тест на котором я получил удачный взлом:
    15
    2 1
    3 2
    4 3
    4 5
    6 5
    7 6
    8 7
    9 1
    10 9
    11 10
    11 12
    13 12
    14 13
    15 14
    Может он больше поможет.

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

      там чушь

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

        По сути я такое же сдал, только почему подотрезок с максимальной суммой? Нам нужно минимальное количество элементов поменять на противоположные, чтобы вектор принял вид (сначала сколько-то -1, потом сколько-то 1).

        Ну и ещё все остальные поддеревья тоже надо учитывать.

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

      Спасибо за тесты. на первом у меня 1, на втором 4. 4 — это правильно?

      И я не совсем понял, что вы имеете в виду. Зачем нам идти вверх по дереву? Ведь мы затратим строго больше поворотов ребер, потому что при спуске в недоступные из корня поддеревья мы все равно повернем те ребра, которые нужно повернуть, чтобы эти вершины были доступны из корня.

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

        На втором тесте ответ 2 — надо свапнуть (4 5) и (11 12)

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

Как решать Е (div 2) ?

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

    Зафиксируем одну вершину из ответа и подвесим за неё дерево. Для каждой вершины посчитаем сколько ребёр, направленных "вверх" в её поддереве и запустим dfs. Пусть мы хотим узнать ответ для корня и текущей вершины в обходе. Понятно, что все рёбра, не находящиеся на пути из корня до этой вершины надо просто повернуть, иначе никак. Далее посмотрим на путь от корня до вершины(обозначим за 1 — рёбра вверх, за 0 — иначе) и представим, что мы считаем di — сколько надо сделать операций, чтобы все рёбра до i - го повернуть вниз, остальные (на пути) повернуть вверх. di — количество единиц на [0, i] + количество нулей на [i + 1, end]. Надо только узнавать минимум в этом массиве для текущей вершины за O(1). Заметим, что когда мы добавляем в конец массива d ноль (проходим по правильному ребру), то к минимуму в нём добавляется единица (ко всем значениям +1 на самом деле), а значение нового равно значению последнего (количество единиц осталось таким же). Если проходим по ребру "вверх", то в конец добавляется единица, значение остальных di остаётся таким же, значение нового — это значение последнего +1. Всё это просто можно передавать в dfs.
    Вот, дописал через 5 минут после конца вчера)

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

where can I find the solutions to the problems in contests?

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

Какой ответ в задаче С (для div.1 А) при n = 100000 и m = 60083? Все решения, прошедшие полное тестирование дают ответ 0, хотя там никак 0 не может быть, или я что-то не так понял/не смог понять?
UPD: более формально это все такие m и n, что

(2 ^ m) % mod < n && 2 ^ m > n
  • »
    »
    12 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    Скорее всего, 0 там получился вследствие одного из 99999 умножений по модулю 10^9+9, поэтому дальнейшие умножения ничего не изменили. Или просто (2^60083-1) mod 10^9+9 < 99999, тогда начальный множитель при уменьшении 100% когда-то дойдет до нуля и обратит в ноль все произведение.

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

      Выходит, что 0 получается, когда один из множителей (2^m — i) кратен модулю?

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

        Да, но это можно проще сформулировать — если n > (2^m-1 mod 10^9+9).

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

Is there any editorials?

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

UPD Ok it's published now

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

hey guys can anyone tell me how to solve Div 2 Problem C

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

    try to make a new sequence of n numbers for each valid answer sequence that i'th element of new sequence would be equal to xor of first i elements of answer sequence . each element of new sequence will be different form others and it's between 1 and 2^m -1 ... so for every n and m number of answer sequences would be equal to this :

    (2^m -1)*(2^m -2)*...*(2^m -n)

    I hope this will help you :)

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

      I can't get the first sentence at all...did you really mean the second word "sequence"? Each element of new sequence will be different from others? Are you sure? I thought (1,2,1,2) is valid since 1^2^1^2 == 0.

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

        But the request is to count the sequences that are NOT a wool sequence...So (1,2,1,2) is invalid..

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

When the next contest start?