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

Добрый день!

В воскресенье, 23-го сентября в 16:05 по московскому времени состоится Отборочный Раунд 1 олимпиады для школьников Технокубок 2019. Раунд будет длиться два часа, участникам будут предложены 7 задач. По его результатам лучшие участники (но не более 45% от общего числа участников раунда) будут приглашены на финальный этап в Москву. Для регистрации на раунд и участия перейдите по ссылке. Не забудьте заранее зарегистрироваться на раунд! Для опоздавших будет открыта дополнительная регистрация (с 16:15 до 18:05).

Зарегистрироваться на Отборочный Раунд 1 →
Соревнование открыто для всех в виде отдельных раундов для первого и второго дивизионов.
Для всех участников всех трех редакций этого соревнования будет пересчитан рейтинг.

Параллельно с Отборочным Раундом будут проведены открытые рейтинговые раунды для обоих дивизионов, в них могут принять участие все желающие.

Напомним, что согласно правилам раундов Codeforces во время соревнования ваши решения будут тестироваться только на претестах (предварительном и неполном наборе тестов), а системное тестирование состоится после окончания раунда. Обратите внимание, что претесты не покрывают все возможные случаи входных данных, поэтому тщательно тестируйте свои программы! После прохождения претестов у вас будет возможность заблокировать решение, тем самым получив привилегию искать ошибки и взламывать чужие решения, но отказавшись от возможности перепослать ваше решение при каких-либо обстоятельствах (например, даже если вы найдете ошибку или вас взломают). Со временем задачи падают в стоимости. После системного тестирования учитываются только полные решения. Подробнее про правила соревнований можно прочитать по ссылкам:

Регистрация на олимпиаду Технокубок еще открыта. Победителей и призеров олимпиады ждут значительные квоты при поступлении в престижные технические вузы России и ценные призы! Если вы — школьник 8-11 классов и пока не зарегистрировались на Технокубок, то самое время сделать это:

Зарегистрироваться на олимпиаду →
После регистрации на олимпиаду не забудьте зарегистрироваться на Отборочный Раунд!

В финал соревнования будут приглашены лучшие участники каждого из отборочных раундов (но не более 45% от общего числа участников раунда).

Авторы отборочного раунда — Roms, BledDest и adedalic. Дополнить раунд до полноценного div. 1 помог Anadi как автор задачи, спасибо ему и arsijo за помощь в координировании. Кроме того, хочу выразить благодарность тестерам, без помощи которых этот раунд не состоялся бы: winger, Um_nik, AlexFetisov, Denisson!

Для тех, кто впервые на Codeforces: в таблице ниже вы можете найти примеры решений на всех поддерживаемых языках:

Группа языков Языки программирования / компиляторы Примеры
C GNU C, GNU C11 10903473, 17029870
C++ GNU C++, GNU C++11, GNU C++14, GNU C++17, MS C++, etc. 23794425, 5456501
C# Mono C#, MS C# 3195513, 3794163
D D 5482410, 2060057
Go Go 7114082, 21366098
Haskell Haskell 455333, 1668418
Java Java 8 25491359, 23678167
JavaScript V8 35963909, 35681818
Kotlin Kotlin 25779271, 25204556
OCaml OCaml 6157159, 1281252
Pascal Delphi, FPC, Pascal.NET 1275798, 1259434
Perl Perl 2519448, 1277556
PHP PHP 413942, 35875300
Python Python 2, Python 3, PyPy2, PyPy3 35883730 (Py2), 36179112 (Py3)
Ruby Ruby 1837970, 1289551
Rust Rust 25180002, 35652442
Scala Scala 35847980, 2456025

Удачи!

Обратите внимание, в Отборочном Раунде Технокубка и в div. 2 будет по 7 задач, предварительные стоимости:
250 — 500 — 750 — 1500 — 2000 — 2500 — 3000.

В div. 1 будет 5 задач, предварительные стоимости: 500 — 1000 — 1500 — 2000 — 2500.

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

Технокубок 2019 - Отборочный Раунд 1

  1. 300iq
  2. sadovan
  3. voidmax
  4. karasek
  5. ----------

Codeforces Round 512 (Div. 1, основан на Отборочном раунде 1 Технокубка 2019)

  1. TLE
  2. webmaster
  3. sunset
  4. jcvb
  5. volamtruyenkyii

Codeforces Round 512 (Div. 2, основан на Отборочном раунде 1 Технокубка 2019)

  1. Chair_man_Xi
  2. icecuber
  3. yp155136
  4. xjd0623
  5. liyingyan7

Опубликован разбор.

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

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

Clashes with open cup. Please delay the contest.

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

Just before September CookOff On CodeChef — Two Consecutive Contests + Sunday

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

You didn't mention anything about the number of problems. Can you edit that please? Edited, thanks

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

Round 2^9 :D

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

There are gonna be statements in English for the Div.1 and Div.2 editions, right?

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

A bad time for Chinese students.

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

    Better than contests that started at 11:35p.m.

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

      But most high school students can't use computers between 10 and 10:30. So I think it is better to race earlier or later.

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

        But I don't think so. Codeforces is not only for high students.

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

          May I ask why high school students there can't use computers between 10 and 10:30? Just curious.

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

            Because most Chinese high school students will leave school at 10 pm, they need to go home to continue the competition.

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

    This world needs one more cp platform for Сhinese, Japanese, Vietnamese and Australians.
    btw MikeMirzayanov can earn a lot of money by trading his cf system and installing it with Full Construction for anyone who could pay him some amount of money, so that person could hold contests there and get donations.

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

Another good time for Chinese Oier to enjoy the contest!

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

    But ...... many of HE->OIers doesn't have a holiday in Middle Autumn Festival...

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

      Still not so bad..(at least much better than 11:35 for oiers..) (why don't you use self-studying in the evening?:D

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

May I ask how many problems are shared between divisions?

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

Aren't 250 points for the first problem too less ?

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

    Wait for question to pop up.

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

    The question will have 2500+ submissions within 6-7 minutes, then :P

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

      Personally speaking, I will prefer to solve this question at last.

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

        I'm pretty sure that the optimal strategy is to always solve problems in increasing order of the time it takes to solve that problem. For example, if it takes you 1 minute to solve A and 3 minutes to solve B, if you solve A first you'll get 249+492=741 points, but if you solve B first you'll get 246+494=740 points.

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

          I would love to follow this stratergy but after getting soln. It takes me 5 min to code and test (due to my slow typing speed.) So I prefer reading all questions before starting.

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

            I agree with reading all problems before starting because there are many times where I get stuck on a problem believing "the ones after are harder" while I could've solve problem D way faster than problem C (or some other combinations). I failed a contest for not reading all the problems at the start before :(

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

          Not exactly. I think it's more of decreasing order of . For example, if it takes you 2 minutes to solve A and 3 minutes to solve B. Solving A then B gives you 750 - 2 - 10 = 750 - 12 = 738 points while solving B then A gives you 750 - 5 - 6 = 750 - 11 = 739 points.

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

            Yeah, i calculated something wrong. I'll check with a bunch of random inputs if your theory is correct.

            EDIT: It works on 500 million random contests with 4 problems each and 43 million random contests with 6 problems each. I think you're right.(I made each problem worth 250*(random number between 0 and 3) more points than the one before it and made the time required to solve a problem a random number between 1 and (problem number)*10.)

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

              Good job showing that you're a good scientist. thumbs up

              I think you should also try to prove it with a contest of 2 problems. You'll have a better understanding of why that's the case.

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

This is going to be my first contest ever. Wish me luck, guys. :)

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

Thanks to Mike Mirzayanov for the platform...

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

    Don't be angry with downvotes, you don't want Mike to see that. Codeforces community tryin to help you by hiding this comment

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

По его результатам лучшие участники (но не более 45% от общего числа участников раунда) будут приглашены на финальный этап в Москву.

Но на сайте олимпиады написано следующее:

Финальный этап Олимпиады пройдет 3 марта в МГТУ им. Н.Э.Баумана, МФТИ, а также на других региональных площадках по всей России, о которых будет сообщено позднее.

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

    Как я понимаю пока только ведутся переговоры с возможными другими площадками. Москва будет точно, другие города — посмотрим.

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

Wish you all get failed system... Ok, that's a joke. Wish you all get high rating!

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

А сам официальный раунд будет рейтинговым? Или рейтинговыми будут только div.1 и div.2 раунды?

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

What will be the duration of the contest, <= 3 hours right? Otherwise it clashes with September Mega-Cookoff on CodeChef.

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

round 1000000000

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

Логотип технокубка в статье ведет на codeforces.com/technocup2018 вместо 2019. Причем в анонсе ТК18 он тоже ведет на codeforces.com/technocup2018.

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

dont try to hack my solution .. warna kanpatti sek dunga.

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

upvote if u want to get upvotes.

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

who will give me the first upvote?

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

Geometry forces

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

today was a bad day , my mind completely shut off on B :( can anyone explain once the contest is over ?

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

    same here

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

    Mine did too when I first read it so I was like "you know what? Convex hull!" lol

    I got the convex hull out of the 4 points they gave us on the input and then, for each point, I tried to add it to the convex hull. If this point is in the new convex hull, that means this point isn't originally inside the polygon given (or it wouldn't be in the convex hull).

    I mean, I know there's probably a much easier solution, but that's what I came up with in a few minutes xD

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

      I was also inspired by the convex hull algorithm. I walked from anti-clockwise around the corners of the rectangle. Then for a given point I checked if the cross product of the vector from one corner to the next and the vector from one corner to the point was non-negative. If this is true for all corners the point is inside the rectangle.

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

    Div2 B Write equation of each line then divide rwctangle based on x coordinates and check if y lies below or above the line segments. Also do the case when n-d<d.

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

    Each line on the rectangle can be written as y = x + c or y = -x + c. Finding c for all 4 lines is trivial, as well as <= or >=. For every coordinate see if the inequality is true for all 4 equations.

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

    Look at the picture:

    These red lines are covering all of the points of the rectangle.
    Now focus on the topmost red line. What is common for all the points that lie on that line?

    All of the points on the top line can be descibed by this equality: y - x = 2.

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

      By the way, in general I know only about 4 equations which are useful in these types of problems:

      1. Horizontal line

      2. Vertical line:

      3. Diagonal line from top left to bottom right

      4. Diagonal line from bottom left to top right

      Diagonal lines are more difficult of course =)
      I need to constantly remind myself that I can add and subtract coordinates and get something meaningful out of it :)

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

    Since the coordinates are small , iterate through all the coordinates which lies on or inside the rectangle and mark them as 1. Now if the point lies outside the rectangle then the value of that point would be 0.

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

if i'am submit two time accepted to same problems, why i'am take point to the last submit?????

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

What is test 5 of B div 1 :(. Failed on it 3 times and can't find the mistake.

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

I was trying to solve E wth I smoked today

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

What is pretest 4 of Div. 1 D? T_T

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

Can anyone explain Div1-B? I thought that for (l,r) to be good sum(l,r) has to be even and >= max element of (l,r). I couldn't do anything with this fact though. How can I approach this kind of counting problems?

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

    My approach -
    Considering the count of 1 bits as elements in the array.
    Sufficient condition -
    good sum(l,r) has to be even and sum(l,r)/2 >= max element of (l,r). And log2(1e18)<63.
    Then iterate until sum(l,r)<=126.
    Rest of r with even sum is good. At max 126 iterations.
    Time Complexity — O(126*n).

    Upd — 128 is loose upperbound. 64 is enough.

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

      I don't understand why you have taken 63, isn't 60 good enough? I used 60 and got the wrong answer on pretest 8 for whole contest

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

        Only statement on this case.
        "Take a loose upper bound. But it should not be large enough so to give TLE."

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

    I will try to explain my approach, though I failed on test 5 for unknown reasons: - For a certain r, you will store all "records" from right to left, which are new maximum numbers. You can see there are at most 60 values of this. Then you can simply binary search in this range for the rightmost index x that sum(x, i) >= 2 * bits. Then prefix sum in this range is easy.

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

    As you said, you have to have:

    1. sum(l, r) is even
    2. sum(l, r) >= 2 * max(l, r)

    This is easy to prove, since your basic operation is decrementing one from two numbers in the interval (meaning that some of their bits cancel each other out).

    But we notice that max(l, r) <= 64, and the value of every element is at least one, so you can:

    1. Brute force intervals with length <= 64
    2. Count number of intervals that are longer than 64, with even sum

    code: 43313078

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

      You will have to brute force until 128.

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

        Well not really since max(l,r) is also counted in sum(l,r) so even if the other elements in the range are 1s your sum will exceed 2*max(l,r) after 65 elements or so.

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

          Got it.
          I took loose upper bound.
          I will pray that I don't get TLE and pretest cases are strong enough.

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

        You don't, since , so it's enough that the interval is longer than 64, since then .

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

    Thank you all very much!

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

      can you help understand this plz .. we are calculating for each number how many 1 in the binary representation right ? but why does it matter that the sum of 1 is even

      if we have 15 and 6 the sum of 1 is 6 which is even but xor isn't 0

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

        Cases where there are only two elements have one extra condition: Number of ones in al == Number of ones in ar

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

          doesnt that mean max element should equal or be less than half of sum of (1)

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

            I don't understand what you mean by that.

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

              if we have a number that has 8 ones in its binary representation and other 7 numbers that has only one one (lol one one) isnt that the same issue of the two numbers

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

                If I understand correctly what you are asking, this array will not be good, as the number with 8 ones can't have 0 ones even after xoring with all the other numbers. The condition that the numbers should be equal only applies where the subarray you're checking has 2 elements only.

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

what is the solution for Div2 D ?

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

Geometry forces. WTF?

A — too much troll problem. If a person couldnt solve problem A, what's he doing here? Why add such tasks in the competition?

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

I think this is my worst performance ever, fell ashamed about this stupid bugs I had :(

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

What is wrong with the following solution for div1D?

For each prime I can choose element of order p or order p - 1. Sort all primes and consider them from biggest to smallest if:

  • p is more than once than choose elements of order p and order p - 1

  • p is only once and our current answer is not divisible than p, than take element of order p

  • p is only once and our current answer is divisble by p than take element of order p - 1.

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

Is Div1D just making copies of p into p and p - 1 and taking LCM of everything, or is that wrong?

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

Codeforces? More like Mathforces.

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

Thanks codeforces for wasted an hour of mine for not specifying that "the segments should span the whole sequence" in Problem C

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

hi how does one do problem D from Div 2? i was thinking along the lines of the shoelace method but didnt really manage to get far with that idea.

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

    AFAIK let it's height be h, and base length be b, now 1/2*b*h = n*m/k , so if 2*n*m%k != 0, then print "NO"

    else note than you can always get one value of b less than n and one value of h less than m just by dividing gcd's and simple manipulatins

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

      Why b * h is an integer ?

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

        since area of the triangle in coordinate form is

        1/2*sum(x1*(y2-y3)) = 1/2*b*h

        and the left side (after removing 2's) is indeed an integer

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

        If you have a triangle with points A, B, C; its area can be computed using cross product as 0.5*abs(AB X AC), where AB and AC are vectors going from A to B and C respectively. Since the points have integer coordinates, then b*h in 0.5*(b*h) must be integer.

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

    You can construct the triangle using the points (0,0), (a,0) and (0,b) for some values of a and b. The first thing to check is when you simplify the fraction by diving by gcds if the denominator is greater than 2 there is no solution. You can see this because of the shoelace method you mentioned. The key to finding a and b is when you divide by gcds first divide n and k by gcd(n,k) then take this new value of k and divide m and k by gcd(m,k). Then if in the end if your k is 2 your new values of n and m will work for a and b. If the new k is 1 you have to multiply one of these results by 2.

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

How to solve div2E (div1B) ?

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

What is wrong with this solution for Div2 D 43333417

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

    we aren't not allowed to see other's submissions until system pending is done.

    But maybe you're missing the case when n*m isn't divisble by k, but 2*n*m is .

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

      Oops, didn't know about that.

      I checked for that case. My code got WA on pretest 10. Thanks for your response

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

Does anyone have any idea what pretest 8 for Div 2E is?

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

is cf predictor broken? I know I'm not that good in div1 but I feel like being in the 2/3 place should not be a rating drop for barely above 1900 (I noticed people around me also had rating drops despite being like 1910)

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

    I feel like recently it's broken. 1 contest it predicted me having +112 when in reality, it's a mere +55. The second time not as broken, still, +102 turns into a +124.

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

how to change the username which is shown to others?

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

WTF??!! 2 GEOM TASKS?? OMG F****G GEOMFORCES

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

I can't approach div1C by anything. Can somebody help me ?

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

    If you move boxes i ... i + k to positions x + i ... x + i + k, it costs:

    We want to choose the x that minimizes this. Note that the function is convex. We also have:

    Where comp(x, y) = 1 if x ≤ y, and  - 1 otherwise.

    Since the function is convex, therefore the difference is increasing, and cost(x + 1, i, k) - cost(x, i, k) only changes when x = (aj - j) for some j, we can just binary search the index j where when x = (aj - j), the change first turns positive. This is the minimum of cost(x, i, k). Then, we just need to calculate cost(aj - j, i, k).

    To do both, we store in a segment tree two values. For an interval [x, y] in the tree, we store:

    On the left side of j, the absolute value does nothing, and on its right side, it multiplies by  - 1. Therefore, we can easily calculate the cost.

    My solution is O(n log(n)^2), but a O(n log(n)) solution can be easily achieved by doing the binary search inside the segment tree.

    Code: 43339602

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

А где можно будет увидеть, кто прошел в финал?

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

    Обычно проходят 100-150 (в прошлом году было так), ты вряд ли пройдёшь с этого раунда

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

Thank you for the round, I really like the problems! Although I have no idea about Div.2 DEF, but thank you for the round!

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

Hi, This is regarding solution 43335491 for the problem 1058D - Vasya and Triangle , I have solved this question on my own ......I also matched my solution with 43330317 yes we have same variables declared due to which this misunderstanding took place and I m wrongly penalised....but as you can see there is a lot difference in my templates and him....which I always use. This is just a coincindence and I am Innocent. Kindly consider my submission. Thank you.

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

    Even with the different templates the main code is the same and that's definitive proof it's plagiarism

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

Submission 43333246

What those weird loops are for? Cheat detection evasion? The user did that regularly on their submissions.

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

My code is giving correct answer on local compiler but giving false answer on codeforces compiler. My whole contest went bad due to this error. Atleast my rating should be reverted back. 43309972

I checked test case 10 on codeblocks compiler as well as codechef IDE. Both of them are giving output as "Yes". My code is completely correct but still got WA.

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

    "Atleast my rating should be reverted back" "My code is completely correct"

    Stop with the trash attitude, you made a mistake, just own it.

    Here, i modified your code and it got accepted: https://mirror.codeforces.com/contest/1058/submission/43347029

    You had undefined behavior when accessing prefix_sum[pos] when pos = -1, so the output is never guaranteed to be the same.

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

      I didn't know there was undefined beahviour because as I said online compilers as well as codeblocks was giving me the correct answer, that's why I though my code was correct.

      If my code was wrong which you very correctly pointed out that it is, I wouldn't have written this comment. Thanks for your help.

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

I've solved div1 A

And I have a question, can anyone help me?

My solution of div1A used a valuable called "y1" , but I forgot to "define y1 _____y1".

And I passed the samples, pretests and main tests.

Why?

Here is a link of my solution :

![](http://mirror.codeforces.com/contest/1053/submission/43301181)

UPD: My question has already been solved.

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

I solved Div1C at 01:59:36, but Codeforces was down at that time... This is my first time to solve Div1C during a contest... QAQ

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

When there will be a list of those who have passed to the final?

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

Div.1 and Div.2 top 1 are both Chinese! They are sooo good at math (and coding)!

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

На финал идут топ 100?

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

    Узнать финалист ли ты можно в личном кабинете сайта ТК. Я 98й и попал в финал => те кто выше тоже.

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

      Просто в прошлом году писали прямым текстом, что в финал проходят участники с 1 по 100 место. Странно, что в этом году они не пишут.