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

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

Привет, Codeforces! :-{D

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

Этот раунд подготовил я (havaliza), dani1373 и keivan, также нам помогал fab. Я хочу поблагодарить всю команду Codeforces за их усилия в поддержании этого веб-сайта.

Надеюсь вам понравится решать задачи так же, как нам понравилось их готовить! ^.^

Update 1. Распределение баллов по задачам в Div. 1: 500-1000-1500-2500-2500, в Div. 2 распределение стандартное.

Update 2. Большое спасибо пользователю Aksenov239, который очень много помогал нам в подготовке раунда.

Update 3. Here is the editorial. To be completed soon :)

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

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

Good time for Chinese!

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

Nice moustache :)

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

'#198' ?

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

Wish you 4 shiny gold medals :-) I believe the contest is going to be one of the greatest.

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

Thanks to the early time because I have an exam on 24th morning. :D

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

I'm going to be travelling at the time of the contest... which, of course, doesn't mean I'm giving up on doing it. As long as I get internet connection in a train...

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

early time is good! since there is cookoff also on codechef.

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

Email I've just received says that round will be today (22.06.2013). A bit confusing. Is something wrong with my calendar?

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

Change tag, it's wrong.

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

worst time for Iran I guess. Nobody can participate :( . Everybody is in the club :D

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

I want to see you in IOI!!

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

This time we do both the contest codechef/cookoff and codeforces Div I/II round Really good timing :)

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

I hope the english will be understandable this time! :)

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

Ну вот, щас на кф ещё и систему ЕГЭ введут... а преподы из школ будут следить, чтобы мы не списывали.. :)

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

I'm sorry, but what was popped out?

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

    If you mean a JavaScript alert that popped out about 30 minutes ago (for me), it's a change to the rules:

    Attempting to digitally extract other contestant's code during the hacking is considered cheating. You may not use any technical/digital tools to obtain other contestant's code, including (but not limited) ORC, traffic capture, browsers plugins and so on. The only allowed method to analyze other contestant's solution is reading it in a hacking window. However it is allowed to manually retype the solution or it's parts to run it locally.

    (Can-do's and Can't-do's, item 8)

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

    If you mean the pop-up a few minutes ago, the theme of the announcement was 'Hacking during the contest'. It said, that we aren't allowed to use any technical help in form of tools etc. to extract defenders code. We are only allowed to analyse it by looking or we may also write parts of the code down manually. Edit: ah, a few seconds too late.

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

    copying contestant's code to hack using any plug-in is considered cheating, but it's OK to retype it

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

А что за оповещение было?

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

    Глупо задавать такой вопрос, если уже прочитал это оповещение, тем более не в том топике.

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

Количество зарегистрированных во втором дивизионе равно моему году рождения — надеюсь это хороший знак=)

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

На странице «Основное» в контесте каждое оповещение показывается по два раза.

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

Очень обидное было падение Кодефорса в последние 5 минут. Отправить посылку так и не удалось...

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

Ahhhh, having to look at "Codeforces is temporary unavailable Possibly the server is too busy, something has gone wrong or it is server maintenance. Anyway try again in a few moments. " during the closing stages of the competition, when trying to submit a solution wasn't too enjoyable :(

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

Хм, последние 10 минут челленджить было совершенно невозможно, codeforces стабильно лежал... Жаль.

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

Соревнование закончилось, я уже мог смотреть чужой код, и все после этого возобновилось на 8 минут.

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

I hate those moments when I think I did well in contest and it's unrated because of server problems :-(

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

Is pretest 2 at problem E (div 1) correct? I don't see any solution passing it.

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

    I passed and I got WA on pretest6 ...

    And I found that I may got WA on this test

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

    The answer should be
    NO
    YES

    But sometimes even i passed this case, i got WA on pretest2 again.

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

      This test is incorrect — interval lengths have to be increasing.

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

        Hmm.. I didn't consider that, sorry for the mistake.

        But if I swap the second line and third line.

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

        Should it be YES, NO ?

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

Кстати, а что за странную симуляцию с очередями народ писал во 2ой задаче? С виду она работает за квадрат, но почему-то тесты против квадрата проходит... Я так 3 неудачных челленджа получил, и так и не понял, в чём прикол.

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

    Я смог посмотреть решения других людей, прежде чем контест продлили на 10 минут. Это нормально ?

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

    Да, кстати? Учитывая то, что раунд еще идёт, а решения можно было посмотреть, наверное, стоит сделать его всё же нерейтинговым.

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

      Зачем нерейтинговым? Почему бы просто не аннулировать посылки за последние 10 мин?

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

        Зачем тогда продлевать было :)

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

          Все равно лучше, да и навряд ли много людей успели за это время понять решение(или переписать) и сдать

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

          Продлевать надо было из-за нестабильной работы Codeforces на последних минутах. Но получилась вот такая не очень приятная ситуация. Думаю, что в данном случае, аннулировать сабмиты будет неплохим компромиссом.

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

    Я писал странную симуляцию, но без очередей, просто после каждого хода я отмечал тех, кто в этот раз кого-то убил, и в следующий раз рассматривал только их. Поскольку если человек никого не убил, то больше уже и не убьёт, ему остаётся только ждать смерти или конца игры. Это будет работать за линию, потому что количество убийств — O(n), и количество раз, когда мы убедились, что человек больше никого не убьёт и выкинули его из списка — тоже O(n).

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

      А как быстро отмечать тех, кто хоть кого-то убил?

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

        Это-то как раз легко. Пробегаемся по всему списку, если справа от человека человек с меньшим номером, то это убийство. Потом надо выкинуть тех, кого убили. Подходящая структура, где легко выкидывать людей из списка — список на массиве.

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

          А разве оно не будет получать TL на тесте:

          100000
          100000 1 2 3 ... 99999
          
          • »
            »
            »
            »
            »
            »
            11 лет назад, # ^ |
              Проголосовать: нравится +14 Проголосовать: не нравится

            После первого прохода останется только 1 "убивающий" и все оставшиеся итерации будут за одно сравнение и удаление.

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

              Мне кто-нибудь объяснит, в чем именно я ошибся комментом выше, или будут дальше продолжать минусовать?

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

              Совершенно верно, в списке убивших на первом ходу останется только первый, и дальнейшие итерации будут происходить за O(1).

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

          А разве оно не будет получать TL на тесте:

          100000  
          100000 99999 99998 ... 1.
          
          • »
            »
            »
            »
            »
            »
            11 лет назад, # ^ |
              Проголосовать: нравится +8 Проголосовать: не нравится

            Этот тест вообще после первого хода превращается в [100000].

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

          Круто, я пытался на простом списке сделать, погряз в реализации. Хрень всякая лезла постоянно, типа того, чтобы не вмазать не по той памяти. А на массиве все очень легко пишется) Спасибо. Очередная прикольная идея для олимпиадной проги)

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

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

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

i was able to see someone's solution for D. handle is sn23581. I think many of coders have seen solutions. As codeforces allowed to see. You can check the log.

I think , the contest should be unrated, or make it unrated for me or other who have seen other's code.

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

Jun 23, 2013 7:01:33 PM Announcement General announcement ***** The round is extended for 10 minutes.

Announcement came after the contest ended.

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

I think this Contest should canceled I saw solutions of some contests before time extention i saw fog solution in C he use array called deg & his solution contain one loop only i just talk about this to ensure that some contests show solutions during this small period of time before you extend time Thanks

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

Actually, I do not understand why contest is extended, because a lot of coders saw other participants solutions, so they can send them now.

I think the best solution is to make contest unrated or delete submissions and challenges after 01:59.

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

No, please don't make the contest unrated. Not again :( There were too many unrated rounds in the last period. Also, as I can see, no other solutions for problem D were submitted after the contest was extended, so I don't see any problems (even if some people saw the source code, as long as no submissions were made, I think it's ok).

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

    I think that cancelling the submissions made after the contest ended (01:59) would be the best solution. Also, please tell us as soon as a decision is taken.

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

    you speak in your case , not generally , in Div2 i saw Problem "C" solution so if i submit it and gain points and my rate increased you don't mind about this ?

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

      I just said that the submissions/hacks should be ignored. I don't see any problem in that case.

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

        But what about those who cannot submit the solution in last minutes of the contest?

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

          It is the same for everybody. I don't think that the contest should be unrated just because it was 2 minutes shorter.

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

      Why do you insist so much, perhaps because you solved just one task? :P I would like to see if your reaction would've been the same with you having 3 tasks solved.

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

I am so silly that I thought I could AC pE.

After I got WA for long time, I found out that I didn't clearly understand the porblem... so sad.

for the case: I1 (0,5) and I2 (2,3), query I1 I2 is NO, query I2 I1 is YES..

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

I can open the code of others in the first minute after contest. But I do not know the contest is still running, because the announcement is not shown in the standing page. :(

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

I think it's possible to make this round rated by ignoring all submissions or hacks after extending;if the system can do it!

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

    But the contest was extended, because there were problems with server in the end of the contest and while someone was not able to submit his solution in last 5 minutes in contest it would be unfair for them.

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

      That makes sense. Now I'm wondering how many (cheating) solutions are there... I hope they're few and it's rated...

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

        I'm not telling those are cheater, but I was 33rd and when the contest was extended I finished 44th so 11 coders needed that time...

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

It would be unfair to leave this situation as it is now, because a lot of people left their computers immediately after the end of contest.

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

hope this contest will not be unrated !!!

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

to solve div2 E /div1 C :

the key is to use B[n]=0 advantage so the problem is reduced to:

what is the minimum cost to completely cut the n'th tree

let's reverse the trees (also A and B arrays)

dp[i] means minimum cost to cut tree 1 (which was n before reversing) using only trees from 1 to i assuming A[i]=1

we have:

dp[i]=min for all j<i(dp[j]+B[i]*A[j]);

using convex hull trick we have O(n) solution.

but I had very bad luck getting WA on test 3 :(

please help me 3950250

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

FFFFFFFFFFFFFFFUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU

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

Writers, thank for the contest ;-)

Except the dance club which I didn't understand, the problems were really nice ;-)

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

About Psychos in a Line Div1B/Div2D

How to pass a case like follow:

100000
100000 1 2 ... 99997 99999 99998

My solution will get Time limit exceeded on this case.

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

    One can use generator for this ;-)

    edit: I misunderstood the first version of your question. I thought you are asking how to use it for hacks. Now I cannot remove my comment...

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

    Put i in a queue(kill list) if a[i] > a[next[i]] and i is not dead, then go through the queue and start killing people and update the next[i], you might need to use 2 queues to do this.

    In your tes case, there is only 1 number in the queue every time, so O(n).

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

    Store a list for psychos, who will be killed. And in each turn recreate this list by the previous list(it is possible, because in next turn only those psychos can be killed, who was next after psycho from previous list(who were killed in previous turn))

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

A very interesting contest :)

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

How did you find out the solution for Div1A without using backtrack for small n values? I still don't get why the answer is correct.

Upd: the solution is x·2n - 1. It's not obvious why all these solutions give the same result.

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

    if a > b and a^x < b^x, it is mean that "^x" operation is chenge first different digit in a and b.

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

    If bit i is 1, then A0B > A1C (A contains i — 1 bits, B and C contain n — i bits).

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

    If the first bit of x is 1, we swap two halves of array, that gives us 2n - 1 × 2n - 1 inversions. The i-th bit gives inversions in the same way, but we swap halves of 2i arrays sized 2n - i, for 22n - i inversions. Clear to see every bit is independent from the others.

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

      why?(but we swap halves of 2i arrays sized 2n - i, for 22n - i inversions)

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

        For instance n = 4. Arrays for different i's look like this:

        i = 0:

        (8 9 10 11 12 13 14 15)(0 1 2 3 4 5 6 7)
        

        i = 1:

        (4 5 6 7)(0 1 2 3)|(12 13 14 15)(8 9 10 11)
        

        i = 2:

        (2 3)(0 1)|(6 7)(4 5)|(10 11)(8 9)|(14 15)(12 13)
        

        i = 3:

        (1)(0)|(3)(2)|(5)(4)|(7)(6)|...
        

        Easy to see the pattern here.

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

    I wrote down all the numbers in binary when n = 3 and x = 111, instantly I found the beauty of the answer:)

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

    The least significant bit affects each pair of subsequent numbers ((0)-(1), (2)-(3), (4)-(5), etc): if LSB of x is 1, then we count each pair (2^(n-1) at all), else we don't.

    Next bit affects pairs of subsequent groups of 2 numbers ((0,1)-(2,3); (4,5)-(6,7), etc), each pair of groups adds 2 * 2 pairs.

    And so on: i-th bit affects pairs of subsequent groups of 2^i numbers.

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

    I just solved a simple case by hand:

    101
    
    000 101
    001 100
    010 111
    011 110
    100 001
    101 000
    110 011
    111 010
    
    1 * (4 * 4) + 2 * (0 * 0) + 4 * (1 * 1)
    
  • »
    »
    11 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

    dp[i] — number of bad pairs in set with (2^i) numbers

    dp[i] = (s[i] = 1)·(22i) + 2·dp[i - 1]

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

    so if x[i]==1 must inverse bit, and if x[i] == 0 the bit will not change.

    eg.

    x=10
    MDC    NFC
    00(0)  10(2)
    01(1)  11(3)
    10(2)  00(0)
    11(3)  01(1)
    ans is 4 = 1*2*2
    
    x=01
    MDC    NFC
    00(0)  01(1)
    01(1)  00(0)
    10(2)  11(3)
    11(3)  10(2)
    ans is 2 = 2*1*1
    
    x=11
    MDC    NFC
    00(0)  11(3)
    01(1)  10(2)
    10(2)  01(1)
    11(3)  00(0)
    ans is 6 = 2*1*1 + 1*2*2
    
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I randomly guessed ans+=2^(i+length(n)-2) for '1' in ith digit.

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

Sorry about unfortunate contest ending. We will investigate accounts who saw the other's solutions and accepted code after it. It doesn't look like there are many such participants.

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

    No matter whether this contest will be rated or not, plz start system test first. Many people are waiting for the result anxiously。

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

      Why chinese have different dots(.) ? Before, I saw some chinese writing (?)(.) and some others characters differently. Can you please tell me the reason of this ?

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

        because chinese words and english words are two different systems.

        besides, are you talking 全形碼 。?, <--?

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

          If I understood you correctly ("are you talking about 全形碼 。?"), YES I am talking "?". :)

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

            Chinese is double-byte-character-set, check wiki DBCS, so we Chinese makes everything double bytes. like 。。。,,,!!!???Even this: Hello World.

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

        check this and this

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

    really, can you do it after systest? It is rather more interesting for most copetitors.

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

    What about people who left their computers immediately after finish of the contest?

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

    I wrote a lot of scripts and found that no more than 8 persons from both divisions tried to see other's solutions and passed system tests after it. So I don't see any reason to make it unrated for all. Sorry again about the issue.

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

    I think that it's quite unfair to distinguish those participants who have accepted their solutions after viewing the other's code and those who haven't viewed code in "intermission" but have also got accepted verdict. The reason is that one cannot be sure that they won't be able to get accepted without viewing the other's code. So, to my mind, they shouldn't suffer from the fact that they have viewed it.

    P.S. I don't refer to any of above-mentioned groups.

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

Да плевал я на рейтинговость контеста, давайте уже систест!

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

Кстати, мне одному кажется, что задача div.1 C пугающе похожа на 311B - Транспортировка кошек? Я имею в виду решение.

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

What is the Test 5 in B DIV2? I send an O (n ^ 3) and I have TLE, with n = 100??

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

    Mine is O(n^3.5) ans passed in in 15ms, so you are the one slowing down the system test...

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

    I think that a solution in O(N^4) should pass because 10^8 can pass in two seconds, indeed my solution is O(N^4)

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

Thanks for interesting problems!

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

I think have an unique DP method to the problem A div1. 3951181

I don't know if ther is other people use this method...

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

It seems many competitor passed Problem D by simple brute force.

I wonder if it is the expected right solution or the test cases are weak?

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

    It's third or fourth contest, that contains the problem, which has n ≤ 50000 or n ≤ 100000, and you have to solve using simple straightforward algorithm, and optimize it.

    I don't know if it's good or bad, but all thinking skills you have to use when solving the problem are useless here, you just have to optimize it well.

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

      And you have also to notice that the TL is large enough :( I didn't see it in time and wasted plenty of time thinking over a fast solution.

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

        Yes, 6 seconds tell you: "man, O(n^2) should be the right solution".

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

      well,but how can that worth 2500 points...

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

        Only seven participants solved the problem. It's fair enough.

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

        :) well, I have the same question.

        By the way, I guess that there is solution. I'm not sure, but I guess, that you can find the shortest tandem repeat in the string like the algorithm for the longest one, and then remove all tandem repeats using linear algorithm. There will be such tandem repeat lengths.

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

    I have c*n^2 + n^1.5 but c is small enough (4 seconds). But it's not a simple bruteforce.)

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

    The actual solution has time complexity O(nsqrt(n)log(n)) and we didn't expect bruteforce solutions to pass the tests. Actually we're not ok with what happened! :(

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

      And what is the work time of this solution? I guess, it's not much faster, than bruteforce.

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

    Hi, actually I think I have a O(n^1.5+nlg^2n) solution. The nlg^n part took me too long to think of during the contest, so I was not able to finish it during contest time. The latter part requires hash, though.

    The idea is that:

    1. Note that we can implement a function cut(d) that given a length d, cut according the rule all XX s.t. length(X)=d. This should not be too hard so I'll skip the detail. The time required is O(n).

    2. Suppose you have a oracle function foretell(d), that could tell you (ignore how for the time begin) in a fast enough time, whether there exists X | length(X)=d s.t. XX is in S. Once you have this, the rest is simple. Because if we only call cut(d) on d | foretell(d)=true, then there will be at most O(n^0.5) calls.

    3. So the question remain: how fast can foretell(d) be? I came up with an overall O(n/d*lgd) one, and I think there may be better solution. Anyway my version is: For each d, partition the (current) S into segments where each except possibly the last is of length d. Then for each endpoint x of segments, we record two things:

    • left_extend[x] = max{l|s[x-l..x]=s[x+d-l..x+d],l<=d};
    • right_extend[x] = max{l|s[x..x+r]=s[x+d..x+d+r]},l<=d];

    These could be obtained by binary search + hash (hmm..), and we just need to check whether there is x s.t. left_extend[x]+right_extend[x]>=d.

    The overall runtime is clearly O(n^1.5+nlg^n), and could pass systest in a mere 109ms. I wonder if there is something better (in runtime / don't require hash .. etc) in the latter part though. Anticipating for great opinions.

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

      After each change of the string S (and the beginning), build suffix array of S. By the properties, we only build the suffix array times.

      Then right_extend[x] can be calculated in O(1) by finding the LCP (RMQ) of suffix(x) and suffix(x + d).

      left_extend[x] can be calculated similarly using suffix array of reverse(S).

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

        Good point and thanks!!

        Now we really have a totally reasonable solution (and without hash!) that could run well below the time limit.

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

Has it been made official whether or not this contest will be rated?

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

Disclaimer: rather angry and loud comment follows.

WHY THE HELL?

Good problems, great social platform, but still going down during rounds. What's the problem? Slow code? You're programmers, optimize it! You cannot, because you need 'readable' code? Damn it, the website doesn't work during rounds, who cares about program's code if it doesn't work?

Too much users? Set limit of participants, like TopCoder do. At least rounds will be reasonably rated.

Not enough servers? VK offered you, not even once. If your code is good, it should be easy to scale on 10 servers.

Please, stop being prideful and make Codeforces a stable system!

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

Эх, недолго я побыл желтым =(

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

Is the contest unrated?

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

my dfs solution for problem B div 2 failed on test 5 because I didn't pass the visited vector by reference to the dfs function :(

is this something to be expected?

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

    There should be vector <bool> &visited in the runDFS declaration:

    3951797

    Otherwise, it just creates a copy of your vivsited array for every function call, which means u get additioncal O(visited size * times RunDFS is called).

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

What was the point of restricting Div2 B (ping pong easy) problem with increasing segment lengths?

Did we have to use that in the optimal solution?

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

    I think, it's important for "ping pong hard" problem from Div1. Statements are the same except n's range.

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

      It can be promise that the interval you add in the future would not be full covered by the interval you had added.

      So you only have to consider what intervals it can conneceted. And the interval you connected can go to each other... (it should be a<c<b<d, not a<c<d<b)

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

Will someone give some hints/explanation for Div 2 D (psychos in a line)? Thanks!

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

    I took pen and paper and for each psychos wrote down when he will be killed and in which step. Do it and you will understand what to do. Another hint is you may need segment tree.

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

      I completed it without tree with O(n) and without turn simulation.

      I set their targets onto the next psycho and then let right ones kill as long as they can, taking targets of their victims to skip dead. As kills are made every turn, maximum number of kills is answer. The only problem was that already dead psychos kept killing but I solved that with giving those kills to their killers as they would grab them later anyways. Targets can be changed only N times(after kills).

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

      How can one use a segment tree here?

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

        Consider the initial line of all psychos. Let us choose the psycho that has the highest ID number. Now you can divide the initial task in two parts: (a) solve the task for the line of psychos to the left of the psycho with the highest ID (excluding him); (b) solve the task for the line of psychos to the right of the psycho with the highest ID (including him).

        The answer to the initial task will be the maximum from the answers to sub-tasks (a) and (b).

        In order to solve sub-tasks like (a) and (b) you can keep recursively dividing any (sub)line of psychos in two parts, around the psycho with the highest ID in this line. For the purpose of finding such psycho every time you can use a segment tree.

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

Please, help me understand, I think I didn't get well the problem. In the problem B of DIV2, test case #4:

20
1 1208 1583
1 -258 729
1 -409 1201
1 194 1938
1 -958 1575
1 -1466 1752
2 1 2
2 1 2
2 6 5
1 -1870 1881
1 -2002 2749
1 -2002 2984
1 -2002 3293
2 2 4
2 8 10
2 9 6
1 -2002 3572
1 -2002 4175
1 -2002 4452
1 -2002 4605

How does the last '2' query return "NO"?

The segments 9 and 6 (highlighted) are overlapping.

Thanks!

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

An editorial, plz!

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

I hope the editorial is good,detailed and understandable

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

can anyone help me to solve Problem B (Div 1) or Problem D (Div 2). Thanks in advance :)

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

    On each step you must check for abilitiy of kill only for people who kill on the previous step, and then remove killed people. Each man or kill someone or go away from list of killers. Total amount of murders is O(n) and total amount of cases when man go away from killers list is O(n) too.

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

      suppose the test data was-

      5 4 3 2 1 22 20 10 15 14. So after first step the array became-

      5 22 15 . And after second step the array became

      5 22.

      Now how to solve this in O(n). Please explain by taking it as example.

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

      I looked at your AC code here, http://codeforces.me/contest/319/submission/3944800 and your logic made sense. However, I am confused as to why you didn't get TLE on the test case below. A test case that will cause this to be O(n^2) will be 100000 100000 99999 99998 ...

      Unless I violated/misread the problem statement.. was the provided test case too weak?

      [EDIT] here is a sample test case. I copied the exact same code, but replaced the input with pregenerated test case: http://pastebin.com/PJPaK7Da

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

        In this case, everyone will die in the first round itself. It's still O(n). The complexity is the sum of (no. of people who killed someone in the round) over all rounds. To be part of a given round, a person must have killed in the previous round. As the number of killing victims cannot exceed n, the number of killers(counting people who killed twice, twice etc.) cannot exceed n.

        Hence, the complexity is linear. EDIT: In my implementation, it took log(n) time to find the right neighbour of a person. Hence, the complexity would be O(nlogn)

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

          I agree. That's why I upvoted his comment for the same observation you mentioned. However, his implementation for killing (unfortunately) causes it to be O(n^2), which you can try by using the sample test I provided. You can see line 26-28 of http://pastebin.com/PJPaK7Da

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

    my idea: observe that only elements i with a[i]>a[i-1] will not be chopped down in step 1. others will be chopped down instantly

    maintain a linked list X

    run the array once from n to 1 (reverse order)

    assume initial answer to be 0

    if (a[i]<a[i-1]) and i!=1 then answer will be max(answer,1) as at least one step will be taken

    otherwise insert the element to the head of X. To know how many steps he will go on, we try to make the inserted element to chop down the new elements.

    Assume ans2=0 be the moment which the inserted element cannot kill anyone anymrore, On each next element that is smaller than the inserted element, the inserted element can surely chop down it, and ans2=max(the number of steps the previous element need i.e. the previous ans2,max(ans2,1)+1), ans=max(ans2,ans) return ans at last.

    For the test case,

    • 5 X={5,22} ans=max(0,2)=2
    • 4 ans=max(1,2)=2
    • 3 ans=max(1,2)=2
    • 2 ans=max(1,2)=2
    • 1 ans=max(1,2)=2
    • 22 X={22,15}={22} ans=max(2,1)=2
    • 20 ans=max(1,1)=1
    • 10 ans=max(1,1)=1
    • 15 X={15} ans=max(0,1)=1
    • 14 ans=max(1,0)=1

    note that the process runs from bottom to top

    refer to my code 3950756 if you cannot understand my poor english :(

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

I found these two youtube videos really helpful for problem Div 1 E: Seth MacFarlane Take a look and here is another video And this one !

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

Editorial please

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

Hello. Participate in progressive competition in the Caribbean Online Judge! This is the link for more information: http://coj.uci.cu/contest/contestview.xhtml?cid=1301