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

Автор PikMike, история, 12 дней назад, По-русски,

Привет, Codeforces!

В такой замечательный день недели, как 03.08.2018 17:45 (Московское время) состоится Educational Codeforces Round 48.

Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.

Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

Вам будет предложено 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.

Задачи вместе со мной придумывали и готовили Иван BledDest Андросов, Роман Ajosteen Глазов, Адилбек adedalic Далабаев и Владимир Vovuh Петров.

Удачи в раунде! Успешных решений!

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

Место Участник Задач решено Штраф
1 eddy1021 7 299
2 djp_cqq 6 240
3 halyavin 6 248
4 BigBag 6 250
5 IcePrince_1968 6 286

Поздравляем лучших взломщиков:

Место Участник Число взломов
1 halyavin 80:-21
2 Doriath 45:-10
3 antguz 25:-1
4 applese 12
5 Ne0n25 11:-2
Было сделано 236 успешных и 417 неудачных взломов.

И, наконец, поздравляем людей, отправивших первое полное решение по задаче:

Задача Участник Штраф
A bazsi700 0:01
B bazsi700 0:05
C yjq_naiiive 0:17
D teja349 0:10
E yjq_naiiive 0:49
F eddy1021 0:41
G .................. 1:16

UPD: Разбор задач

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

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

Thanks to MikeMirzayanov for Codeforces and Polygon platform.

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

But is it rated?

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

Уже достаточно давно просят уменьшить фазу взломов. Есть причины. Почему никто не реагирует?(

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

What's up with these two comments? They seem to be visible for a split second when I reload this page.

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

    Comments with extremely low rating don't get deleted, they only get style="display:none" applied to them when the page loads

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

But ?detaR tI sI

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

hope not a mathforces or hackforces

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

Downvoted the blog already. Because the last 2 educational rounds were shitty.

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

Hey man you forgot to Thanks MikeMirzayanov for Codeforces and Polygon platform.

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

i will stop commenting ..

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

10 mins penalty or 20 mins?

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

Some upvotes please...

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

Please do not disable problemset submissions during contest.

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

Some downvotes please, I want to reach desired 69 contribution.

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

8000+ participation just wow gonna be challenging :)

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

why 10 minutes delay :(

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

I love CodeForces delays ^___^

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

what's the reason behind the delay ??

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

I HATE CODEFORCES DELAY

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

10 Min delay !! Welcome back codeforces <3

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

10 seconds --> F5 --> 10 minutes :)

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

Codeforces site already running slow, even before contest has started.

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

I think there is a problem, contest is delayed but Hightail was able to parse 2 question's TC. Using this anyone can get extra time in these scenarios.

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

+10 minutes in my wasting time sad :(

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

502 Bad Getaway-- CF wants to make you late for school.

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

I hope there woudln't be any lagginess during the contest since we're having ~9k participants

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

Educational rounds are useless !!

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

Well 9000 participants ! Love codeforces and this competitive programmers family.

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

"IS IT RATED?" in CodeForces is just the same as "Is ThIs Loss?" in reddit && other meme portals :)

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

9k! Congrats!

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

Как всегда, баланс между задачами просто ошеломителен.

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

    Ну что за "как всегда"? Для educational раундов это скорее исключение из правил.

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

is this a div1 contest!! :|

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

Че то сложно... Всегда знал, что я Div3

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

Any hints for C and D?

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

    D: You don't have to fill the entire table, just try to fill exactly one column and exactly one row, other cells are 0

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

      Why does this method work? Any intuition or proof? Thanks :)

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

        Suppose you constructed an answer with some number x in cell [i, j].

        Then you may:

        1) Set ans[i, j] = ans[i, j] xor x

        2) Set ans[i, 1] = ans[i, 1] xor x

        3) Set ans[1, j] = ans[1, j] xor x

        4) Set ans[1, 1] = ans[1, 1] xor x

        Then all xor-values of all rows and columns will remain the same, but we will get rid of some non-zero number.

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

        I think it's like this;

        Let a = (first column) xor (all rows from 2 to n)

        and b = (first row) xor (all columns from 2 to m)

        Both a and b represent cell(1,1) xor submatrix((2,2) to (n,m)), so they should be equal.

        If they are not equal then it's impossible to construct a matrix that satisfies the given constraints.

        And if they are equal, then we can fill all the submatrix((2,2) to (n,m)) with zeros and no contradiction will occur.

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

          Can you elaborate the last line — "And if they are equal, then we can fill all the submatrix((2,2) to (n,m)) with zeros and no contradiction will occur."

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

            You're right, I didn't know how to explain that part very well.Let me try again.

            At first I thought; what can stop us from filling all of that submatrix with zeros? the only "possible problem" will be at the cell (1,1) because of the two values a and b(from the above comment); they represent the same thing but have different expressions that depend on the two input arrays.So they must be equal(or else no matrix will be correct no matter the values you choose).

            Now that the submatrix is all zeros, and the value at cell (1,1) is fixed, can we have another "possible problem" or "contradiction" with the other cells ? (cells (1,2) to (1,m) and (2,1) to (n,1)).

            No, because the xor of any of these columns/rows(columns [2,m] and rows [2,n]) only depends of the first cell in that column/row and the zeros, so in other words no column/row will touch the first cell in any other column/row.

            So for any of these columns/rows nothing is stopping us from putting the value of it's first cell as the xor of all it's cells(since all the others are 0s, the result will be correct).

            Try to come up with counterexamples and you'll get it.

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

          what will be there in cell(1,1)?

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

            We chose to fill the submatrix from (2,2) to (n,m) with zeros, so a and b(from the above comment) will both be equal to the value in (1,1).

            Using the two input arrays;

            a = b1 ^ a2 ^ a3 ^ ... ^ an

            b = a1 ^ b2 ^ b3 ^ ... ^ bm

            You need to verify if they are both equal.

            If they are, fill that submatrix with zeros, fill the first row like this:

            matrix[1][i] = bi for i in [2,m] and matrix[i][1] = ai for i in [2,n].

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

          @glays I wanted to know can you give any proof/surety that by following above strategy there is no way such that if you use use some other strategy you can make a matrix while this method returns "NO" i.e answer doesn't exist using this strategy?

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

            I understand what you mean, try reading these comments:

            first

            second

            Cleaner and better proof from BledDest

            Also re-read the editorial.The first equality in it must be true, because both expressions represent the xor of all elements in the matrix, so they must be equal.If not, it's just impossible i.e. these constraints can not form a matrix.

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

    Well, first off I didn't AC problem C but I hope my approach was correctly. Basically, you can observe that since there are only 2 rows, and you need to visit every glade exactly once, you need to travel in a snake-like pattern from the start (going down, left, up, right, down, etc.). But you can also go all the way to the last glade of the row and 'loop' back to visit all the other unvisited glades in the other row. Please correct me if this approach doesn't work! Thanks.

    Edit: I suck and created an array too small. It passed afterwards.

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

      i thought exactly that but could not implement it...like : for going all the way to n... same cell can be multiplied with different number like 1 if we come straight from 0 or 3 if we zigzag like : 0->up->right->down....how do calculate for such different values

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

        Yeah that was tricky for me as well. Let's say you're at row 1 column 3 (1 indexed). You can get here and multiply by 2 (by going right from the start) or by 4 (if you zigzag down from the start). When you calculate going all the way to the last column of the row and return on the second row from this glade, you can notice that the difference between going right from glade (1, 1) and right from glade (1, 3) is the sum of all the numbers from ((1, 3) to (1, n) + (2, n) to (2, 3)) * (4 — 2). Hence, you can use prefix sums here to speed up the computation.

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

          ....

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

            You multiply by (4-2) because if you reach glade (1, 3) and multiply by 2 (and then go all the way to the last column and return), then you multiply the subsequent numbers by 3, 4, 5, etc.

            If you reach glade (1, 3) and multiply by 4 (going to the last column and return), then you multiply the subsequent numbers by 5, 6, 7, etc.

            Since you are multiplying the same set of numbers in the same order, by putting the multiples side-by-side you can notice the following:

            First situation: 3, 4, 5, 6...

            Second situation: 5, 6, 7, 8...

            Each number in the first situation is multiplied 2 less than each number in the second situation. Thus, the difference between the sums of the two situations is (sum of numbers from (1, 4) to last column and return) * 2, with 2 being the same thing as (4-2).

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

    Consider every point as "End" cell where vasya will end his journey and also the fact that each cell could be visited only once. You'll notice only possible end points are indices with (i+j) "ODD". (First move in a zig-zag manner to the adjacent cell at same column and traverse all the way round back to the End cell). P.S Zig-Zag manner means move to unvisited cell at same column and from there to adjacent cell at next column(Repeat). Please do ask if its not clear.

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

How to solve C?

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

    There is one pattern of going only: Zigzagging up to the ith column, then go all the way to column n and return. I don't want to get in details of how to calculate this, pretty long. But yeah you get the basic idea

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

    Suppose you're at cell (1,1), there are three possible ways.Either you;

    • go straight to (1,n) then down to (2,n) and back to (2,1).

    • go down to (2,1) then straight to (2,n) and up to (1,n) then back to (1,2).

    • zigzag your way to (2,1) then (2,2) then (1,2) then (1,3).Now that you're at (1,3), repeat.

    The first two can be precalculated using (painful and annoying) prefix and suffix sums.But it's not obvious at first.

    By the way, there are only n different routes.

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

In F, you always put edge at same place right?

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

What's 6 pretest for D?

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

чё за прекол С за 40 минут пишется а D за три минуты

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

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

I changed all long long into int, all long double into double, then I passed problem E instead of TLE. But I submitted it when the contest was already finished.

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

    And you still leave endls in your code. I changed endl to \n and it got AC in 750 ms instead of 1980

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

      I tried several times again. I got TLE on 8 with long long, long double and endl. 1980ms with int, double and \n. 1590ms with long long, long double and endl. 1434ms with int, double and \n. 311ms with printf.

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

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

      What about long long main() ?

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

        you can replace int main() with int32_t main();

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

          Or you can just write main(). By defaualt it assumes int. and No it's not undefined behaviour.

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

            It's also not something supported in the C++ standard. In might work in GCC (or at least the version of GCC that codeforces uses), but it won't work on other compilers (try visual studio and clang).

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

Show unofficial isn't working!

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

    Because it's Educational and after hacking phase you can choose division.

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

Problem D can be solved using flow. Bits are independent of each other, so treat one at time. Do matching to see where to put the 1's. XOR into some matrix and check at the end.

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

    Flow sounds a bit overkill

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

    How do you build the network?

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

      First consider simpler problem. Limit values to 0 and 1. If we want the values in a row to XOR to 1, there must be an odd number of 1s in that row; if we want it to XOR to 0, there must be an even number of 1's. It is the same for columns.

      The number of elements in a row depends on how many columns there are, and vice versa.

      There are some cases to consider. Let number of columns be c. If c is even, and we want some row to XOR to 1, there can be at most c - 1 1's in that row; if we want to XOR to 0 and c is even, we can put all c ones in that row. The other cases follow from this and are easy to work out. These values become the capacity of edges from source to row and and column to sink...

      For edges in between, place edge between each row and column. Saturating the edge is like putting a 1 in the cell that is the intersection of that row and column. Obviously we can only put a single 1 or 0 in a cell so those edges have unit capacity.

      Now we run max flow on this bipartite graph. Saturated edges represent cells with 1 in them.

      ...

      Now we take the same problem for general case of numbers, not just 0 and 1. Note that all bits in binary representation of number are independent, as I said before.

      So we take the simpler problem I described above and do it 30 times, for bits indexed 0 to 29, because the problem is bounded by a billion in the problem statement, the base-two log of a billion is just over 29.

      Do all the flows and put the resulting values in the matrix. To check if there even exists a matrix we simply validate the matrix produced by XORing its rows and columns and comparing to inputted XOR values.

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

        Thanks for explaining. Still confusing because there seems to be no explicit constraint on parity. For example, nothing prevents an edge of capacity 8 going to sink from saturating to 7.

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

          We want the maximal flow, so it’ll saturate fully if it can. That’s what we want.

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

    That's why you are still blue.

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

Why "wrong answer 154th numbers differ — expected: '-0.0000000', found: '-0.0000000', error = '-0.0000000'"?

Submission

»
11 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Пожалуйста, проверьте, все ли нормально с чекером к задаче E. На мои посылки какой-то странный

ответ (скопирован вердикт посылки 41190467) wrong answer 216th numbers differ — expected: '0.0000000', found: '-0.0000000', error = '0.0000000'

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

    Насколько сейчас известно — это баг в комментарии стандартного чекера rcmp6. То есть проверяет правильность он верно, а вот комментарий выдает с багами вывода действительных чисел. Аналогично страдал ncmp. В скором времени отображение комментариев поправят.

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

can you show me that why my code in Problem C got WA in test 7, please :(((((. I think my code WA in bignum but can't fix it :(((( http://codeforces.com/contest/1016/submission/41190766

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

I submitted a hack but the verdict is still not shown (spinner for the last 10 minutes). How much time does it usually take for hacks to show the verdict?

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

How to solve problem E?

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

    consider query point Q. find intersection of AQ and BQ with x-axis. The amount of x-axis covered in this range is proportional to shade time. To get actual shade time multiply by (y - sy) / y. I think my logic is correct although I couldn't debug my code.

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

Is It Rated?

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

Nineteen minutes lagging i hate my internet XD

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

I saw some solution use hashing with only 1 modulo and got hacked on problem B. I am considering which type of test did hackers use to hack?

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

Why there's no * after those orange or higher people ?

All participants are official ?

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

    Yup, it's been like that for a while now. Everyone is official, rated status doesn't depend on that.

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

Is It Rated or Contributed?

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

When will there be a tutorial? Anyway, I will try to solve more problem myself. :p

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

Congrats to djp_cqq, who received a 450+ rating change after his first round!

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

Congrats to djp_cqq, who managed to gain a 450+ rating change after his first contest!

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

Could anyone please help me with my E problem? No idea how to make it work faster, O(nlogn).

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

Need editorials!

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

Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).

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

I ak ioi!

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

Where are the solutions?

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

Is the judge for E broken? I do not think this submission should TLE...

I even tested the solutions of people on my friends list who got it AC, and they also get TLE...

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

    Can you please tell me which submissions have got AC, but now is catching TLE?

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

      adedalic See here for the AC one, and the copy-pasted one I submitted that TLEs.

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

        Seems that compilers differ, maybe C++11 one has slower iostream functions than C++17? Probably it's worth trying getting rid of cout for printf or submitting in C++17.

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

        More over, it seems that IO operation more than twice slower in C++11 in comparison to C++17

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

          I barely get my initial submission accepted in C++14 and it still TLEs in C++17.

          cin/cout with the special speedup should be on par with printf though...

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

            Lol the problem was taking in floating-point numbers instead of integers, if you take the input as integers it still passes C++11 (I know from stalking vamaddur's submissions)

            Apparently difference is so great, taking in floating point makes the whole program (which is nlogn) take more than 2x runtime.

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

No editorial?

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

Can somebody explain for problem D why the greedy always works/doesn't mess up the impossible case?

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

Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).

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

can someone explain C

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

I was really educated.

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

But is it contributed?

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

Hi!