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

Автор allllekssssa, 11 лет назад, По-английски

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.

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

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

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.
»
11 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится -7 Проголосовать: не нравится

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

»
11 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится +11 Проголосовать: не нравится

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

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

    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 ?

    • »
      »
      »
      11 лет назад, скрыть # ^ |
      ← Rev. 3  
      Проголосовать: нравится +16 Проголосовать: не нравится

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

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

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?