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

Автор BledDest, 11 часов назад, По-русски

2051A - Подготовка к олимпиаде

Идея: BledDest

Разбор
Решение (Neon)

2051B - Путешествие

Идея: fcspartakm

Разбор
Решение (BledDest)

2051C - Подготовка к экзамену

Идея: BledDest

Разбор
Решение (BledDest)

2051D - Подсчет количества пар

Идея: fcspartakm

Разбор
Решение (BledDest)

2051E - Лучшая цена

Идея: BledDest

Разбор
Решение (Neon)

2051F - Джокер

Идея: BledDest

Разбор
Решение (Neon)

2051G - Змейки

Идея: BledDest

Разбор
Решение (adedalic)
Разбор задач Codeforces Round 995 (Div. 3)
  • Проголосовать: нравится
  • +18
  • Проголосовать: не нравится

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

If tutorials for some problems aren't loading, they should be up in about 3-4 minutes.

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

    The E problem is really well designed. Initially, my understanding of the scanline algorithm was focused on processing points within a two-dimensional range. Therefore, when analyzing the E problem, I enumerated all the values of $$$~a_i~$$$ and $$$~b_i~$$$ and treated them as prices, which we denote as val. At this point, the number of buyers among those who would not leave negative reviews is the count of $$$~a_i~$$$ that are greater than or equal to val. The number of buyers who would leave negative reviews is the count of $$$~b_i~$$$ that are greater than or equal to val, under the condition that $$$~a_i~$$$ for that $$$~b_i~$$$ is greater than val. Thus, I viewed this problem as counting points within a two-dimensional range, applying a scanline approach combined with offline processing using a Fenwick tree. However, the complexity of this approach prevented me from implementing it during the competition. After the contest, I was able to see a similar application of the scanline thinking, and the profound understanding of it truly opened my eyes. This also led me to reflect on the essence of the scanline preprocessing, which is to update all necessary states in a legal time complexity according to a certain order. It made me reconsider that in my code design, I should focus on specific implementation steps rather than just thinking about which algorithm to apply. This experience has been very educational and helpful for me! I really appreciate the design of the problems you created!

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

      I think E problem has some ambiguity because if the price advances bi ,that someone may dont buy it and also dont leave a negative review

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

        all right, i am wrong sorry

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

For problem D, I felt so pathetic, if I would have realised earlier that there is no distinction between index i and j. I have solved same kind of question earlier, I would have solved it in contest as well as:(

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

E, input:

3 1
2 9 5
12 14 9

Why the answer is not 18 (2 * 9)?

1st customer: 9 <= b (negative review), 2nd customer: 9 <= a (positive review).

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

ty for great contest!

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

In E, a third method to optimize would be using PBDS, 297960644

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

Hi is there anyone able to solve G with python? My TSP seems too slow (currently at 7000ms). Also, it there any reason for the strict contraints, making it just a library check as even some C++ solutions are TLEing?

UPD: Got it AC

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

E is simple binary search on answer right? Or am I missing something?

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

Why are O(nlogn) solutions getting hacked in E ?

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

why the testcases of the problems are opened?

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