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

Автор coder_1340, 13 лет назад, По-английски
Are there FLOW and MATCHING problems at IOI currently?
  • Проголосовать: нравится
  • -9
  • Проголосовать: не нравится

»
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
No. As I remember, there wasn't any flow/matching problem on all IOI since 2000. And I don't think there were something like that on earlier IOI, that would have been strange :)
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    As I know, different flow problems are excluded by syllabus. Even bipartite graphs are excluded.
    By the other hand, big numbers arithmetic is excluded too, but one problem from IOI2011 cannot be solved without it.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      are the geometry problems excluded?
      • »
        »
        »
        »
        13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Excluded: Real and complex numbers, general conics (parabolas,
        hyperbolas, ellipses), trigonometric functions

        You can read syllabus here. As I know, it's the most recent version.

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится
      I have a 100 points solution for parrots without big numbers arithmetic. It's not the best known, yes, but it still gives 100 points.
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Wow, cool.
        Can you tell about it?
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится +8 Проголосовать: не нравится
          On my way writing and remembering it. One moment, please... :)
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
          Rev. 4   Проголосовать: нравится +21 Проголосовать: не нравится

          The idea:

          We split the input in maximum of 16 groups (32 bits each). So, with every parrot you transfer a group number (4 bits) and some number (4 bits - from 0 to 15). Now, we can pass the numbers and distinct the initial value of group by different combinations of counts of numbers from 0 to 15. How to count it? If we pass X numbers, then the amount of combunations is C(15+X, 15).

          So, when the sum C(15,15) + C(16,15) + C(17,15) + ... is >= 2^32?

          Counting until 34, the result is 4059928950, but until 35 - 7307872110, which is just enough. So on every group maximum of 20 numbers should be passed.

          So, on every 4 bytes we need one group, so the ratio is: 20 * |` N / 4 `|. Which gets us ratio of 5. The problem is, if N is not divisible by 4 - we still need the same amount of groups, so the ratio gets slightly bigger than 5. However, if N is 63, not 64, the last group is not in range [0..2^32), but in range [0..2^24). If we assign our combinations cleverly, so that smaller number gets smaller amount of numbers to pass, the ratio of 5 is still present:
          C(15,15) + ... + C(30,15) > 2^24
          C(15,15) + ... + C(25,15) > 2^16
          C(15,15) + ... + C(20,15) > 2^8

          Now we need to get a bijection between combinations and actual numbers, but it can be done with DP, and the big number aritmetics is not needed here.

          I can provide a source code, which I coded after IOI (on IOI I coded similar idea, only 64 groups (8 bits each) - that approach gives 98 points with a ratio of 7), if I can find that source code on one of the flash drives.

          UPD (source code):
          Encoder: http://codepad.org/Xer4MZ0q
          Decoder: http://codepad.org/09R1OUHl
          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится +16 Проголосовать: не нравится
            Thank you very much.
            This solution has the same idea that mine (split into small groups and avoid big arithmetic).
            Marvelous. I thought that it's impossible to improve in ints/long longs.
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        That's great! Can you tell it?
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
can anyone give  link(s) for flood fill algorithm and its applications?
thanks in advance......