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

Автор ghoshsai5000, 4 года назад, По-английски

I recently stumbled upon the website DMOJ by accident and I could hardly find any posts about the website and so decided to make this thread to give it some publicity to the DMOPC'19 October Contest which will be conducted tomorrow.

As far as I can tell, the problem writers are thebes, KevinWan and linus123 (little_prince on DMOJ. Thanks to Kevin for informing me.)

Some facts about the contest

  • It is full feedback. There are no pretests or system tests.
  • There will be 6 questions plus an extra question for beginners
  • The duration of the contest is 3 hours and can be taken at any 3 hour slot over a period of 48 hours starting from 12th Oct 00:00 EDT

And yes, it is rated ;)

The contest will be conducted at

Let us discuss the questions here after the contest is over on 15th October.

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

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

Let us discuss the problems !

P0 — This was a straightforward implementation problem

P1 — For this, we only need to sort the array and calculate the medians of the two subarrays and the entire median seperately.

P2 — This was a standard Grid DP Problem. Let f(i, j) be the minimum cost to reach (i, j). We know that we can only reach (i, j) from (i + 1, j) or (i, j + 1). The transition is f(i, j) = G(i, j) + min (f(i - 1, j), f(i, j - 1)). We need to handle the corner case of the first row and first column carefully. The answer is f(n, m).

P3 — I was clueless for quite a while on how to do this problem. However, I realised after a point that the values of the array elements are quite small and are  ≤ 20 ! I made 20 segment trees, corresponding to each element.

While performing an update, if x is replaced with y at the %i% th position, then place a 0 in the i th position of the x segment tree and a 1 in the i position of the y segment tree.

To answer a query, we will start from 20 and iterate down to 1. If frequency (i) = k, we are done. Otherwise, simply update k - f(i) and decrement i

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

UPDATE 1 — Contest is now live. We can take the contest in any 3 hour window of our choice.

UPDATE 2 — There are one and half days left to take the contest

UPDATE 3 — The contest is now over !

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

little_prince is linus123 on CodeForces.

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

    Thanks for informing me !

    I'm eagerly waiting for the editorials tomorrow :)

    Do you mind saying a few words about the scope of DMOJ and the type of contests it holds and it's frequency ?

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

How difficult were the problems? :) Asking for future reference.

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

    Look at the scoreboard.

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

      The scoreboard shows relative difficulty of the tasks among themselves, not difficulty compared to Codeforces tasks, which I'm familiar with. Don't waste your time on useless answers ;)

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

        I suppose that you could compare how quickly a user solved the tasks on DMOJ vs a recent CF.

        Is there a better way? I can't really give a specific rating bound for the last two problems. Of course, they're probably CF Div 1 D-E level (but you could tell based on the number of solves ...)

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

    The first $$$2$$$ problems were just implementation. The third problem was a standard exercise.

    In my opinion, there was a big jump in difficulty to the fourth problem.

    Here is my rough estimation of difficulty with respect to CodeForces —

    $$$P_0 - [700, 1000]$$$ $$$P_1 - [1100, 1200]$$$ $$$P_2 - [1300, 1500]$$$ $$$P_3 - [1700, 1900]$$$

    However, I could only do $$$4$$$ problems so I cannot comment on the difficulty of the remaining $$$3$$$ problems. However, going by the number of people who solved them, I'd say they were all $$$\ge 2300$$$ :)

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

      That was useful, thanks! :)

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

        You're Welcome ! And now that I think about it, I think the other 3 problems were $$$\ge 2300$$$ :) (Based on the number of people who solved it)