### ghoshsai5000's blog

By ghoshsai5000, 11 months ago,

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.)

• 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

 » 11 months ago, # | ← 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
 » 11 months ago, # | ← 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 contestUPDATE 3 — The contest is now over !
 » 11 months ago, # |   +2 little_prince is linus123 on CodeForces.
•  » » 11 months ago, # ^ |   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 ?
 » 11 months ago, # |   0 How difficult were the problems? :) Asking for future reference.
•  » » 11 months ago, # ^ |   0 Look at the scoreboard.
•  » » » 11 months ago, # ^ |   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 ;)
•  » » » » 11 months ago, # ^ | ← 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 ...)
•  » » 11 months ago, # ^ | ← 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$ :)
•  » » » 11 months ago, # ^ |   +1 That was useful, thanks! :)
•  » » » » 11 months ago, # ^ |   +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)