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

Автор MikeMirzayanov, 10 лет назад, По-русски

Добро пожаловать на 2014-2015 CT S02E07: Codeforces Trainings Season 2 Episode 7. Продолжительность тренировки — 5 часов. Тренировка открыта как для команд, так и для индивидуальных участников. После ее окончания вы можете дорешивать задачи тренировки или поучаствовать в ней виртуально, если не смогли принять участие одновременно со всеми. Пожалуйста, участвуйте в тренировке честно.

Так как это тренировка, то возможно набор задач будет расширен, если для значительного количества участников он окажется простым.

Условия задач будут на английском языке, ведь мы же готовимся к ACM-ICPC!

Удачи!

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

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

don't know why, but I am not able to submit. Every time I submit, I am redirected to the page again.

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

DELETED

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

Code-duplication meme XD

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

Will you publish an editorial after the training session is over?

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

My codes: A C E F H I J K

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

    I looked at ur code, ur code is amazing!

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

    In problem "Laundry" , what this statement actually meant :- clothes belonging to different persons may not be fastened with clothespins of the same color ??
    Does this mean that we cannot assign same color clothespins to different persons ??

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

      Yes, we cannot.

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

        Thanks.
        the problem statement was not clear :(

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

          clothes belonging to different persons may not be fastened with clothespins of the same color

          Sounds clear enough to me.

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

            I guess, "may not be" and "can not be" are two different things.

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

              Not really. The differences are very subtle, maybe I'd use "can not" as "it's impossible" and "may not" as "it's not allowed" — but it all amounts to the same thing here.

              But what else can it mean in a non-probabilistic problem statement? You either can use different colours for different people, or can't, and in the first case, that sentence makes no sense, so it's the second one.

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

    Xellos is too mainstream, if you know what I mean.

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

    Can you explain your E? I get that it's an sparse segment tree, but I don't get how the updates are done. my team thought it was just like this problem, so we went for an sqrt-decomposition approach, but it TLE'd (test case 4 ran for ~20min in my computer, lol).

    PS: for a team that has no other help around but the internet, you are one of the most helpful guys for our preparation to ICPC Regionals, so thanks a lot for your contribution here!

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

      It's not a sparse segment tree (the one where you don't have some subtrees in memory at all), but there are some similarities.

      In each node, you count the number of intervals that cover it fully; that number can be "normalized" so that if 2 sons of a node are both fully covered by two intervals, we can view it as the whole node being covered by one, and split one interval into its sons similarly (lazy propagation).

      You also need to know how many leaves in a subtree aren't covered by anything. If there's an interval covering the whole thing, it's 0; otherwise, it's the sum of its sons (or 1 for leaves).

      The rest is just drilling it into standard segment tree implementation.

      The whole contest has some crazy limits (O(N4 / 3)? ok, let's set N = 3000000). I'm not surprised that sqrt-decomposition fails.

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

        "The whole contest has some crazy limits (? ok, let's set N  =  3000000)." — fact that you didn't solve it in a better complexity doesn't mean that there is no better solution -_-... In fact J could be solved in complexity (and this simply pops out of Erathostenes sieve)

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

          Okay, I didn't see that one :D

          But the limits are still tighter than in most contests. In this case, my point is that it completely nukes sqrt-solutions of E.

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

        But wouldn't that result in O(N * log(N)) per query in worst case? For example, in a testcase where L = 1 and 500000 evenly spaced gophers/cd players, so that the segment tree's leafs would be like this: "01010101010...."

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

          Of course it's , what else could it be?

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

            per query? I was expecting an O(logN) per query w/ segtree+lazy update

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

              Shitty reading, my fault. Notice that I don't have a get() function in my segtree at all; how do I get the result, then?

              (Hint: read the 3rd paragraph of my explanation again.)

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

    Hello, I want to Know can the Problem e be solved by Segment Tree?

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

      If you actually read the comments above, you'd see that my solution is a segment tree.

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

"It is possible that the problems will be too easy for some participants, it is possible that we will add some problems." — lol. Indeed one team participating in that training did 11 problems (though ended 5 minutes before the end) and one ghost team also got all of them, but AMPPZs (at least those organized by UW, I don't know problems from others) contain really challenging and interesting problems :). I hope you enjoyed problems :).

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

    I actually solved some of them in an older, Slovak training. I even remembered how I solved some of them, although my solutions this time were often a lot simpler idea-wise...

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

Did anyone solved E using sqrt-decomposition? We've tried it, but got TLE on test case 4 ):

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

Is there anyone who solved G with the idea of using string matching on graph? All the solutions I have checked so far are based on hash.

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

    When I solved this problem a long time ago, I used it. It took me one night (it was quite long and I had trouble debugging it)...