Are there FLOW and MATCHING problems at IOI currently?
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 156 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
Название |
---|
By the other hand, big numbers arithmetic is excluded too, but one problem from IOI2011 cannot be solved without 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.
Can you tell about it?
The idea:
UPD (source code):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.
Encoder: http://codepad.org/Xer4MZ0q
Decoder: http://codepad.org/09R1OUHl
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.