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

Автор tourist, история, 7 лет назад, По-английски

Hello!

Topcoder SRM 728 will be held tomorrow (January 25, 2018).

See what time it starts in your area.

I'm the writer. Everyone is welcome to participate!

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

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

Tourist these days be like

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

Reminder: The contest starts in less than 4 hours. Registeration has started.
If you are first to compete and don't know how to use applet, I suggest downloading applet from https://www.topcoder.com/community/competitive-programming/ and see https://www.youtube.com/watch?v=A5vnkkFGOo0 (of about first 20 minutes).

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

arena is not working properly:

screenshot

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

Arena not working for me. The same with web arena

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

Похоже Генке помимо рейтинга захотелось подрочить на вклад.

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

Is it possible to solve d1-500 with factorial polynomials?

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

    I think you are not missing anything, and this problem is indeed very similar to today's Div1 Medium. Unfortunately, I haven't been checking APIO problems since I graduated from high school :(

    Sorry about that.

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

      Well, individuals can make mistakes, but I don't understand that you didn't had any testers pointing out that.

      But whatever, it seems nobody remembered that APIO problem (and I'm really surprised about this. Why guys?????) I'm pretty sad to miss a trivial 497 points.

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

How to solve Hard? I've seen that the twirl operation actually just allows you to consider basically isomorphism only for even permutations. And it's obvious how to count the number of isomorphism classes if it weren't for this parity stuff. But it just seems impossible to tackle...I'm really curious to see the solution

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

    The usual way to find the number of equivalence classes under a group of actions — Burnside's lemma.

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

      Shit...I need to learn that. I've kept procrastinating it. Do you have any good tutorial?

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

Here is a short summary of solutions. Have fun!

Halving (div1 250)
IncreasingSequences (div1 500)
Trisomorphism (div1 1000)
HalvingEasy (div2 250)
IncreasingSequencesEasy (div2 500)
TrisomorphismEasy (div2 1000)
  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +46 Проголосовать: не нравится

    It's also possible to do the Div1 1K in polynomial time (code in the practice room):

    Spoiler
  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +45 Проголосовать: не нравится

    It's also possible to the div1 med by reducing it to this problem: http://codeforces.net/problemset/problem/559/C.

    For instance, replace L[i],R[i] with L[i]-i, R[i]-i, respectively so we are looking for non-decreasing sequences. For each interval L[i], R[i], we can add the points (i, R[i]+1) and (i+1, L[i]-1). Then, we just need to find the number of paths from (0,0) to (n, R[n-1]) that go only go down/right and don't touch any of the given points. This is a bijection, since we can take the column where we go from row i -> row i+1 to be the i-th number in our sequence. This can be done in O(n^3) if you don't preprocess factorials, but I'm not sure if you can get to O(n^2) with some smarter pre-processing.

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

      If I understood you correctly, I think there is a bijection iff after doing your changes for L and R arrays, we need to make L non-decreaasing (each L[i] is the maximum of all L[j] for j<=i) and R non-decreasing (each R[i] is the minimum of all i such that j>=i) to make the bijection true, and also making those changes in that way won't change the answer.

      Imagine the case where all L[i] are very large except for the last one is very small, there will be a path that go down early at first row (after a few steps), and keep going down, and at row n turn right, and you will avoid all L points since all of them is large except the last one (will be also avoided as L[n-1]-1 is smaller than index current column) , you can also find similar case for R.

      But I believe if you made L non-decreaasing and R non-decreasing in the correct way the bijection will hold.

      Anyway, I really like your solution a lot ^_^

      Thank you :)

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

This question is not about SRM 728. In topcoder is it possible to see SRM announcement at least 1/2 day(s) before? I used to see about SRM in arena in the day of contest. Due to this I miss SRM frequently.

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

    Pro Tips:

    1. Check https://www.topcoder.com/community/events/ (topcoder public calendar)
    2. Like codeforces, topcoder also has a e-mail reminder system. But for doing this you have to go to https://www.topcoder.com/settings/email/, and I suggest turning on "General Newsletter" and "Data Science Newsletter" (because in topcoder "competitive-programming" is included in "data-science").

    Now you have a schedule on SRM 729 and SRM 730:
    SRM 729: February 10th, 12:00-13:35 (UTC -5), writer is Errichto
    SRM 730: February 20th, 07:00-08:35 (UTC -5)