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

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

Лиса Ciel возвращается!

Все приглашаются поучаствовать в Codeforces Round #290, который начинается в обычное время в ближайший понедельник.

Это мой четвёртый раунд на Codeforces, можете ознакомиться с моими предыдущими раундами: #190, #228, #270.

Последний Div1-раунд (#286) оказался очень непростым, поэтому мы решили уменьшить сложность раунда (например, Div1-E превратилась в Div1-D). Надеюсь, это позволит большому количеству людей насладиться всеми задачами раунда: в этот раз ни одна задача не требует продвинутых знаний наподобие линейной алгебры или преобразования Фурье.

Главным персонажем раунда будет Лиса Ciel и её жизнь: она учится программировать, играет, путешествует, принимает ужин, а также делает многое другое.

Как и на раунде #228, топ-20 участников, присутствующих на зимних сборах в Петрозаводске, будут награждены футболочками Codeforces. Футболку может получить любой участник сборов, член жюри, тренер, организатор или любой другой человек, так или иначе присутствующий на сборах.

Как обычно, спасибо Zlobober за ценные советы и помощь в подготовке моего раунда, и MikeMirzayanov за платформы Codeforces и Polygon.

Удачи!

Update1: Score Distribution is ... Div2: Standard (500 — 1000 — 1500 — 2000 — 2500), Div1: a bit unusual ... (500 — 1000 — 1500 — 22502250)

Update2: Editorial: http://codeforces.com/blog/entry/16173

Update3: Congratulation to our winners:

Div1:

  1. Petr

  2. Endagorion

  3. mmaxio

  4. jqdai0815

  5. tourist

They are all people who solved 5 tasks!

Div2:

  1. SkullSkin

  2. joshkirstein

  3. gabrielinelus

  4. UnknownNooby

  5. Andrey_WK

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

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

Nice! I love your contests! Always I think that a little easier problems are better.The best programmers will certainly be in their place,and other competitiors will get more fun.

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

i'm not in Petrozavodsk training camp, but i want t-shirts too :)

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

"advanced knowledge like linear space" :P

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

hmm, i always thought that Bredor was the author of Round #228. ;)

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

Doesn't using the current Div1-E as Div1-D make it harder, not easier? The D task will be hard as E task, and E task will be even harder!

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

    It means the previous D will be the current E.

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

      actually, minimario's translation was correct. It seems that the author has his wording wrong.

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

        Maybe you are right, I'm not good at grammar. Then how to express it properly?

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

        I parsed it as "the upcoming Div1-E was initially supposed to be Div1-D". But the points is this round is going to be easier than the last Div1 round, at least according to the author.

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

The contest is from China. The time is 19:00 in Russia it means 00:30 in China! an it will last for two hours that is 2:30 AM! Will you be awake that time? :D
Anyway, Thank you for the contest... It's my 100th contest and I'm really scared because my rating change in your last contests was : -54 , -74 , -127 :D



UPDATE : This time my rating change was -106 :|
cgy4ever...

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

Didn't provide much help to Fox Ciel in last round . Will try to impress Fox Ciel atleast this time

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

Thank you for making this contest :)

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

YES

A CGY4EVER ROUND

!!!

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

finally a Div 1 + Div 2 round after 4 continuous Div 2 only rounds :)

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

Congratulations on advancing to the onsites of Facebook Hackercup cgy4ever.

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

    Thanks!!

    Now I've advanced to nearly all big onsite finals at least once: GCJ(2011), TCO(2013,2014), Yandex(2014, but can't participate due to visa issue), FHC(2015) and ICPC(2015).

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

~~~~~~~~

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

Посмотрел предыдущие раунды, я в них не участвовал, но тем не менее имя лисы Ciel кажется знакомым..

UPD: Ошибка, оказывается я участвовал в 270 раунде, но при открытии ссылки на него из анонса — открылась страница, на которой меня разлогинило, поэтому и не нашел себя в участниках раунда.

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

    Да на топкодере миллионы задач с Ciel

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

      Я слишком плохо знаю английский, а с гугл переводчиком я участвую только в официальных соревнованиях facebook и google.

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

I've registered but I might not be able to participate. Will my rating be affected if I never even open the contest page? (like on TopCoder).

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

    Your rating is not affected if you don't make any submission. (You can open the problems and decide to leave if you don't want to submit without any rating change.)

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

I wish good rating for all

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

I Love my rating :

1616 :))

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

hoping to taste div1 after the competition

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

Its good that its two division contest, otherwise merging it results in some weird rating change like #270 and GoodBye 2014 because too many top coders registered for this round.

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

My first contest, wish me luck.

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

Get ready to rumble!

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

Good luck

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

Wow, over 6000 registrants in total. Can CodeForces handle it?

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

Why I can't hack other code?

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

    Make sure you locked your solution for that task first.

    And make sure you are in the same room with that person.

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

      He's only submitted problem A. And I really can't think of a bug someone would have in coding such a problem. :) I think he asked why nobody has made mistake in implementing A. :D

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

That feeling when you hacked tourist :))

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

Oh! TAT! In my room,only I locked the code!And I was waiting a coder locked his code then I will hack him! But when I found a coder has locked his code,he used java and I can't hack him.I am so sad! Maybe I should average up and I can go to the div1....

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

    You can hack any solution, not only those that are locked. (Of course, hacking an unlocked solution means the owner can still get to fix it.)

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

what was the hacking case in div-1 A

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

Как ломали DIV1 А? Подскажите.

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

So what's the solution for D?

It seems that we need to ignore nodes contained in a cycle, and do a DP on the resulting forest. I had a O(N4) DP for solving a single tree, but I'm afraid it would TL (especially with recursion). Then I thought that to count the number of eliminations of size k, we need to count the number of subtrees of size treesize - k, which results in a O(N3) DP, but that totally ignores the order of elimination. Is there a O(N3) solution after all?

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

    To solve a tree of size S I used this algorithm: for each node, find the number of ways to remove K nodes such that the node is not removed (if K < S) or is removed last (if K = S). Then an ending subtree of size N is counted N times (once by each of its member nodes), so we adjust for overcounting by dividing by N.

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

    O(N4) with 3 seconds TL (and nothing else that could have the same complexity) and only in one small loop? Plus with O(N3) memory? I'm pretty sure it would work if you don't do something utterly stupid.

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

      For some reason I still have the impression (from sometimes before) that anything more than 108 is slow. Time to forget that and move on :)

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

        Depends on what it is. Processor instructions: no. Actually 4 times (common with DP) less simple C++ instructions: no. Insertions in a map of constant size: probably yes.

        It's better to risk it and find out in such a case.

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

    We should exclude not only cycles but some other vertices too, for example if cycle is conected to another cycle etc.

    We have rooted trees (connected to some bad vertex), and unrooted trees... and well I in both cases we can compute the answer using dp in N^3. Then we can join answers for trees using binomial coefficients in O(TN) where T is number of trees.

    But I didnt have enough time to debug my solution, so maybe it's wrong.

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

      What I meant was that we should exclude nodes that are part of some cycle. That includes your case :)

      Yeah, I think you were doing it the right way.

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

Как решать В?

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

    За минут 40 до конца я понял, что нужно выбрать набор чисел, у которых НОД равен 1. Развить это до адекватного решения не смог.

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

      Я понял это по третьему примеру за 5 минут. Пытался придумать умное целый час, забил, написал тупой перебор. Претесты прошло. Финалы зайдет или нет не знаю, но gcd быстро убывающая функция

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

        У меня тоже перебор претесты прошел, но перебор 300^8 (я сделал вывод о том, что больше 8 чисел нам никогда не надо будет выбирать, хотя на самом деле 9 или 10 еще может быть). И перебор этот я писал за 12 минут до конца, просто чтобы хотя бы хоть что-то сдать и вдруг повезёт.

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

          Я сразу понял, по одной очень известной теореме о НОД, что наименьше число, представимое в виде линейной комбинации чисел и есть НОД.

          Если ты можешь на каком-то наборе получить 1 в виде линейной комбинации, то из этого следует, что НОД этих чисел равен 1. А если можешь получить 1 — то можешь получить всё, что угодно.

          Потом понял, что задача на динамику, но так и не дошло, какая именно динамика-то :(

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

          "Последний Div1-раунд (#286) оказался очень непростым, поэтому мы решили уменьшить сложность раунда (например, Div1-E превратилась в Div1-D)." Я долго думал над этой фразой, и понял, что здесь что-то не так с логикой, если более сложная задача стала ближе к началу, то значит контест усложнился? Но почему же тогда пишут, что решено сложность уменьшить :(

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

            Ты еще не C не видел. Там поток. В начальной школе проходят.

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

      я сделал дп на мапе dp[N][достижимые_gcd] = минимальная_стоимость, но очень сомневаюсь, что такое пройдет.

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

        Пройдет. Возможных состояний — не более ND, где D = 29 — максимальное количество делителей числа. Переходов из каждого состояния О(N), по одному для каждого числа. Можно также было ускорить, храня только уникальные делители (D = 9)

        UPD: Оценка на D неверна, см. ниже

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

          Спасибо =) Можете доказать, почему состояний не более ND?

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

            Рассмотрим любое конкретное число. Все возможные достижимые из него состояния будут его НОД с некоторым подмножеством чисел. Любой такод НОД будет его делителем. Всего чисел N. Отсюда оценка ND. Правда, я неверно определил D:

            D не равно 29, D порядка O(X1 / 3), потому что такая типичная оценка на количество делителей числа (X ≤ 109).

            Если рассматривать только простые множители числа в первой степени, то можно гарантировать, что их не более 9 (2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23), а значит возможных комбинаций делителей не более 29

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

          Откуда такая оценка?

          Интуитивно понятно, что в целом достижимых состояний будет мало, но ведь у одного числа делителей может быть намного больше, чем 29.

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

    Я сдал так.

    Переберем последнюю взятую карточку. Заметим, что количество различных простых в l[i] <= 10. Для каждого из них нам надо выбрать карточку, которая не делится на него. Посчитаем динамику dp[k][mask] — минимальная стоимость, если мы взяли что-то из первых k и при этом "убили" простые, помеченные в mask. Переходы очевидные: или мы не берем очередную маску, или берем и убиваем соответствующие простые в маске. Итого n * n * 2^10 — примерно 9e7

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

мы решили уменьшить сложность раунда (например, Div1-E превратилась в Div1-D)

Но при этом усложнить Div1-A до Div1-B, а про Div1-B я вообще молчу...

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

great contest i'm waiting for your next contest thank you

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

Last minute, CF was down! I couldn't submit my A solution :( Actually I solved A but I was waiting for solving another problem too, after I submitted B and Got Pretest Passed, I wanted to submit A too. Which is now undone thanks to codeforces :D

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

    i wrote a submission for b, but haven't ten more secs to submit(

    my last round i submitted C 2 minutes before the end.) nevertheless, i need more time to get div1 membership :/

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

what was the solution for div1 b or div2 d? I tried pd with a knapsack, but the numbers were to big i think for that. Are there some tricks for big numbers? or is there another approach?

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

    A linear diophantine equation: a * x + b * y + ... = n has a solution if and only if GCD(a, b, ...) divides n. Since we want that to apply to all n, then the GCD should be equal to 1. The solution is DP with state (i, GCD) (last used card and current GCD of cards). We can use a map to store the states since the number of different possible GCDs is quite small.

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

      that was also my idea, but forgot the fact that the number of GCD is small. thanks!

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

      How to prove that the number of different GCDs is quite small?

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

        Because it should be the divisor of some number ai and ai ≤ 109. Numbers in that range can't have many divisors (less than 100 I believe). EDIT: Ooops, my guess was wrong, thanks for correction Andrei1998!

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

      "linear diophantine equation" is probably an overkill ;-)

      Basic number theory: Given x and y, their smallest positive integer linear combination spc(x, y) is given by sx + ty = spc(x, y) = gcd(x, y). You just need to find the minimal cost subset such that spc(a1, a2, ..., ak) = gcd(a1, a2, ..., ak) = 1.

      Note that gcd converges quickly as the subset size increases, assume that integers in the subset are distinct.

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

        Overkill or not, it's how that type of equations is called. Then again, anyone who has done a bit of number theory knows what a diophantine (I imagine the name doesn't sound horribly different in other languages) equation is, not to mention linear.

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

      "A linear diophantine equation: a * x + b * y + ... = n has a solution if and only if GCD(a, b, ...) divides n"

      Is there a proof for this?

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

    Yes, you are right, the gcds are too big to do dp with them, but the right thing to do there is to note that the number of useful gcds is small enough (my calculation ended up being ~60000 different gcd's), so you can map them to 1-60000 and then do dp.

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

      thanks! unfortunately, i'm not used to mapping and tried some tricks with big numbers, but they didn't work...

      i definitely have to learn how to map

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

Best message ever :v (And definitely, I didn't submit that -_- )

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

thanks for A. sweatest shit I ever eaten...

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

Div1 A

What's the answer for:

2
aa
aa

?

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

Это у всех сайт очень тупил? Первые 5 минут он не работал, когда начал работать уже поздавали А. И так весь контест 5 минут работает, 5 минут нет. И последние минуты тоже не работал.

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

    Да и вообще сайт нестабильно работает в последние дни, не только во время контеста. У меня такой режим "5 минут работает, 5 нет" почти постоянно.

    Upd. После консультации с MikeMirzayanov, диагностики и опроса других пользователей пришел к выводу, что проблема на стороне провайдера в отеле на сборах в ПЗ, а не на стороне сервера СF.

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

How to solve Division1 C? Task looks like a Euler path, but I don't know how to solve it.

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

    Although i have not participated in the contest but i think this problem can be solved using topological sort this way . Please correct me if i am wrong some where ..

    We can take each pair of string and find the first miss match then we put a directed edge from one character to the other (offcourse miss match pair is taken) then find whether there is a cycle or not in the graph . if there is a cycle then it is impossible otherwise find the topological sorting .

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

    No, a set of cycles.

    You can notice that any two neighbours need to have different parities, so you have a bipartite graph describing possible neighbourings; you want to match each vertex of each partition to exactly two other vertices.

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

      ai >= 2. Yep, only even lenght, I miss this restrict. Thx

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

      Is it correct to find one bipartite matching then remove the edges of this matching from the original graph and find a second matching? I wrote the solution and it passed the sys.tests, but I couldn't prove it's correct.

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

        It's not correct. Try test:
        6
        10 2 26 5 3 9
        or its permutations. System tests are weak.

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

          UPD: The following proof that we need two perfect matchings is correct, but finding two perfect matchings sequentially does not always work.

          "=>"

          Each breakdown of graph into cycles can be divided into 2 sets of edges, "left-to-right" and "right-to-left". Each node from left and right part has exactly one edge of each type incident to it. Therefore, each of such sets of edges forms a perfect matching.

          "<="

          For a pair of two edge-disjoint perfect matchings we get a set of edges such that each node has exactly two incident edges. Since the degree of each node is even, there exists an euler tour in each connected component. Each connected component has exactly K nodes and K edges, therefor the tour is also hamiltonian. Since each node has at least two edges, each component has > 3 nodes.

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

            A flow solution finds this order: 1 5 3 4 2 6

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

              Ah, I see. So the idea about two perfect matchings is correct, but finding them sequentially does not always work.

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

            The answer exists:

            9 10 3 26 5 2

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

For D1-A, what is the correct answer for this case?

26
a
b
c
...
z

According to this sentence:

But it was always true that after some modification of the order of letters in alphabet, the order of authors becomes lexicographical!

Should the answer be Impossible? Since you cannot do any modification to make them lexicographical...

I think this problem is ambiguous on this case. Could the author clarify?

Edit: well my solution outputs abc...z on this case. However, my friend's outputs Impossible, because he was struggling to resubmit his hacked solution on this multiple times without success, to the point that he thought the wording of this sentence was actually the tricky case.

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

Did somebody made mistake of writing "Impossible" as "impossible"? :P

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

How is Div1 B solved?

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

Thanks a lot for the nice C problem :) It is clear experienced coders must have seen it before but I was happy once I figured out the max flow solution. Then, I ran out of time because I didn't know how to restore the flow, and had to spend some time debugging >.<

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

Very nice problems cgy4ever, thank you :)!

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

Thanks for this round. Though my rating will decrease I learnt a lot . Hope you will be setting problems frequently .

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

Did anyone else wrote randomized algo for Div1 E? (・_・ヾ If my solution pass, I would probably look like (☉_☉')

Edit: It failed (˘_˘٥)

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

What a bloodbath on div1 A! I missed the opportunity of being hacked.

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

 BUTTHURT

Я специально обработал этот случай, бугуртил, читая в семпле "аккуратнее, не прозевайте ВОТ ЭТОТ САМЫЙ случай", и что я сделал?

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

My code (codeforces.com/contest/512/submission/9686628) got accepted but it writes "Impossible" with this simple input: 2 a a :))

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

Thank you for such a wonderful contest!!

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

Finally in top 5! Congratulations to winners and big thanks to those who created this nice contest for us.

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

Best contest since I am on codeforces :) Thank you :)

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

Codeforces was working perfectly during last 10 minutes. I've read so many codes, challenged so many people during that time! To help u guess how many, i say that factorial of this number is 1

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

Great contest with good problems,I just didn't know about 'topological sort' before the contest,and learn it during the contest ;)

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

Very nice problems. And finally I can become international grandmaster, really excited!

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

My short sad story:

I had A and B and it was like 15 minutes to the end. I didn't have any good idea for C/D/E so I wrote some simple greedy-random solution to E but I wasn't able to submit it during last 2 minutes. And now my code from contest passed all tests: link to solution

Ofc. AC with this solution would be a bit unfair but still I'm just sad... 155-th place vs. ~24-th place :(

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

Why is this Div 1 B solution failing the system test cases. Please Help. http://codeforces.com/contest/512/submission/9690331

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

Won't there be a rating change for this round?

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

My rating increased by ranking 266 ?!?!

Whoa, and here I was regretting not realizing C was a flow problem sooner and complaining about how terrible my performance was...

Though I wasn't fast enough to solve it during the contest, problem C was really nice. A very good contest overall!

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

Слабые тесты в задаче B первого дивизиона! Моя программа, получившая вердикт "Полное решение" даёт неправильный ответ на тесте: 9 9699690 111546435 74364290 44618574 31870410 20281170 17160990 13123110 11741730 1 1 1 1 1 1 1 1 1 числа l[i] сконструированы так : 2*3*5*7*11*13*17*19, 3*5*7*11*13*17*19*23, 2*5*7*11*13*17*19*23, 2*3*7*11*13*17*19*23, 2*3*5*11*13*17*19*23, 2*3*5*7*13*17*19*23, 2*3*5*7*11*17*19*23, 2*3*5*7*11*13*19*23, 2*3*5*7*11*13*17*23. Поэтому наименьший набор l[i], имеющий наибольший общий делитель равный 1 содержит все 9 чисел l[i]. Поэтому правильный ответ на данный тест 9. Однако моя программа, зачтённая на codeforces даёт ответ 8 (не та программа, которая прошла претесты во время соревнования, а которая была отслана после окончания соревнования).

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

    Что не так с моим комментарием?

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

      You wrote that comment in Russian, but posted it as English. Many people who use English version of CF see your comment and can't understand.

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

    Weak tests in problem B of Div.1! My program that got AC gives wrong answer on test: 9 9699690 111546435 74364290 44618574 31870410 20281170 17160990 13123110 11741730 1 1 1 1 1 1 1 1 1. Numbers l[i] are constructed so : 2*3*5*7*11*13*17*19, 3*5*7*11*13*17*19*23, 2*5*7*11*13*17*19*23, 2*3*7*11*13*17*19*23, 2*3*5*11*13*17*19*23, 2*3*5*7*13*17*19*23, 2*3*5*7*11*17*19*23, 2*3*5*7*11*13*19*23, 2*3*5*7*11*13*17*23. So the least set of l[i], that has gsd equal to 1 contains all 9 l[i]. So the correct answer to the test is 9. But my AC program answers 8. This is my comment.

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

Эх подстава в div1 B, одинаковые прыжки с разной ценой..

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

Nice problem set :)

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

DIV 1 C --> Awesomeness!! Thanks cgy4ever!! :D

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

How this contest can be rated since I did not connected to codeforces at least an hour ? Is that just happened to me or everyone ? I can not send my solution to B because of the network problems and now I got -80 :( I WANT MY RATING BACK !!!

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

    Just to you. Codeforces wasn't running so smooth, but rest of people were able to send their codes and get the verdicts.

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

Russian page has no links to editorial nor winners of Div1 / Div2. If anyone can fix it then do it please.

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

Take a look at this solution of div.2 D/div.1 B please. Where is bug? (WA on 24th test)

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

    Here. for (int i = 0; i < N; ++i) { cin >> c[i]; dp[l[i]] = c[i]; } Nobody guaruanteed that l[i] is not in map already. You will just lose too much information if l[i] overlaps with another one.

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

мы решили уменьшить сложность раунда

А вдруг это была реклама раунда, в следствии чего 6067 участников: div1 — 1728, div2 — 4339. Почти столько же, сколько участвовало в Goob Bye 2014.