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

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

Привет Codeforces!

Приглашаем всех принять участие в Codeforces Round #266, который состоится 12 сентября в 19:30 MSK для участников Div2. Как обычно, участники из первого дивизиона могут принять участие вне конкурса.

Подготовкой задач занимались Antoniuk и я. Это наш второй раунд на CF, и все еще надеемся, что не последний.

Выражаем благодарность Gerald за помощь в подготовке раунда, Delinur за перевод условий на английский, а также MikeMirzayanov за Codeforces и Polygon.

Разбалловка задач будет стандартной: 500-1000-1500-2000-2500.

Желаем удачи и высокого рейтинга!

UPD. Раунд завершен. Спасибо всем за участие, надеюсь задачи вам понравились.

UPD2 Поздравляем пятерку победителей:

1) dominator_hza
2) Final_Battle
3) free_pascal
4) vanhanh.pham
5) NUOUN

UPD3. разбор задач

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

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

Все с нетерпением ждут что будет дальше.

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

    Если верить цветовой шкале, worse станет первым участником с белым ником

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

      Станет скрытным.

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

        Продолжайте в том же духе, worse

        P.S. Интересно, можно ли таким методом обогнать Гену по абсолютному значению рейтинга?)

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

          Ради него нужно вводить новые цвета и звания в нижней части шкалы)

          Да еще и багу нашли, должен быть белый цвет, а у него дальше серый.

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

          Думаю нет, в какой-то момент рейтинг будет падать на 1-2. Хотя вот если бы такик worst-ов было бы 500, то возможно:).

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

Блин порешать не смогу, жалко однако(везунчики удачи на кантесте):(

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

I really liked k-tree! Hope to see some more problems like that!

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

Решил посмотреть прошлый ваш контест, наткнулся на одну интересную задачу 431E - Химический эксперимент. Кто-то может мне объяснить её условие? Она точно на русском написана?

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

    В каждый момент времени у нас есть колбы с h1, h2, ..., hn литрами ртути. Воды в колбах никогда не будет.

    Первый запрос состоит в выполнении присваивания hp = x (то есть в p-той колбе теперь будет x литров ртути).

    Второй запрос состоит в следующем: нам дано v литров воды. Мы можем выбрать некоторое непустое подмножество колб и произвольным образом (мысленно, вода в колбах от эксперимента не появляется) разлить в них эти v литров ртути. Более формально: пусть = {m1, m2, ..., mk}, где . Тогда мы должны взять любие такие положительные числа d1, d2, ..., dk, что d1 + ... + dk = v.

    Мы можем выбирать множество и числа di как угодно. При этом мы хотим минимизировать значение величины .

    Искомый минимум (то есть минимум по всем возможным парам (множество
    , числа di)) надо вывести.

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

Brazil's ACM/ICPC First Phase will be held this Saturday, this contest came in a good time for a last preparation. Thank you.

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

мой последний раунд...

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

    Вам ещё самый большой подъём делать.

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

    Варианты того, что сегодня случится:

    1. Получив нулевой рейтинг, codeforces воспримет тебя как только что зарегистрированного участника (у них тоже нулевой рейтинг), и со следующего раунда тебе придётся по новой идти к нулю с 1500.

    2. Рейтинг станет отрицательным.

    3. Ты станешь топ1, так как случится переполнение (если для хранения рейтинга используется тип данных вроде usnigned int):

    unsigned int a = 13;

    a -= 40;

    cout << a << endl;

    Вывод: 4294967269.

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

      Codeforces на джаве написан, там нет unsigned

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

        Даже помечтать worse о топ1 не дал...

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

          Такое чувство, что даже если бы worse и стал первым, то он так бы и "висел" в ТОПе вечно

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

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

    а что если...

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

it won't be 500-1000-1500-2000-2500?

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

UPD: duplicate english comments

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

i really shocked when see only 4 comments :D usualy it's in order of 50-100

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

Wow! tourist just finished in 22 minutes!

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

Is there any problem in java compiler?

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

Is there any problem in java compiler? Runtime error for me even in custom invocation, working fine in my computer. UPD- BigInteger function nextProbablePrime() giving runtime error on codeforces.

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

.

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

hard math contest !!!

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

sometimes easy math is very hard , how to solve B?

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

    If you'll increase both numbers by more than 1e5, then product will increase by more than 1e10. But it is clear that you can get better answer, so you may check only all possibilities of increasing one of numbers by 0..1e5, and for every such possibility calculate required increasing of second number.

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

Задача С баян вроде. http://codeforces.net/problemset/problem/21/C

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

Правильна ли такая идея для Е:

Сохраним все запросы 3 типа в мап по документу

Далее пойдем по запросам сначала: если 1, объединяем героев в СНМ, если 2, то проходимся по мапу и смотрим был ли тот о ком спрашивают в одном множестве с тем кто подписал, сохраняем в ответ

?

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

    Вроде нет. Дерево 4->3. Документ приходит 3, 4й его не подписывал, но в одном мн-ве.

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

      ок, понял свою ошибку. Спасибо.

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

        А теперь у меня вопрос: Та же самая идея, но в СНМ добавить уровень вершины в построенном дереве, сливание 2х множеств производить руками и полностью переписывать в одном из поддеревьев уровни вершин. Для ответа на запрос, смотрим что обе вершины в одном дереве и проверяемая выше.

        Почему это не работает?

        UPD. Отбой, у нас могут быть вершины-не предки выше получившего пакет.

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

how to solve D??

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

    DP[i][j] — how many ways to solve first i points while having j open segments.

    You have following moves at position i:

    • close some of previous segments, don't open new (j+1 ways to choose segment to close)
    • close some of previous segments, open new (j ways to choose segment to close)
    • open segment and close it in same cell (1 way)
    • open segment and don't close anything here (1 way)
    • neither open nor close segment here (1 way)

    And for every possibility you should check that number of segments covering position i after such move is h-a[i];

    Answer will be in DP[n][0] (you solved all points, all segments were closed).

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

    A simple linear solution. Consider the sequence bi = h - ai. If some two bi, bi + 1 differ by more than one, the answer is 0, since some two blocks begin or end in the same position.

    Otherwise the answer is the product of values val(i, i + 1):

    1. if bi - 1 = bi + 1, then we must end one of the bi - 1 blocks. This can be chosen in bi - 1, so val(i, i + 1) = bi;
    2. if bi - 1 = bi, then we can end any of bi - 1 blocks that still continue at position i - 1, and start a new block at position i. Or we can continue all of the blocks. So val(i, i + 1) = bi + 1;
    3. if bi - 1 = bi - 1, we should begin a new block, so val(i, i + 1) = 1;
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      What does Val mean?

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

      What is the meaning of val(i,i+1) here?

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

        Imagine that ending a segment and starting a new segment is the same as putting a red border between two cells: see this picture:

        The white cells must be covered by the segments [l;r]. Thus if $$$b_i \neq b_{i+1}$$$, we must either end a segment (if $$$b_i > b_{i+1}$$$), or start a new segment (if $$$b_i < b_{i+1}$$$). If $$$b_i = b_{i+1}$$$, we can either end a segment and start a new one, or do nothing.

        $$$val_{(i,i+1)}$$$ is the number of ways to do that in each case. In the picture, $$$val_{(i,i+1)}$$$ corresponds to the number of ways you can put a red border between the $$$i$$$-th and the $$$(i+1)$$$-th columns. Note that you cannot put more than two red borders between the same two columns $$$i$$$, $$$i+1$$$.

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

В задаче E заходит : 7767621...

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

http://codeforces.net/contest/466/submission/7771298 — то есть такое нормально? где в условии написано, что нужно указывать стороны в ответе в таком же порядке, как и в условии?

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

    Выведите три целых числа s, a1 и b1 (a ≤ a1; b ≤ b1) RTFM)

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

      Я невнимателен, прошу прощения за вопрос. Весь контест думал, что неважен порядок

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

I think this time problem B was one of the hardest problem B's I have ever solved...

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

    Yeah, I was confused about how to solve (a + x)(b + y) ≥ 6n where x and y are the number by which a and b are incremented. I tried to solve this for most of the time and I couldn't concentrate on problem C because I couldn't solve B!

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

    A lot of us tried a greedy approach or maths, making it seem tough, but a brute force approach would have solved this.

    As pointed out by I_love_Tanya_Romanova and aaaaaaaaaaaaaaaaaaaaaaab in the comments, both numbers cannot exceed 1e5 (LeBron's idea) or sqrt(6*n) (AvadaKedavra's idea). You just check a or b for all possibilities from 0 to 1e5 or sqrt(6*n) and calculate the required increase of the second number.

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

    I think this time problem B was one of the hardest problem B's I have ever not solved...

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

I think this time problem B was one of the hardest problem B's I have ever solved...

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

Ironically, though there were few solves, the tests for B seem to be pretty weak — my submission 7762305 was accepted despite failing on many many tests (any of the lines in http://pastebin.com/rP0u5f4t would result in WA) due to having > rather than >=.

The actual problem was pretty nice itself though — proving that the solution will run in time is not too simple or obvious.

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

Seems like there was some miscalculation of the problems' complexities :D

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

Hard but nice problems!

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

Rank: 235 , best performance so far. :)

Biggest mistake that I made was locking all solutions when I did not have any intention of spending much time on hacking.

Solution B got hacked. Could not resubmit. :(

Probably will remain EXPERT for some time.

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

    Congrats, I too had my best performance so far today! Solved E for first time! :)

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

can anyone tell me why this solution gives WA while it works for that case on my pc http://codeforces.net/contest/466/submission/7772471

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

    Not sure if that's the cause but a thing I notice is you do not return 0 in the end of the function, so I suppose the returned value is undefined, therefore it may return true at some moment?

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

Finally worse did it.

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

Congrats to worse for becoming the first ever white coder on codeforces !

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

Even though ratings have been updated, colors have not. I am a specialist with rating 1553. :P

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

Ограничения по рейтингу для div2 1-1699, интересно сможет ли worse принимать участие в div2 теперь.

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

 What happened to my account rating ? http://screencast.com/t/pdEJQN5CZu

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

так-то dalex прав был про worse http://codeforces.net/blog/entry/13121#comment-179480

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

I solved nothing but A this contest.

I've actually solved E(for the first time in my life) but made a simple mistake. In one of the lines, I used the variable which I use to count the number of tasks received till now instead of the variable that holds the number of task that is in question... Passed pretests but got WA in system tests :( I suspected that I'd get TLE in system tests but when I corrected that line I got AC...

Anyways... Let's look at the bright side.. I've solved my first E even though it's not official.

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

This is first time I solved problem E! :D And became candidate master! :D :D

At first I got many WA 3 times on problem 1, I thought that for sure I will become Specialist again (got Expert only in previous contest).

After A passed pretests, I tried C and again got WA 2 times... tried E and got TLE. Finally I tried different method and E worked, then turned out I had to use long long int in C and that passed pretests as well.

Edit: I previously asked about other solutions to E, but I found a very simple one now.

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

I am unable to guess why my code gives WA plz can someone help me find the bug .Here's my submission http://codeforces.net/contest/466/submission/7774444

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

У меня видимо забавный баг. При рейтинге 1709 у меня зеленый цвет. Что мне с этим делать?

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

    Это все worse сломал, скоро админинстрация починит, наверное

    UPD: О, ты уже фиолетовый. Странно, я еще нет

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

So, apparently E had weak testdata. Or else, How did this solution pass? http://codeforces.net/contest/466/submission/7765318 I can break this solution with very easy testcase.

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

    there are many question like this with weak tests... anyway after this time if i cant solve a problem efficent i will send a naive solution :|

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

    Can you give one?

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

      I think an input of the following type would work:

      50001 100000
      1 2 1
      1 3 2
      1 4 3
      1 5 4
      ...
      1 50001 50000
      2 50001
      3 1 1
      2 50001
      3 1 2
      2 50001
      3 1 3
      ...
      2 50001
      3 1 25000
      

      Basically, the idea is that we have a chain of bosses 50,000 employees long, with 500001=>50000=>...=>1, so 1 is the boss of everyone. Then, we have 25,000 documents. Each document we give to employee 50,001 and we ask if it reached employee 1. It seems like you're doing a linear search for each document. So your running time will be on the order of 50,000*25,000 = 1.25 billion operations.

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

        Ah, you are correct. For some reason I assumed maximum height of tree as log(N + M).

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

I jumped to exactly 1700 in this contest. Now it appears that I am in some sort of bizarre limbo...

[UPD: Fixed now, as add1ctus said.]

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

    You are a candidate master, but it seems that worse broke the rating system by getting negative rating (thus not fitting into the 0 — 1199 gray rank, but in a new color — white). Hopefully once it gets fixed you will be promoted to candidate master.

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

It seems, there is a bug in standings table: purple participant is impossible for Div.2.

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

    There is a bug with the rating/rank system. He had 1472 rating before Round #266 and got promoted to purple after the competition. Check his profile.

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

What happened to phantom11's country-wise standings?

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

I couldnt understand the concept to B. Anyone?

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

    If a >= sqrt(6n) and b >= sqrt(6n), then a*b >= 6n; in this case, do nothing. Let a be the smaller of the two input numbers, and b be the larger of the two.

    One trivial solution is to increase b until the room is big enough. E.g. if a = 10, b = 11, 6n = 1001 (somehow): then the trivial solution is 10*101 = 1010. Then your "overflow" is at most a, which as we said was <= sqrt(6n). Let TRIVIAL be the value of this trivial solution, i.e. in this case, 1010.

    Therefore, the optimal solution has "overflow" at most a. Suppose that the optimal solution is x*y, with x <= y (WLOG). Then x <= sqrt(6n) + 1, because otherwise, x*y > (sqrt(6n)+1)*(sqrt(6n)+1) >= 6n + 2sqrt(6n) > 6n + a >= TRIVIAL, therefore the solution was non-optimal.

    What we have shown is: you are guaranteed that an optimal solution exists with at least the smaller number being less than sqrt(6n). It is possible that one of the two is larger, though, e.g. 1*6n = 6n. However, your goal is only to find the smaller number, through the following method.

    Fix w between 1 and sqrt(6n). For every w, let h be the smallest integer s.t. w*h >= 6n, i.e. h = ceil(6n/w). Keep track of the best value you've found so far. Then, you iterate through sqrt(6n) < 10^5 possible values of w, and for every such w, your computation is constant time, so your algorithm is linear in sqrt(6n).

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

Here is my code : http://codeforces.net/contest/466/submission/7796449 In my computer and ideone.com http://ideone.com/6lt8wR it runned test 1 and give me 4 but on codeforces it give me 0 ??? Who can explain me ??