allllekssssa's blog

DMOJ Contest
By allllekssssa, 9 years ago, In English

Today I have a lot of free time. I was looking for competitions today, and I found only one:

DMPG '15 — Gold Division (Open Unofficial Mirror)

Contest Time

Contest site https://dmoj.ca/

Contest isn't very popular ( last time was only 70 participants). If you also have free time, participate and compete against me (I hope for 100 competitiors). Contest has 6 problems and lasts 3 hours. Site also has some rating system...

For me this is new thing,I'd like to try new site and solve new problems.

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

Comments Comments (21)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

More information:

  • Contest is 3-hour virtual contest. Contest window runs in this timeframe. It starts 1 hour after the onsite version to reduce load on servers.
  • The contest window may be extended if there is still interest in people doing the contest near the end of the contest window.
  • I have added Bronze and Silver mirrors too; note that the difficulty of bronze is intended to be easy and the difficulty of Silver is intended to be medium. Personally, I only wrote problems for Gold, and I encourage you all to do Gold. However, you may still join all 3 contests if you want; they do not share problems. Do note that you may or may not be rated on all the contests you join, if there are enough people to compare you against.
→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    what is the difficulty of gold contest compared to div 1 codeforces contests?

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

      I hope most problems will turn out to be Div1 B, C, or D level, except for one or two easier problems.

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

    Thanks for information! Can you tell me about testing system ( full feedback or nor ? ) and whether the problems are sorted by difficulty ?

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

      The contest is full feedback. The score will be the maximum score of all submissions, but the tie-breaker for equal score is the most recent time you submit (so if you resubmit and get the same amount of points, you will gain more time penalty). Time penalty is sum of submission times of the counted submissions over all problems from beginning of registration.

      All the problems are worth an equal number of points, and partial marks are available in the form of subtasks.

      Problems in Bronze and Silver are sorted by difficulty. Problems in Gold are in random order.

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

        Can we choose which solution to be official, that is if we resubmit and get the same amount of points, can we choose our official solution to be the one made first in order to have less time penalty?

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it -11 Vote: I do not like it

          No, unfortunately the contest system does not support this. An imperfect solution is that you can post a comment to remove your later submissions from the contest, and we will try to accommodate you.

          → Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it -7 Vote: I do not like it

For me this was interesting contest. I was solving 3 problems on competition.First problem was easy ( but at begining I think that we couldn't do it in O( n3 ). Last two problems was a little harder and I couldn't think something smart. I'd love to hear solutions.

Also I have problem with Pascal, I do 5th and 6th problem , for some points , in good complexity but I get TLE ( for example subtask in 6th problem with M<=10 I do in complexity 10*(n+q) and get TLE ).

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    How did you solve 1st :P we had to find a cycle . ( that was easy ) but cycle should make a square (that i had no clue)

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it -8 Vote: I do not like it

      You can ask me after the end about solution.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 2   Vote: I like it -8 Vote: I do not like it

        The mirror is still open for the next six hours. It might be better to discuss solutions after everyone has finished competing (especially since FatalEagle mentioned that this contest might impact ratings).

        → Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it +11 Vote: I do not like it

Now that the onsite contest is over, I want to say a few words.

Firstly, I want to apologize to all the users that started at the very beginning and so were affected by strange test data in P2. I'm particularly sorry to Egor and zxqfl, because I answered their clarifications, and I answered them wrongly. Not just once, but twice! I wasted a lot of their time with that, so again, I'm sorry.

The updated test data for P2 also affected one onsite team which previously got 100, but it was unfair to decrease their score an hour after they received the AC verdict. Luckily, even if we chose the other way (rejudge without manually changing score), that team would still place first (due to time penalty).

Luckily, the bronze and silver contests, where the majority of onsite participants were, went much more smoothly.

I probably shouldn't try preparing (almost) entire problemsets two days before the contest without a tester anymore. In fact, I said the same thing several times before, but it always ends up happening again. So instead I hope I will improve at last-minute contest preparation. I hope everyone found the contest enjoyable, and short solution sketches for Gold will be posted on the site after the unofficial mirror ends.

UPD: Now that the online contest is also over, I want to add two more things. First, some of the time limits for Java were a bit tight, I only considered onsite competitors when making problems and most of them used C++. Also Java8 judge is slower than Java7 judges. Sorry to those affected. Also, my expected difficulties and predictions of problems were wildly incorrect. A few submissions that I looked at for P6 solved it by hacking the data (test cases were fairly weak).

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

    problem: DMPG '15 G3 — Kinako Bread 2 has complexity N * log^3 N with 2d fenwick tree? if not can you explain how to get results in log N ?

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

      I know an O(N * log^2 N) solution based on the centroid decomposition(it gets AC in practice mode, I didn't have enough time to implement it during the contest).

      The merge phase looks like this: let's take a look at two vertices from different subtrees. When do they form a valid pair? When Lk <= sk1 + sk2 + addK <= Rk and Lc <= sc1 + sc2 + addC <= Rc(sk is the numbers of K's on the path from a vertex to the root of its subtree. addK is 0 or 1(it depends on the content of the root). sc and addC are the same thing but for C's).

      If we fix one point, we can rewrite these inequalities as Lk - addK - sk1 <= x <= Rk - addK - sk1(constraints for C are handled similarly). It means that we just need to count the number of points in a rectangle. It is a standard problem with a well-known O(N * log N) solution which uses a sweep line and a binary index tree.

      How to deal with vertices from one subtree? We can just run the same algorithm for each subtree separately and subtract the result from the answer.

      Now we know how to merge all subtrees in O(N log N) time, so the total time complexity is O(N * log^2 N).

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

        Yes, this is the official solution. My implementation can be found here: http://ideone.com/L50nyo.

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

          Shouldn't line 96 take care of the RK == 0 and RC == 0 case?

          For the input 

          2 0 0 0 0
KK
1 2

          It seems to return 2 instead of 0.

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

I've tried to solve last problem by using Mo's Algorithm. Its complexity was . I thought I could get 60 points, but I got 40 points. Is there anyone who got 60 with Mo's algorithm? Also, what's the 100 points solution?

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

    Here is a very simple O(N * sqrt(N)) solution(which obviously gets a full score):

    1. If r - l + 1 < 3 * SQRT(N), we can simply iterate over the entire [l, r] subarray.

    2. If the query range is longer, we know that any flavor that occurs at least L / 3 times must occur at least SQRT(N) times in the entire array. But there are at most SQRT(N) such flavors! Thus, we can simply iterate over all "interesting" flavors(that it, those that occur at least SQRT(N) times) and check if any of them fits.

    → Reply