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

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

Скоро состоится очередной раунд Codeforces Round #284, задачи для которого готовили Виталий Гриднев (gridnevvvit), Илья Лось (IlyaLos), Данил Сагунов (danilka.pro).

Большое спасибо Максиму Ахмедову (Zlobober) за помощь в подготовке задач, Марии Беловой (Delinur) за переводы на английский, Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon.

Будет использоваться динамическая разбалловка. Задачи расположены в порядке возрастания предполагаемой сложности.

Раунд окончен, поздравляем победителей!

Div1:

  1. yeputons
  2. rng_58
  3. Endagorion
  4. KADR
  5. Egor
  6. uwi
  7. mmaxio
  8. atetubou
  9. RAVEman

Div2:

  1. sorry_dreamoon
  2. dreamoon_love_AA
  3. dreamoon_fan

Разбор задач

Удачи!

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

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

Just why on Christmas Eve?

Check out: http://polishchristmasguide.com

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

I will just leave this here: http://codeforces.me/blog/entry/10034#comment-155087

Exactly the same situation as year before or even worse, because year ago time was not that bad, but 19:30 (17:30 in Poland) it's definitely too late. I think you shouldn't expect many Polish coders tomorrow missing one in a year feast and ignoring whole family which gathered in their home.

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

    This. I registered thinking that I have no idea whether I'll find the time to participate...

    although it's a chance for a very good (absolute) place... so much win.

    Also, working name of this contest: basement dweller check.

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

      Don't you think that in all countries except Western Europe and US/Canada nobody cares about celebrating Christmas because New Year is our national holiday? We will not miss you today, take it easy.

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

        New Year is only the main holiday in Russia (and countries with similar traditions), because Julian and Gregorian calendar. It kind of explains why there's a contest on this date, but the argument still stands for most of the world, Central Europe included.

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

        Dude watch yourself when leaving a comment in a site full of Russian.

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

    I also find completely unacceptable that so many contests on Codeforces take place on Fridays after the sunset or on Saturdays before the sunset.

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

I celebrate my birthday today. And I hope, this round will be a gift from CodeForces for me!

GL && HF!:)

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

i am new in codeforces i want to see problems in codeforces round #284

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

Your bets — will dreamoon_love_AA win div2 tomorrow? :)

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

    We 2nd division participants will make sure he doesn't

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

      Haha, div2 guys defeating international grandmaster sounded pretty hilarious, but dreamoon seems to be taking this contest seriously, cause he solved 3 problems, but you are on better position now, so I see that your words were pretty serious :D

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

    Maybe he will cha to get -inf score,and integer overflow to +inf score and get the first place

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

      You shouldn't be drinking so much during christmas .

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

      if the hack points is defined by short, he can do it... if it is int..I think codeforces may break down.... if long long...the internet of the world may break down..What a DDOS!

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

    I bet 100 Quatloos that he won't.

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

    btw,can you imagine that oneday tourist's rating overflow to -inf and worse's rating overflow to +inf?

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

      He would have to take part in atleast 58040011 contests assuming he keeps getting the first rank and the first rank fetches him a gain of 37 points like it happened for his previous contest .

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

    Maybe He/She is challenging worse !

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

Merry Christmas to everyone !

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

Good luck to everybody!

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

dis like me plz

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

Минутка самомотивации — если я сегодня попадаю в желтые и этот коммент в плюсе, то ставлю Азиса на аву:)

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

    У тебя какая-то неправильная мотивация. Измени аватарку, если НЕ сможешь получить желтого :)

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

      Судя по всему, ты вообще не разбираешься в искусстве

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

    Я залажал, сори, Азиса не будет

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

Hi!
thanks gridnevvvit !
your last contest had vary nice problem (Codeforces Round #275):) thanks :)

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

Hope for high rating.

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

Christmas Round && My first CF Round ... Sounds nice ;-) But the time is not convenient for Coders at GMT+8 ... such as China. It is 00:30 to 02:30 , which means we might be very sleepy ...

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

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

Merry Christmas to all :)

All the best for the Round #284.

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

Merry Christmas! GL && HF!

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

Hope to gain some rating points this Christmas ;)

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

Hope to gain some rating points this Christmas ;)

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

I hope all Specialist be candidate master (!) and all Expert be master (!!) and dreamoon_love_AA be grand master !

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

Merry Christmas!

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

Merry Christmas

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

Scoring system will be Dynamic , don't know is it good for me or not ! My curious mind want to know what others think ?

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

Dynamic Scoring.

while(true) System.out.println("NOOOOOOOOOOOOOOOOOOOO");

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

Hope for much [pure] math

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

    (And strong pretests!!)

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

      Eh, well it is a matter of opinion. I personally believe that hacking creates more suspense, especially right after you try to hack someone.

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

We can see about dynamic scoring system here.

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

Seems like tourist didn't register for Div.1 .Could it be that he made a Div.2 account to beat dreamoon_love_AA ? By the way, good luck to everyone, and Merry Christmas !

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

Let's Pa Pa Pa tonight. :D

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

Many Thanks to you <3

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

GL HF

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

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

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

    Аналогичная реакция. В очередной раз жалею что опять попал в Div1. Мне тут совершенно не место.

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

    А на топкодере бы в низ таблицы поместили за такое :)

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

      на топкодере вообще грустно, я там за 5-15 минут решаю первую (див. 1), а дальше без понятия, что делать))

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

        На ТопКодере быстрой первой хватает на красный, на CF такое не прокатит:)

        ИМХО перестарался автор с вчерашней первой задачей. Я-то видел ее месяц назад, но если человек раньше такую или подобную задачу не видел — то "с ноля" она для него будет явно сложнее обычной div1 A. С учетом того, что С-Е выглядят намного проще обычного — я и от А в таком раунде ожидал бы чего-то более простого.

        P.S. Хорошо хоть автор не пошутил и не дал n<=20 вместо n<=300, тогда мы бы увидели много интересных идей по А :)

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

          А по-моему обычная Div1A — требуется быстро увидеть не такую уж и сложную идею (хотя первые мысли наподобие "блиин, чо, надо строить граф чтоли? да вы упоролись там все?!", конечно, могут немного помешать)

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

          Точно, искусственно заниженные ограничения порождают очень бурную фантазию.

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

I have seen the problems and have decided to not participate. I don't see myself solving any problem other than A and B and that's not good enough for me. Maybe, I will have better luck next time.

GG.

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

sorry_dreamoon is now at first place! dreamoon_love_AA's only chance now is to solve E quickly and find lots of hacks!

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

In first 2 problems(div.2) the limits of numbers were to low...

so all coders will accept them by terrible codes...

It's the reason of less hacks than other contests...

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

dreamoon_love_AA has solved all 5 problems now. He needs to find 5 hacks to get to first place. He has currently locked C. I think that is a very good choice.

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

How hard it is!!! Poor rating...

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

contest is not attractive :( without Top rank in Div2 :)

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

interesting competition between sorry_dreamoon and dreamoon

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

I just want to know who is sorry_dreamoon :P Comment guesses :D

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

Highlight of this match: will sorry_dreamoon beat dreamoon_love_AA? There's probably no way for hacks to change the current situation, but there are still pretests! What if one (or both) fail something? Resubmissions are also possible...

Find out next time, on Dragon Ball Z!

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

liymsheep on the lines of worse

Doing so many unsuccessful hacks, so the first three contestants will have dreamoon in their handle name :D

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

    It's such sad story...after letting the top 3 places to dreamoons, liymsheep fails D him/herself and becomes 10th instead of 4th :(

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

What a Christmas gift!!!

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

It was a nice contest! easy problems A & B and normal Problem C!

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

    If I'm not mistaken, Array and Operations was a maximum matching problem (so maxflow). You separate each number into its primes, and then built a tree based on that, and find the maxflow.

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

      Wait really? This is what I did (hope it doesn't time out), but since it doesn't use the i+j is odd condition (AFAIK), I was assuming it wasn't the intended solution...

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

        @waterfalls it should be using the i+j condition...

        Well some people did it in <=7 minutes, so this may be a harder way to solve it.

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

        The i + j odd condition just enforces a bipartite graph. I don't think it was really necessary, but maybe there was a simpler solution if you took advantage of that.

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

      How is the tree built?

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

        What I did is the following:

        1. Make a supersource and supersink.

        2. Make two*n nodes, one in-node and one out-node for each number in A.

        3. Connect the supersource to all the in-nodes, and the out-nodes to the supersink, with capacities equal to the number of factors of the prime p being considered.

        4. Connect, for each pair, each in-node to each out-node, with capacity equal to the number of factors of p the number in A shares.

        5. Find the maxflow of this.

        6. Divide by 2 (everything is counted twice)

        Nooooo WA on test #26 -> took like a minute to fix it... (for those who are wondering, with big primes must run maxflow again instead of just counting pairs that work and removing, which I did because I incorrectly thought since each could only have one of a prime, it would be ok)

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

Правда, что можно было в E запихать 700000*2^7? У меня вот было 2200мс на макс тесте на джаве, пришлось переписывать :(

Да, если каждый раз не создавать заново массив, то выходит заметное ускорение...

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

    Как ее решать за 700000*2^7? Я умею только за 700000*(2^7)^2 и за 7*(2^7)^3*log2(100000).

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

      Ну 700000*(2^7)^2 это видимо решение, в котором за один шаг динамики добавляется слой клеток, а можно по одной клетке добавлять.

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

        А, точно.

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

        Ну там еще тогда надо на 7 умножить, а если учитывать переход, то еще на 4. У меня такое не заходило в 2 секунды, пришлось добавлять возведение матрицы в степень. Хотя люди ниже пишут, что у них успевало, так что может это я криво написал.

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

    Мое решение с такой асимптотикой в запуске на макстесте работает около 1700 ms. 9258359

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

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

Div. 2 Problem C. I thought that answer is number of lines between two points. Where i am wrong?

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

Epic Standings . Sorry Dreamoon

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

So sad

Got D solution produced correct answer for sample case after the deadline 2 seconds !!!!

I use 60 segment trees (for all the possible modulo).

UPD: that code got Accepted T_T. Life is so harsh.

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

Is this contest too?

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

I think that sorry_dreamoon is another account of dreamoon_love_AA

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

It is a bit annoying that there are a little hacks int the 2nd division

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

Nice problem thanks gridnevvvit!

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

Happy Christmas Everyone!!

Especially to dreamoon... Awesome scoreline XD

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

The only fail of the contest factor of ax!

The most fun part of it is I asked once about it and they gave me no comments. Anyone else had the same problem?

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

How to solve DIV 2 D?

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

Look at my submission 9258135 , I forgot to remove the "freopen", surprisingly my code outputs zero instead of getting RTE on test 1. and unfortunately because the answer of first test is zero I got WA on test 2 making me lose 50 points.

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

I got 'judgement failed' on my submission for Div1 B: http://codeforces.me/contest/498/submission/9246565. What does this mean?

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

Contest in hack is not !!!

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

Mery Christmas :) Good problems!

But Today, I'm not lucky (I've been seen dinosaurs on chrome :D)

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

    Same thing happened with me, I know how it feels when you finish both the problems in 10 mins and can't submit till 20 mins due those dinosaurs, btw Merry Christmas :)

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

Poor dreamoon_love_AA, he still can't win a codeforces round...

sorry_dreamoon named all his class as Dreamoon... maybe he does love dreamoon_love_AA...

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

I dont know dreamoon But It's for him/her (...)

I hope best ranks in goodbye 2014 for you :D

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

Merry Christmas dreamoon_love_AA!

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

http://codeforces.me/contest/499/submission/9254466

can someone point out why its giving wrong answer?

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

I have a gut feeling that dreamoon_love_AA will again try to return to Div. 2 in the next contest.

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

dreamoon_fan is also there, is it possible to change your handle??

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

is tourist sorry_dreamoon ? Because sorry_dreamoon finished the contest in 48 minutes.

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

    Take a look at top of div1 standings. There are quite a lot of contestants who did div1A-div1C in less than 48 minutes, so it is clear that you don't need to be a tourist to solve div2 problemset in 48 minutes (even if you still need to be a strong contestant to achieve this).

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

      And the codes were is JAVA, i dont think tourist would have done that, even though thats not hard for a redcoder!!

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

    Too sad.

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

    I think sharing Personal talks publicly is not cool.

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

pls,plz,pls,plz

dis like me plz

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

Is dreamoon_love_AA girl or boy?

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

A little bug in my submission for problem A div.1 ...
I want to kill myself now :D

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

Rating Updated.

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

sorry_dreamoon . Please can you reveal yourself .

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

After 42 contests I finally reached Div1. What a great Christmas gift! :)

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

во 2 диве чет подразнительна =)

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

Div.1 B is really hard to understand for me... Sad story...

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

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

The amount of dreamoon_love_AA is too damn high

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

Div2 only top 3 ... Why? because... dreamoon :)

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

Many O(nT) solutions for Div.1 B get TLE...I think the time limit is a bit tight, or maybe there is a solution faster than O(nT)?

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

    That's indeed the case, TL is quite evil IMO. Many solutions encounter problem with double performance for small numbers (it is well-known that double arithmetic is much slower if numbers are very small); in this particular problem the issue results in ~2 times slower running time. E.g.: this 9261764 gets TLE, while this one 9261771 (the same with rounding numbers below 1E-200 to 0) — AC in 483ms. Moreover, compiler choice matters; the same solution in Java 7: 9261791 (I guess it's because the startup time of Java VM is accounted to TL).

    In general, many failed B's were due to TLE for random reasons, and the actual running time was borderline. Increasing TL to 2s would resolve this. So I wonder why the TL was set to 1s, what wrong solution did jury try to kill? The only TLE-incorrect solution I can think of is O(nT2), which would run forever. It's sad that even good problemsetters continue to set TL without thinking, randomly killing many correct solutions as a result.

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

Can anyone explain me Div 2 E which involves Max. Flow? I was trying the greedy approach, which is wrong. (Realized after system test. :P)

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

    Here's what I did, which isn't the same as the editorial, but I find it easier to understand. (I got WA26 due to a small bug, but got it AC after) EDIT: See here for a more detailed explanation.

    For each prime that divides some a[i], we make a flow graph and find the number of operations that can be made using only that prime. The first thing to notice is that it is best if v is always a prime, since otherwise that operation could be split into operations using v's prime factors. Then,

    1. Make a supersource and supersink.

    2. Make two*n nodes, one in-node and one out-node for each number in a.

    3. Connect the supersource to all the in-nodes, and the out-nodes to the supersink, with capacities equal to the number of factors of the prime p being considered.

    4. Connect, for each pair i,j given, each in-node to each out-node, with capacity equal to the number of factors of p the number in A shares.

    5. Find the maxflow of this. A flow from an in-node to an out-node corresponds to using some prime factors of the two numbers the nodes represent in an operation.

    6. Divide by 2 (everything is counted twice)

    I'm not sure how clear this is, so feel free to ask questions (particularly on the modelling which I didn't really explain.

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

      Actually, there is no need to make 2n nodes. According to the statement, the sum of each pair is odd, so one of the numbers is odd and another is even. That's why the given graph is bipartite, and more than that, the first part contains the numbers with odd indices, and another — with even ones. So we can make edges from superstore to the ventices with odd indices, from the vertices with even indices to supersink and the given edges, directed from odd to even vertex.

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

        Ah ok that's why i+j is always odd... (I did think if there was a way to split the nodes to avoid an in and out node, but came up with nothing)

        Why would such a condition be added if it only helped a little bit with implementation (if at all, I'm not sure it would have been easier with the cases involved)? Was there another solution that used it more?

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

          Without having i + j is odd. Graph might had triangles. That's why one can not use bipartite matching anymore.

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

          How does your flow solution ensure that if we are sending k flow down (i in) -> (j out), we are also sending exactly k flow down (j in) -> (i out)? Surely for any feasible solution they should be equal, otherwise you can do crazy things with e.g. a triangle graph and get an answer that is actually impossible.

          For example, your accepted code fails with this non-bipartite-graph test case:

          6 6
          2 2 2 2 2 2
          1 2
          1 3
          2 3
          4 5
          4 6
          5 6
          

          On a bipartite graph this does not matter because your flow graph is essentially just two bipartite graphs that are equivalent (i.e. even positions on one side, odd positions on the other side, edges represent number of prime factor p shared), with one being the mirror of the other, so you are guaranteed to get 2X the correct answer.

          If it's not a bipartite graph, then the problem essentially reduces to maximum matching on a general graph, which is not solved with flow as far as I know. See 9250097 for example on solving it for the general case.

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

      Hey waterfalls, I didn't quite understand the graph making part. Let me ask some clarifications.

      For each prime that divides some a[i], we make a flow graph and find the number of operations that can be made using only that prime.

      Connect the supersource to all the in-nodes, and the out-nodes to the supersink, with capacities equal to the number of factors of the prime p being considered.

      I didn't understand those two parts properly. Would you please explain with a sample test case?

      Thank you.

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

        Here is what I did:

        (The number of p in A[i] means the number of times A[i] can be divided by p)

        1. Make a source and sink node.

        2. Add a directed edge from source to all nodes with odd index i. The capacity of each edge is the number of p in A[i].

        3. Add a directed edge from sink with all nodes to even index i. The capacity of each edge is the number of p in A[i].

        4. For each good pair (i,j), add an edge from an odd indexed node to even indexed node. (If the good pair is (3,4), add an edge from 3 to 4. If (6,7), add an edge from 7 to 6) The capacity of each edge is the number of p in gcd(A[i],A[j])

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

        Although some of my reasoning was wrong, as ikbal pointed out above, I'll try to explain this (if HidenoriS didn't already clear it up)

        Basically, you want each operation to be made on a prime. Then, split the operations into the different primes to perform them on. This results, for each prime, in a different (but similar) problem:

        Given b[i] for 1 ≤ i ≤ n, (here b[i] is the number of factors of the prime in a[i]) and m good pairs, find the number of operations you can do where each operation consists of subtracting the same number from both numbers in the pair.

        For this, use flow. Make a supersource and supersink, and (I'll use the even-odd thing now) connect the supersource to the odds, and the evens to the supersink. To ensure the flow is limited by the factors of p (which is just b[i]), make the capacity of the flow from any node representing i to the supersource/supersink equal to b[i]. Then, for each good pair connect the two nodes, with capacity equal to the minimum of the numbers of factors of p (which is (min(b[i], b[j])).

        Running maxflow on this from the supersource to the supersink gives the number of operations that can be made with a certain prime p, and repeat for all primes.

        Sample:

        3 2 8 12 8 1 2 2 3

        Here, a = {8, 12, 8}. Consider the prime p = 2. The resulting b = {3, 2, 3} (the number of factors of 2). Now, the flow graph looks like this:

        flow graph

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

Where are the editorial ?? :/

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

When could I get the editorial for 284 div 2?

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

Оказалось, что победить в DIV2 не по силам даже "бывшему" IGM-у.
Все обсуждают "забавный" DIV2 TOP3, но не нашел ни одного комментария о том, что юзеры
sorry_dreamoon, dreamoon_fan и, возможно, MoonShooter
грубо нарушили правила Codeforces, умышленно создавая дополнительные аккаунты.
На мой взгляд, это неплохой повод для показательной порки, подобной этой.
А честного человека dreamoon_love_AA жаль: пять раундов сливал, чтобы в DIV2 поучаствовать на "законных основаниях", а какие-то читеры понабежали и зарегались за 5 часов до раунда..

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

    Это всё разумно (хотя тут в тему другой пост), но интересны даже не конкретные читеры, а что можно сделать с правилами, чтобы (1) их выполнение реально было проконтролировать и (2) с ними такой чит не хотелось делать. Сейчас, очевидно, ресурсов + желания разбираться даже с чёрными участниками в каждом топе Div2 не хватает, и фактического контроля за исполнением правила о множественных аккаунтах нет.

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

      Всех читеров не поймать и не наказать, это очевидно.
      Но периодические козни с выставлением у позорного столба заведомо очевидных нарушителей не сильно, но будут сдерживать других потенциальных желающих от всяких гадостей.
      Про "проконтролировать": спалили же как-то WJMZBMR-а, значит возможно.

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

        Ну видно же, что это не работает. Сколько в день появляется нарушителей этого правила — и сколько минут потратил MikeMirzayanov, чтобы в итоге появился тот пост про YuukaKazami-а. Несопоставимо.

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

        После этого сценарий «хотел нарушить, но испугался» кажется довольно невероятным. Нужно специально искать, чего испугаться.

        От этого могли бы помочь системные изменения (правила, модерация, публичность). Точечная реакция в той системе, которая есть сейчас, неэффективна.

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

          Это все, конечно, хорошо. Системные изменения, ужесточение правил. Но нужно всегда думать в таком случае, не оттолкнут ли такие меры других участников, и в особенности новых участников. Вот, допустим, администрация КФ сделает сложные правила регистрации новых аккаунтов. Например, для регистрации нового аккаунта нужно будет зарегистрироваться под определенный айпишник и/или мак, сдать задачу(хотя бы div 2 A, чтобы сомнений не возникало что человек сюда программировать пришел а не рекламировать), добавить фотографию, копию паспорта и т.д. Отпугнет ли это желающих выиграть div 2 раунд? Некоторых — возможно, но некоторые просто пойдут к соседу на два-три часа в гости, соответственно оставив все данные соседа и написав от его лица раунд(примеры от анонимуса уже были). С другой стороны, при таких запретных мерах будет невероятно сложно привлечь новые лица на ресурс: школьники в основном вступают в мир программирования благодаря своим учителям, со школьных компьютеров, регистрируясь из своей школы и решая задачи из архива во время урока. Другая категория людей, которым такие правила усложнят вступление — люди, которые не хотят сами решать задачу, но, возможно, хотят проспонсировать и привлечь разработчиков в свою фирму. У них так же возникнут большие сложности(разумеется, решаемые — но тратить на это силы и время...). В итоге системные изменения всегда должны быть очень взвешенными, и любое такое системное изменение чрезвычайно опасно.

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

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

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

              Можно несколько первых раундов после регистрации результаты новичков не учитывать при изменении рейтинга, не определяя их место в общем зачёте. Для этого их можно выделять в отдельные комнаты для новичков. Доказав серьёзность своих намерений, после внезачётного участия в 1-3 раундах участник к допускается к основным соревнованиям, его результаты начинают влиять на итоги раунда, его рейтинг начинает изменяться в соответствии с его результатами.

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

.