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

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

Привет, Codeforces!

2 марта в 10:00 MSK состоится раунд #295 для участников из обоих дивизионов.

Раунд состоится практически одновременно с олимпиадой Зимней Компьютерной Школы на схожем комплекте задач. Авторы задач — я (Endagorion) и Евгений Савинов (savinov). В подготовке задач принимали участие члены технического комитета Зимней Компьютерной школы: Георгий Чебанов (gchebanov), Филипп Рухович (DPR-pavlin), Александр Машрабов (map), Сергей Киян (sokian), Константин Семенов (zemen), Кинан Альсармини (Sarkin).

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

Разбалловка в обоих дивизионах стандартная: 500-1000-1500-2000-2500.

Обратите внимание, что поскольку олимпиада ЗКШ на похожих задачах заканчивается позже раунда Codeforces, мы просим вас не обсуждать в комментариях задачи и решения до 14:10 MSK сегодняшнего дня. Также до этого времени будет закрыт просмотр кода других участников. Разбор также появится после этого времени.

UPD: все, можно обсуждать. =)

UPD2: наконец появился разбор ( теперь и на русском!).

Также поздравляем победителей в Div.1:

  1. Petr
  2. hos.lyric
  3. Syloviaely
  4. andrew.volchek
  5. xyz111

Отдельно поздравляем Petr и rng_58, решивших самую сложную задачу E!

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

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

Holy shit!!! There is eight Grandmaster and one International Grandmaster...

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

It's gonna be LEGEN wait for it DARY!!!

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

It's gonna be LEGEN wait for it DARY!!!

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

artofproblemsolving

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

I even had to write my homework at Roumanian, which was pretty hard to do for being able to compete, so I hope it is going to be a round with very nice problems :)

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

Div1 participants be like

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

I am scared!

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

Feeling unfortunate for not able to participate in such a "red hot" contest due to exams. :(

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

It's good that I have school just in the afternoon :D

(on the other hand, will I wake up so early?)

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

    Oh, come on, 5 hours till the contest, why sleeping at all?

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

      Because I'd be sleeping at lectures otherwise (again) and it's not very nice to lecturers to always sleep through everything :D

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

To sleep or not to sleep...

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

Such a beautiful day on most places in planet earth, would love to get some minus from the awesome people in codeforces.

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

wish you all best luck

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

Is it possible to unregister for the contest now ?

I registered earlier but just realized that I can't participate due to some reasons... I just don't want my rating to be screwed up because of such a mistake of mine...

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

    if you don't submit anything your rating will not be changed, also you can unregister by finding your name in the list and then clicking on the X sign

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

    If you don't submit anything , your ratings will not be screwed

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

The contest is very bad time in IRAN

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

where's the score ditribution ??

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

7 Problems and 10 Red problem setters...

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

I have missed my academic Classes and waiting for Codeforces Round 295.

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

I have missed my academic Classes and waiting for Codeforces Round 295.

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

Информация о разбалловке появится к началу раунда.

ок :)

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

No rooms???

Edit: Fixed

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

where is rooms?

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

А где посмотреть результаты ЗКШ этого тура? http://opentrains.mipt.ru/zksh/index.cgi?data=newstape&menu=index&head=index&class=zksh20151&sbname=zksh2015&rid=1 Тут нет

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

:'(

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

То самое чувство, когда делаешь неудачный взлом из-за #define int long long =(

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

nice modulo used, first time 1000000007, second 1000000009, third 1000000007

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

    Yeah.I got a wrong answer because that.It's stupid.At least, they could put it in statement description in this form, not 10^9 + 9...

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

      Yyyy, is 1000000009 clearer than 10^9 + 9 ; d? But I agree that those modulos were pretty stupid...

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

        You can copy-paste 1000000009, which removes some room for error.

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

          Yes, that's what I wanted to say.If you read 10^9 + 9 and type one more 0, your program will get WA and you'll never know why :))

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
          ModInt.h:
          template <uInt64 _Key = 1000000007ull>
          class ModInt 
          

          I always use my template like it, so I'll write code such as "ModInt<>", rather than "ModInt<1000000009>", because of stupid habit.

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

    Unpredictability.

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

    Now I know what was wrong with my code :(

    Single change of line gets acc :/

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

See more on Know Your Meme.

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

Тестирование-то начнется как обычно или тоже через 2 часа?

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

Were there any successful hacks during this round?!

Edit: Xellos beat me to it :)

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

I almost solved E in Div.2 I think I've got right answer for (1 <= n <= 15) But how can I get n Combination k when (n,k > 15)?

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

mogityantt testebi da amocanebii,meore amocanis 4 testis shemdgenels movutyann suyvelaperiiiiii ( :) <3 best wishes!!! )

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

Problems were fantastic, I LOVED this contest. It was more think-based than algo-based.

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

    shen chemi dzma gemeixede aqett O_o mogityann azrovnebaa ,ra iyoo kaii mitxarii ertiii haa?

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

how to solve problem C Div.2? Ô.Ô

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

Today was very nice time for Korean Users.

I always woke up in dawn to compete.

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

In case anyone missed it:

we ask you not to discuss the problems and solutions in the comments until 14:10 MSK

That's 2 hours from now.

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

Div2 D and E were HARD. (at least for me, unexpectedly harder than the usual D2 D and Es) :(

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

It was nice. thank you.

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

this round is hard :) but has got nice problems.

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

Отличный контест. Большое спасибо!)

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

Div2 C was easier than B :'( :'( :'( That's unfair...

UPD: Wait!! Don't downvote, I'm sorry. Div2 C was the hardest one among all.

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

Почему в претестах по B (div1) не было жирного теста?
Чтобы java7 упала на TL, я поменял бы её на java8 и получил бы AC.
Или может делать это в автоматическом режиме?

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

    Было 2 макстеста в претестах.

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

      Похоже, я просто неудачник, так как я единственный, кто упал с джавой с TL на финальных тестах =)

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

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

        long point(long x, long y) {
            return (x << 32) | (y);
        }
        

        Можно написать x * r + y, где r — случайное число от 3*10^9 до 4*10^9 и получить Accepted.

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

The system test was so fast because of the very small number of sources which passed the pretests :)) Problem A scared a half of the registered peopele in div1...even me, but I had woke up already so what did I have to lose?Excepting the rating, of course :))

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

    Hm, that possibility of not submitting code if one solved it too late is wrong and should be changed...

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

im sad :( i f**ked up :( any advice for me ?? :( (:-selfish) im really sad and there is no one that i cant talk to :( so i commented here :( my coding ability sucks :( i bugged a lot :( feeling so down but the problems were beautiful :)

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

During contest, I tried to hack B problem with N == M. Why it is not a valid input? Where does the problem statement say that M has to be different that N?

Update: Got it. I have to sleep more, lol!

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

Codeforces round 287 : Rank 192, rating change 1582 to 1699
Codeforces round 295 : Rank 95, rating change 1612 to 1699

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

Как решать задачу B?

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

    мы просим вас не обсуждать в комментариях задачи и решения до 14:10 MSK сегодняшнего дня

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

I spend very much time understanding the meaning of Problem B.QAQ

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

    I still don't understand the idea of that problem.Was stupidly easy.You had just to implement it without needing an idea or something.I say this even thouth I solved it...it wasn't interesting, and compared to the others it doesn't find its place in this contest.The rest of the problems seemed ok event thougth that A and C were counting problems and I didn't read D and E during the contest

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

    There were only 20 minutes left when I truly understood the meaning of Problem B.T^T

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

    Question like this (involving complicated, non-trivial process) should deserve explanation of the sample input at least.

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

Can anybody tell how to solve div-2 E ??

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

I still can't view other's codes yet...

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

How to solve Div1 C?

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

    Above formula works when k > 0. When k = 0, then simply output s

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

    Consider some digit d and all summands, where this digit is the i-th least significant. It will add 10id to the answer for every way to choose the +s that makes that digit the i-th least significant in some summand. That means there are no +s on the next i positions (between two digits) and there is one (or the end of the string, which gives 2 cases) on the i + 1-st position. There are no other restrictions, so we just need to put K - 1 +s on N - 2 - i positions or K on N - 1 - i positions; the number of ways to do that is given by binomial coefficients.

    Another optimisation lies in adding up the same thing for all digits d farther than i from the end of the string at once, by quickly counting how many such digits there are.

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

      I was thinking the explanation and then I found that your explanation is much clearer than mine.

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

What's the test 8 for the Div2-C?

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

    5
    ACGTC
    Answer: 1 ("CCCCC")

    Maximum possible value for a string is MAXIMUM_NUMBER_OF_ITERATIONS * n * n.
    For "ACGTC", MAXIMUM_NUMBER_OF_ITERATIONS is 2 for 'C'. So this value is 50.

    UPD: MAXIMUM_NUMBER_OF_ITERATIONS means maximum frequency.

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

Why I can't see others code and test cases?!

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

i need see the tests cases :(, i will not sleep until that happens :(

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

why are the solutions not visible yet !!! ?? I hope the other contest is over ??

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

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

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

    Если бы было написано

        return -Long.compare(v1 - v2, 0);
    

    То это бы гарантированно заходило. Основная идея: сравнение бывает , где a, c порядка 106, а b, d порядка 1011. Если забыть вычитание 1, то будет сравнение , в виде компаратора сравнение (a + b)c - (c + d)b c 0. Здесь прозрачно происходит переполнение на bc — примерно на 1022, но это происходит по модулю 264. Результат будет аналогичен сравнению ac - bd с 0.

    К сожалению кажется, что можно подобрать контртест в текущем написании, но он будет сильно зависит от выбранного алгоритма сортировки. Для Arrays.sort, Collection.sort, std::sort, и random_shuffle + sort возможно потребуются разные тесты. В исходной версии ограничения были не 106 а 109. Более того, нижняя граница на ai, bi была не 1, а 0. Так же при прочих равных было необходимо минимизировать количество апгрейдов. Тесты я составлял в таком формате, а затем по требованию упрощения для школьников стремительно переделывал их. Это могло вызвать некоторые проблем сверх вышеперечисленных.

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

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

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

Eagerly waiting for the editorial !!

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

How to solve Div2 C?

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

    Call f[c] the number of letter c in the string. Call maxF is the maximum value of all f[c]. Call count the num of letter c that f[c] = maxF. The answer to this problem is count^n. I found the answer by writing brute-force solution first, then try some input to observe the rule.

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

      What is the proof of your solution ?

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

        Let s be the string given in input and t a string which maximizes ρ(s, t). Take one character (let's call it c) from t. By shifting s and t in all possible ways, c is going to be at the same position as s[i] exactly n times (for i = 0, n — 1).

        So, the character c adds to ρ(s, t) the value n * count[c], where count[c] is the number of appearances of c in s.

        Then, ρ(s, t) = n * sum(count[c]), for every c in t. In order, to maximize this, you will have to choose c for which count[c] is maximum.

        Let num be the number of c's for which count[c] is maximum. The answer will be num ^ n, because, for every position in t, you have num characters to choose from.

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

    k => Amount of letters with bigger frequency in input

    n => Lenght of input

    sol = k^n % MOD

    My solution

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

    http://codeforces.com/submissions/dc26


    Observe a particular character. In following cases, I am calculating distance of only 'A'.

    ABBB, ACCC -> 4
    AABB,ACCC-> 8
    AAAB,AAAC-> 36
    AAAA, ABBB-> 16

    Hence you can see, formula is something like L*X1*Y1
    where
    L=length
    X1=frequency in 1st string,
    Y1=frequency in last string.

    So Distance reduces to summation of N*X*Y for each of 4 characters, "A, C, G, T"
    Now N and X are constant.
    We have to decide Y to maximize the product.
    Now Suppose my String was AAAC. Now what string should I choose to maximize the product.

    Frequency of A is 3, C is 1. So A will be the major contributor, I will get maximum when my other string is AAAA

    Now if my string is of type AACC, both A & C are contributors. So I can make a string of C's and A's
    I know the length i.e. 4 in this case. Now for every position , I can select either 'A' or 'C'.
    So m answer here is 2^4.


    Similiarly.
    "AACCTT"
    I can chose, 'A' 'C' or 'T' for every position.
    So answer is 3^6.

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

http://codeforces.com/contest/521/submission/10108767

I thought this would TLE, since it first calculates the power and then the remainder (does it?). Could anyone give some insight into this? I'm not sure how Ruby calculates that, but I would imagine it uses big integers.

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

Is there a way to solve Div1-B without using multiset?

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

    You can use priority queues. I'm not sure this is the answer you are looking for :)

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

      Div-1 B why is evryone converting m to n ... how is that easier than converting n to m

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

        You mean storing a point (x,y) as (y,x)? Because people needed to sort the points by y and then by x. Reversing them means that you can use the default pair comparator.

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

    You also can sort all of the cubes and use two iterators for the current upper cube and the corresponding cube it lays on.

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

Can you tell me how to solve div.2 C?

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

Результаты контеста, собственно, в ЗКШ где то можно посмотреть?

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

This is really a nice round. It proves that it was a good idea to challenge a Codeforces Round during class break.:) The problems are really nice,and this is my first time of Rating going up:)

BTW,the contest ID of 520 in Chinese has a quite romantic meaning.

Best wishes to all of you:)

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

Is there any editorial for problem Div.1-D?

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

    The editorials for all problems are coming. I'm sorry for the delay.

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

    Short description: div 1d was greedy. if we use assign op for any skill, then it's optimal to use as first op, so change highest assign op for every skill i to "sum b-a[i]" and discard the rest.

    Now every mult op multiplies answer by b, sum op multiplies answer by (a[i]+b)/a[i]. Greedily take highest multiplication factor until you can't pick any more operations. Print operations used for a skill in the order "type 1, type 2, type 3".

    Note that when you use a sum operation in a skill, factors for the other sum operations on the same skill change (mult doesn't affect anything because it's only done in the end). The way I solved this was keeping only the highest sum op for every skill in the priority queue and updating factors when needed.

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

How to solve Div2-E / Div1-C?
I could find just a dp solution which takes N * K.
Any helps would be appreciated...

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

Why doesn't my solution of Div1 B work? Isn't the answer a modification of Kahn's algorithm? And what's pretest 4 about?

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

    The solution is not a "greedy" topological sort of the graph. You can also remove nodes that have non-zero in-degree but after their removal, the connected component they are part of must remain connected. So you should greedily remove nodes that don't affect "connectedness".

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

    first person can take 0, 1, 2, 6, 9 he will choose 9

    second person can take 0, 1, 2 he will choose 0

    first person can take 1, 2, 4 he will choose 4

    second person can take 1, 2 he will choose 1

    first person can take 2, 6 he will choose 6

    second person can take 2, 3 he will choose 2

    first person can take 3, 7 he will choose 7

    second person can take 3, 8 he will choose 3

    first person can take 5, 8 he will choose 8

    second person take the remaining 5

    so the result will be 9041627385 % 1000000009 = 41627304

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

Can someone please explain the logic of Problem C(DIV 2) ?

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

520B - Two Buttons I know that turning m into n is easier than the opposite, but why is this code wrong? Can you give me any simple counterexample?

while(n != m){
        if(n > m)
            n--;
        else{
            if(m % 2 == 0){
                m /= 2;
            }
            else{
                if((n-1)*2 >= m)
                    n--;
                else
                    n *= 2;
            }
        }
        sol++;
    }
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Try n=3, m=7.

    That code goes 3 -> 6 -> 5 -> 4 -> 8 -> 7, when in fact it is better to go 3 -> 2 -> 4 -> 8 -> 7.

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

Heh, after reading that savinov is also a problemsetter, having #285 in my mind (when I have written two full of hate comments and they turned out to be my two most upvoted comments ever :P) I was scared that some noninteresting problems will be included. And after publishing editorial it turned out that he set one problem — guess which — of course the most shitty one ( ͡° ͜ʖ ͡°) (I hope that it's clear it is B).

B was just straightforward simulation. Could anyone point me something interesting in that problem :P? Moreover it was not nice to code (not that awful since that is still an easy problem, but ratio awfulness of code / needed thinking is still very high). Not to mention that when coding it I got sick of it and switched to C (which turned out to be a good decision, since it was easy) and then read D and couldn't resist solving that very interesting problem (kudos to Endagorion!), even though I was aware that EV of my rating will be higher if I will return to B.

What is more, it got terrible and very confusing statement. In the very title we are told that this problem is about cubes, I have always thought that cubes are something living in 3D space, it turned out that I was mistaken. Then "Let's consider a coordinate system such that the OX is the ground, and the OY is directed upwards." — ok, so OZ is that only one remaining. Then "The figure turned out to be stable. This means that for any cube that is not on the ground, there is at least one cube under it such that those two cubes touch by a side or a corner." — ok, so if directly under one cube there is another one and it touches it by whole face then it is not stable and if area of tangency region is 0 then it is stable? Great idea! Then some confusing part about clarifying that statement which I unfortunately omitted looking for some helpful infos in latter part of statement. And after reading the whole statement I realized "ok, so those 'cubes' are 2-dimensional, good to know" ( ͡° ͜ʖ ͡°) (and of course I needed to reread the statement completely).

I have always thought that Codeforces rounds is not a place for some "ACM Out Of Nowhere Regional"-style problems which statements can be compressed to "You got some stupid rules — simulate it".

I am aware that this is pretty offensive and sorry about it, but I just couldn't help writing that. I think that simply savinov's rounds will be the only ones I will omit purposefully. Maybe it's too big amount of hate for posting just one noninteresting problem (of course I have seen much uglier problems), but facts that it was given together with Endagorion's problems and its terrible statement empowers that impression significantly.

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

    I thought Problem B and D are very similar, so I don't understand your claim.

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

      Did you participate parallely in Div2 contest? Then Div2D and Div1B are undoubtedly similar :).

      In what sense they are very similar? Their contents were surely very different and for me "problems X and Y are similar" means "statements of X and Y were similar/they followed one idea/similar techniques were used" and all of those options are clearly absurd.

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

        It's true that problem B is an implementation problem, but it was interesting and I failed 3 pretests as I didn't think cases that if one box is removed, then some 'free to be deleted' boxes are no more free. If pretests were a little weaker, then the problem could a decent reservoir for hacks.

        In my view problem D was quite similar, in the sense of solving technique, as the greedy condition for each item was more evident for me than problem B. I resubmitted only because I didn't keep 'assign -> add -> mult' order. With 'long long' requirement, there were several traps, and I can understand acceptance rate was very low, but this is not because this problem was superbly interesting.

        In the both problems the main idea was 'use priority queue to decrease time complexity from O(n) to O(log n)' and the data structure to do this was very similar. So while I could be misleading about saying the problem statements were similar, not that much about the solving techniques.

        Anyway, I enjoyed all A-D problems, and didn't have any clue about problem E. (I'm very weak to graph problems, so...)

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

          You know, you also keep a priority queue in Dijkstra, but I won't call it similar algo to those ones. In B one has to come up with an ingenious observation "We want to maximize number (with fixed length). Let's maximize greedily the most significant digit!" and update available values (which for sure doesn't have anything in common with D), while in D you can just take a prefix of upgrades sorted in some funny order without any modifications during choosing them consecutively, so I still no longer see any common things other than greediness.

          Moreover I guess that you have at the moment 2572 rating not for no reason and D might have been clear for you, while I think it was in fact very tricky, while B was straightforward and just demanded some carefulness when coding it (D also).

          The most tricky part in D was in my opinion observing that we can choose to buy upgrades in other order than we have to perform them. But things get even more complicated, because if we will perform adding and multiplying only then for each upgrade we know how many times it will increase result, but things get complicated when we are dealing with assingments, because for addings the ratio after performing it and before changes if we will perform an assignment or not, but next observation is that this is in fact not an obstacle since we can simply treat greatest assignment as an ordinary adding (and forget about others). I consider that reasoning very nice, suitable for D problem.

          By the way I didn't notice that we can choose to buy upgrades in other order than we have to perform them and computed best way assuming that we use exactly k upgrades on that skill for all reasonable values of k. I noticed that if we won't perform all multiplyings (other than those with b=1) then we can perform at most 1 adding and iterated on that number and whether we perform assignments (I used logarithms to compare profits since they were too big). Then I observed that 2 * prof[i][j] >  = prof[i][j - 1] + prof[i][j + 1], what allows us to do everything greedily. I think that those observations are also pretty nice, but unfortunately I didn't make it work since my code turned out to be pretty tedious and vulnerable to many small mistakes.

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

    It should have been mentioned that Vasya and Petya are cosmonauts working on this experiment in zero-gravity conditions.

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

    Ok man, at least you didn't walk up to the computer screen at 2 AM in the morning, and see that all problems but E are math.

    Man you have no idea how I felt after that -__-, and you're complaining about 1 problem.

    There needs to be more diversity in CF rounds, you can't just make 4/5 problems math, or dp, or whatever. It's just not interesting when you do that.

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

      Lol, you will have hard time in competitive programming if you call such problems "math" ; d

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

        You can't argue with tags man.

        Shop math, sortings Pluses everywhere combinatorics, dp, math, number theory DNA Alignment math, strings

        Now if we do a simple string search on "math" we can see it in all three of these problems.

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

          In that sense absolutely everything here is math, go ahead and whine everytime when you see a "+" or "product" in a statement since that immediately indicates that this is a math problem --> shit problem.

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

          You can't argue with tags man.

          And what if I tell you that everyone who solved a problem can edit tags? :) So you can solve/copy-paste solutions for whole div1 problemset and then easily make it 5/5 math (according to tags).

          In some sense all programming is math.

          And problems which you mentioned aren't math in bad sense of this word. I am glad that there are not a lot such problems at CF at all.

          P.S. Have you ever tried Project Euler? Or Ad Infinitum contests at HackerRank?

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

    You know, when I was solving this problemset — I was actually happy that problem B was 2D instead of 3D)

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

      Of course I was happy also, but fact that I learnt that after few minutes is not nice :P.

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

    Well. I feel like I should reply something.

    Regarding problem B, I don't feel like this problem stands out from the problemset in a bad way. It probably didn't feature wonderful insights, but I like this problem too; if I would have created this problem, I wouldn't hesitate to include it in some of my rounds.

    The statement might not be in the best shape, I must agree. However, this is quite certainly not savinov's fault. The point is that the problems were prepared collectively, with me being the lead of the process. We decided to change the problem B in the last moment due to unforeseen circumstances (basically, it turned out that the former problem B was featured in some contest earlier), and savinov kindly provided his problem. It might have had some issues, but then again, every problem has issues until it is triple-checked by different people. So, plainly, it's my fault that the problem didn't get the attention it deserved.

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

I can't understand the solution of DIV 2 C. I spent a lot of time thinking of it and I can't understand why we care only for characters which occur most frequently. Having string s = "GAAAGGCCCCCCGGG" we count occurences of each letter : A -> 3 G -> 6 C -> 6 so the answer will be 2^15, becase 15 is the length of word and G i C appear the most frequently

so for example we count strings like GTTTGGCCCCCCGGG , because here also G i C appears 6 times , but p(s,t) = 1080 which isn't maximum. I believe that maximum is where t is for example GAAAGGCCCCCCGGG or GACAGGCCCACCGGG so A also has contribution to result.

Here is my code calculating these values http://ideone.com/ZedQOQ

I'd be grateful for help

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

    The strings you provided don't attain the maximum value. Have you tried computing the value p(s, "GGGGGGGGGGGGGGG")?

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

waiting for new contest !!... I want to became CM