ghoshsai5000's blog

DMOPC '19 October Contest Announcement
By ghoshsai5000, 5 years ago, In English

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.

  • Vote: I like it
  • +41
  • Vote: I do not like it

»
5 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

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 !

→ Reply
»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

little_prince is linus123 on CodeForces.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 ?

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Look at the scoreboard.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

        → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 5   Vote: I like it +10 Vote: I do not like it

    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$$$ :)

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      That was useful, thanks! :)

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        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)

        → Reply