Are there FLOW and MATCHING problems at IOI currently?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3382 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | heuristica | 3322 |
| 10 | maroonrk | 3312 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 144 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | adamant | 137 |
| 8 | BledDest | 133 |
| 9 | maroonrk | 132 |
| 10 | Proof_by_QED | 131 |
| Название |
|---|



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.