coder_1340's blog

FLOW and MATCHING at IOI
By coder_1340, 12 years ago, In English
Are there FLOW and MATCHING problems at IOI currently?
  • Vote: I like it
  • -9
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it
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 :)
→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    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.
    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      are the geometry problems excluded?
      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it
      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.
      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Wow, cool.
        Can you tell about it?
        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it
          On my way writing and remembering it. One moment, please... :)
          → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
          ← Rev. 4   Vote: I like it +21 Vote: I do not like it

          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
          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it +16 Vote: I do not like it
            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.
            → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        That's great! Can you tell it?
        → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it
can anyone give  link(s) for flood fill algorithm and its applications?
thanks in advance......
→ Reply