Автор BledDest, 2 года назад, перевод, По-русски

Привет, Codeforces!

В 10.10.2021 12:05 (Московское время) состоится Educational Codeforces Round 115 (рейтинговый для Div. 2). Обратите внимание на необычное время старта раунда.

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

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

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

Задачи вместе со мной придумывали и готовили Александр fcspartakm Фролов, Михаил awoo Пикляев и Максим Neon Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.

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

Также от наших друзей и партнёров из Harbour.Space есть сообщение для вас:

Привет, Codeforces!

Мы поздравляем одного из наших преподавателей Николая KAN Калинина с его первым местом в финале чемпионата мира ICPC, который проходил в Москве, Россия. Годы тренировок Николая и его команды из Нижегородского государственного университета привели их к вершине турнирной таблицы, победе над командами из 116 других университетов и чемпионству.

Также поздравляем нашего будущего студента Егора 244mhq Дубовика, завоевавшего серебряную медаль в составе команды Белорусского государственного университета. Егор присоединится к нам в магистратуре "Computer Science" в ближайшие недели.

Мы с нетерпением ждем встречи с Николаем снова в январе следующего года, когда он будет вести свой курс Advanced Algorithms and Data Structures вместе с Майком Мирзаяновым. В этом курсе студенты сосредотачиваются на ключевых алгоритмах и структурах данных, которые составляют инструментарий современного специалиста.

Мы всегда рады видеть участников сообщества Codeforces в качестве наших студентов здесь, в Harbour.Space, поэтому мы снова предоставили специальную скидку (до 70%) на участие в одном курсе в Барселоне, Испания (расходы на проезд и проживание не включены).

Забронировать место →

Codeforces and Harbour.Space

Желаем удачи и до встречи в следующий раз!

Harbour.Space University

UPD: Разбор опубликован.

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

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

Note that the start time is unusual

is becoming quite usual now.

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

Great time for Chinese players!

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

Thank you for the contest. I hope that my rating will be increase after doing this contest

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

Why is it so early dudeee, some people have school

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

Too sad we are not seeing vovuh's handle in writers part of an educational round...

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

[deleted]

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

All the best guys!

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

Why the participation has reduced a little bit from previous 2-3 contests?

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

RIP sleep schedule. Gotta get up at 5am for this contest.

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

Hoping for a great contest OvO

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

The start time of this contest is very friendly to Chinese contestants! Hope I'll perform well in this contest.

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

In China, you can take a nap, wake up and start playing games

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

I hope I will be specialist after this round.

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

I enjoyed this round There is really very interesting problems

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

How to solve D?

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

    I tried to use inclusion-exclusion principle. The answer is (different a) + (different b) — (different a and b). I have figure out how to calculate "different a" and "different b", but didn't figure out how to calculate "different a and b".

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

      Lol, I did the same. Couldn't pass it during the contest. Later debugged and got accepted. Definitely it was an overkill..

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

    I calculated the total possible solutions which will be nC3 and then subtracted the number of bad combinations(observe that in a bad combination 2 problems will be having the same topic type and 2 problems will be having the same difficulty).

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

    Try to calculate the number of bad combinations and then it's trivial.

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

How to solve E?

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

    with dp. the main point is for each flip you just have to update O(n) dp values which makes it O(nq) that fits in time limit

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

      I was wondering the whole time why's $$$q \leq 10^{4}$$$ and not $$$10^{5}$$$, I knew that solution was somewhat related to it. Unfortunalely, I wasn't able to figure it out in time.

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

      Can you please explain further, my brain is fried up right now and I am unable to see the dp states..:P

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

        yes sure let dp[x][y] be the number of stair cases that start from point x,y also dp1[x][y] : number of stair cases from x,y that second move is right and dp2[x][y] : number of stair cases from x , y that second move is down .

        now we can easily update all these dp values (you can see my submission) sorry for bad english

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

          No no the english is quite clear, and thanks. I think I will see ur submission now.

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

        and also for each query update you just have to update these points : (x,y) (x-1,y) (x,y-1)

        (x-1,y-1) (x-2,y-1) (x-1,y-2)

        ...

        which is in total at most 3*min(n,m)

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

    There is a technique know in Brazil as Color Update, it consists in store in a set intervals that we assign a given color, each position can have at most one color. You can use this idea to color an interval, ask the maximal interval of the same color that contains a given point, etc. Using this idea just build maximal staircases, for each position store in which maximal staircases it is, and in which position. Then using Color Update technique the solution is straightforward.

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

How to solve D ? I found it much harder than E or am i missing something ?

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

    just find cases where the given condition fails and remove it from total cases

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

    Inclusion and Exclusion Principle, the total number we can get without any constrains is (N choose 3), then we subtract the invalid ones.

    the invalid ones must have 2 similar elements in both sides so we just count that.

    https://codeforces.com/contest/1598/submission/131438774

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

      could you elaborate how you calculated invalid ones

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

        Invalid ones should have at least two similar elements in both arrays let's say we picked the current element.

        A is the topic
        B is the difficulty
        so
        A should appear at least one more time.
        B also should appear at least one more time.

        so we count the number of other A's multiply by the number of other B's and keep subtracting this from the answer, and this will work nicely with the constrains we have as (A,B) can't repeat again together.
        sorry it's hard to explain, but you can go through my code for better understanding.

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

        Use Multiplication Principle.

        Preprocess each element's number of occurrences , and mark them as cnta[] and cntb[].Enumerate i from 1 to n , and the invalid ones are sigema((cnta[a[i]] — 1) * (cntb[b[i]] — 1)).Hope you can understand it.(My English isn't good).

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

          thanks man.

          understood.

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

            What's more.Because of "It is guaranteed that there are no two problems that have the same topic and difficulty at the same time".

            Invalid ones are a group with two identical "elements A" and two identical "elements B". So we just need to select the first pair first, and then select the other two pairs which have one "element A" and one "element B" which are the same as the first pair. The formula is just written in my last comment.

            I think this comment is more clear than the last one.By the way , wish you good luck. :)

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

              yup , just got the code accepted.

              this comment really summed it up for me ^_^

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

    Definitely missing something. $$$D$$$ was a nice exercise of complement counting. I solved it by adding edges $$$a[i], b[i]$$$ to empty bipartite graph with $$$2$$$ partite sets of size $$$n$$$ and then the problem becomes equivalent to counting the number of paths with $$$3$$$ edges in this graph.(at this point the problem is quite easy by storing frequency array of both $$$a$$$ and $$$b$$$) Of course this is only for better visualization. In reality you never actually do a graph algorithm to solve the problem. But I personally found this as a nice way to see the problem.

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

      Can you please elaborate your visualization?

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

        Uhh just add vertices in the graph and do simple case work for counting the complement. You will find every valid element in the complement corresponds to a path of length $$$3$$$ in the graph u made...

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

    You are not alone.

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

Can E be solved with link cut tree ?

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

Definitely moving up from Pupil today!! How was the contest for y`all guys?

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

solved D but tough Java constraints :( https://codeforces.com/contest/1598/submission/131447806

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

A round a day keeps my rating away.

It seems that I will get about -50 rating after this round. I hope I can remain an Expert.

By the way , Problem D is such an excellent problem although I didn't solve it in this round. It really gives me a lesson.

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

Talk about the shortcomings of this game (this does not mean that I do not support the author, I support every author of CF), the data range of the C question is very intriguing (why is there a data range that cannot be covered by int64?), I am useless Over int128, so I spent nearly 20 minutes on compilation errors. Of course, the other topics are very good, thank you very much to the authors!

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

    I guess you checked for $$$sum \cdot (n-2)=(sum-a_1-a_2)\cdot n$$$?

    Notice, that you can shorten this check to $$$2 \cdot sum = a_1 n + a_2 n$$$ for which both sides do fit in a long long.

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

    int64 works fine for C. You just need to reduce the equation with algebra.

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

How To solve D ?

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

    Let be ai = task, notice, that for a we can take (n * (n — 1) / 2) other tasks and lets just remove pairs of tasks that we can not use with a. This is the amount of the same difficulty * the amount of the same topic

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

    If we consider pairs as coordinates on 2D plane and since all points are distinct, only way three points selected at random dis-satisfy the given conditions is when they form the right angle triangle. Hence subtract number of right angle triangles from NC3.

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

what is the meaning of open hacking phase is running, can i get points if i solve problems or what it is ?

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

    You can hack other's submissions. Hacking doesn't earn or loss points in this contest. Feel free to hack if you find any bugs in other's code.

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

I misunderstood D and thought that both the given conditions should be satisfied. Later obtain the actual answer easily from the answer I calculated. Anyone did the same?

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

In C why (sum*(n-2))==(sum-a1-s2))*n is wrong?

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

    overflow.

    sum can be at max 2e5 * 1e9 == 2e14

    And then sum*n==2e14*2e5 == 4e19 which is more than the limit of the long data type

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

    I don't think this is wrong, maybe its an overflow issue

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

    bro power will reach to something 10^20 and long long has range 10^18

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

      Can't we find mean using this method ?

      double k = 0; //k is the mean
      int t = 1;
      for (double x : arr) {
          k += (x - k) / t;
          ++t;
      }
      • »
        »
        »
        »
        2 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        avoid doing such operations bro.

        it won't give you the correct ans.

        there are always chances of floating pint error,

        performing such operation is not advisable

»
2 года назад, # |
Rev. 5   Проголосовать: нравится -67 Проголосовать: не нравится
  • I love Russian Contests.
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +36 Проголосовать: не нравится

    The fact is that there are many Chinese top coders like Miracle03 and QAQAutoMaton are busy in teaching some new coders.So they don't have time to write more contests.The rounds you see are written by some students who love coding , and I think they're good enough for these younger coders.I think they need more encouragement but not prejudice.

    I do hope you could post comments with less discrimination and prejudice.And I think Chinese writers can get progress very soon.Best wish.

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

Too good questions (:)

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

Where is the solution of this contest ? I think I need it!

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

there is a solution for problem E

notice that each staircase's length at most 2000

and each point have 4 staircases at most

so U can use brute force to solve it

the complexity will be $$$O(Q(N+M))$$$

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

when will publish editorial?

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

Awesome round. Love problem F

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

solved E just several seconds after the round ends, what a pity! :(

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

Awesome round with much less extra hackings (comparing with other Edu rounds) ,excepting problem D.

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

Can anyone help me with the approach to solve B?

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

    There are only 5 days. We can enumerate all pairs of days and find if it is possible to seperate students into two groups. Let's say we choose day A and day B. If there are some students (possibly one) who can't attend day A and day B, then {A, B} isn't the answer. We count the students who can only attend at day A, students who can only attend at day B, and students who can attend at both day A and B.

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

Nice round. Totally enjoyed it!!

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

Please explain how to solve D. >_<

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

    Substract the illegal ways from all the ways.

    There are in total $$$\dbinom n 3$$$ ways to choose $$$3$$$ elements among $$$n$$$ of them. Now considering how many of them are illegal, that is, none of the two conditions in the statement is satisfied.

    To calculate it, we first define cnta[x] as how many times topic x has occured and cntb[x] as how many times difficulties y has occured.

    Then assume that we choose the $$$i$$$ th problem, since no two problems share the same $$$a_i$$$ and $$$b_i$$$, we can assume the second problem we choose shares the same $$$a$$$ with $$$a_i$$$ and the third problem shares the same $$$b$$$ with $$$b_i$$$. So we just need to calculate 1ll * (cnta[a[i]] - 1) * (cntb[b[i] - 1]).

    You can view my code 131440598 for more details.

    Sorry for my poor English(

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

      Can you provide a more rigorous proof?

      It seems that a lot of the solutions for D are getting hacked (mine included) and they all count the answer the same way you are describing. I don't know why though.

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

        They are hack just because they didn't use long long

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

        In your code, when it comes to nA += (ca[a[i]]-1) * (cb[b[i]]-1);, I suppose that it overflows the int limitation

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

      thank you

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

The penalty for each incorrect submission until the submission with a full solution is 10 minutes What is the meaning of this?

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

    Penalties are for the leader board. More time used means lower ranking.

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

      Oh okay. I am a little confused, will I get penalities for multiple wrong answer submissions for a problem even If i don't solve it?

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

Any hack tc for D ?

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

    I think the hacks exploit this.

    I believe you can have all numbers from $$$1$$$ to $$$100000$$$ and create the pairs $$$(1, 100000)\ (2, 100000)\ \dots\ (100000, 100000)\ (1, 1)\ (1, 2)\ \dots\ (1, 99999)$$$.

    In that way there are $$$2\cdot 10^5 - 1$$$ pairs (possible because $$$n\leq2\cdot 10^5$$$) but the product of counts will overflow if they are initialized as int. (for example considering the first pair the counts will both be $$$99999$$$)

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

      I used size_t( vector.size() ) in my code, but it still be hacked.Do you know why?

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

        You've been overflown. Thought your ans is 'long long', you are not yet familiar how expression is evaluated. It's in this line:

        ans += (cntb[d].size() - 1) * (x.se.size() - 1);

        Try to output: long long ans = 100'000 * 100'000;

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

          Thanks for your reply!
          Could give me one testcase? I test my code with input:
          n = 200000
          a = [1, ..., 1, 100001, 100002, ..., 200000]
          b = [1, 2, ..., 100000, 1, ..., 1 ]
          When x.fi = 1, d = 1, that line is:
          ans += (100000 — 1) * (100001 — 1). It seems that my code is correct on this testcase with the ouput of 1333303333500000.

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

Nice problems :)))

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

Nothing to say!XD

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

Why O(Q*(N+M) + N*M) is failing for problem E (TLE on testcase 41 (not included in pretests))?
My Code : https://codeforces.com/contest/1598/submission/131480763

Edit : Finally my code was accepted. Replaced vector with pair which brought a major change in execution time (approx 7 times faster). Always try not to use small vectors (if possible).
AC Code : https://codeforces.com/contest/1598/submission/131498204

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

    Assuming that you are doing a bfs for each query : giving the fact the number of situations is at most (nb of x * nb of y * nb dir = N*M*2), the total complexity of your algorithm is O(N*M*2*Q + N*M) = O(N*M*Q), which is too slow. Sorry for my bad English.

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

      No, the time complexity is fine actually because for changing a particular cell you just need to update max O(n+m) cells, not the whole dp table. I had run test case 41 on codeforces and it's taking 3.3 seconds to give the output. The runtime is slow. Can anyone please optimize this code?

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

    To make your code cleaner, you can use array<ll, 4> instead of those pairs, here is the AC code with that modification 131514905

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

I just came to know that Um_nik was in the 1st place.. I thought that he finished University and I was watching the closing ceremony and thought that this guy behind the mask has a familiar hairstyle and then after googling I got to know that he was our Um_nik. I tagged you because I wanted to congratulate you publicly but without a blog.. Congratulations and wow you are a hardcore person from specialist to red and then ICPC Champion... way to go man I couldn't be a great coder winning contests like you do till now but it's ok coz everyone's life is different.. but it feels good to see an inspiration of hardwork and straight forward man(this i am saying by your blogs and comments) like you at the top.

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

Can somebody give a testcase where this is going wrong

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

For problem C I used double still I think it is overflowing somewhere How can double overflow here.Please help My submission

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

When will the solution be available

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

Does anyone know why the unordered_map solutions to C are resulting in TLE? Is it because of some crafty input which is causing everything in the hash table to be put into single bucket?

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

    yeah its because of anti hash test case which is causing the unordered map to have a bad hashing

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

      That's really interesting. Do you know where I could read more on this or how I could generate such cases?

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

      my question is that is it valid to hack solution on the basis of short coming of unordered hash , should this be concern of the problem . I think its a useless ground to discard out solution specially in problem C

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

      What about hash map implementations in other languages (say Python dict)? Can they be hacked like this?

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

Can someone please let me know the problem with my Problem-C solution. It is giving TLE on Test-17. I have used a standard unordered_map based solution, with O(n) complexity as per my understanding.

Any help will be appreciated. Thank you !

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

    Unordered map does not work as efficient as hashing. Technique

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

    Notice that unordered_map is a hash table and the complexity is average O(n). I believe that is some input that is causing it to get the worst case complexity which is O(n^2)..

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

      So should I prefer ordered_map in future ?

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

        I don't know to be honest. I myself used unordered_map in the contest.. I think that if the log n operations are acceptable we should prefer map since.. Though I think someone more experienced would be able to answer better.

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

        you can still use an unordered map but with custom hashing ,you can copy paste the template from this blog,because in edu round people have enough time to make anti hash test cases.

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

          Thanks KingRayuga, will keep in mind.

          I think we can also go with ordered_map as it seems that the time limits are flexible enough to accommodate O(n*logn) solution even when best one is O(n). Please, correct me if I am wrong.

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

    Just read someone else's comment here and tried with ordered map. Solution Accepted !

    So what should I learn/conclude from here regarding the use of ordered/unordered_map. Like when to prefer ordered_map over unordered (because here I thought using unordered should work, but id didn't eventually).

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

The test cases used for successful hacks will be included in the main tests?

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

Probably not relevant to the blog but I have a solution which I think would work for non-distinct pairs for D. Would anyone like to test it out or perhaps reply with a solution of their own which also works for non-distinct pairs.

Here's my submission

https://codeforces.com/contest/1598/submission/131482336

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

same solution using unoreded_map is tle (after hack) but using map is accepted.

I used unordered_map in contest

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

When will the ratings change?

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

How to solve problem F? I have been thinking for a long time but still have no ideas. Can anyone tell me the idea of this problem? Thx.

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

Why ratings change taking so long?

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

Rating change is taking longer than I thought!!!

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

    I think it's because the unusual time of this round, but also, I have to say that the rating change of this round is the longest I have waited...

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

when does system testing starts?

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

MikeMirzayanov please remove the cheaters and update the ratings thanks !

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

    why the systetm testing is caried out multiple times. is this for rejudging with additional testcases.?

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

why system testing is done so many times ?

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

unordered_map's TLE is about hash, but how about multiset?

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

I will become pupil but why the delay in giving ratings.

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

I find 2 solutions are copied. But even why were they not skipped

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

Please upload editorial as soon as possible. Thank you for the contest.

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

-1

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

Hello everyone, I have written a blog on improving codeforces rating that I used to follow and it is a really good routine. Do read the blog here.

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

when will cheaters be remove. I found many cheaters but they were not removed

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

Can anyone tell me why my rating was decreased by 29 even when my verdict was OK on a single submission. No other submissions were done .Just one and that too with OK verdict

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

-1

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

Have the cheaters been removed? As there are many remaining..