Hello codeforces!
I need help with this problem: UVa_11754
If all Ki = 1, we can use Chinese Remainder Theorem directly, but the number of possible states is (Π Ki = 100^9)
I believe there is a brute_force solution but i couldn't find it ):
# | User | Rating |
---|---|---|
1 | tourist | 3690 |
2 | jiangly | 3647 |
3 | Benq | 3581 |
4 | orzdevinwang | 3570 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | Radewoosh | 3509 |
8 | ecnerwala | 3486 |
9 | jqdai0815 | 3474 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 164 |
3 | adamant | 163 |
4 | TheScrasse | 159 |
5 | nor | 157 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 152 |
8 | Petr | 146 |
8 | orz | 146 |
10 | pajenegod | 145 |
Hello codeforces!
I need help with this problem: UVa_11754
If all Ki = 1, we can use Chinese Remainder Theorem directly, but the number of possible states is (Π Ki = 100^9)
I believe there is a brute_force solution but i couldn't find it ):
Name |
---|
Auto comment: topic has been updated by Ismail_Alrifai (previous revision, new revision, compare).
The number of possible states should actually be bounded by $$$2^{32}$$$ as the problem statement guarantees that the product of $$$X$$$s fit into a 32-bit integer. That said, I believe you should be able to partition the congruences into two disjoint sets (of roughly equal number of states, so upper bounded by $$$2^{18}$$$) and generate all possible solutions in each set and use some kind of meet in the middle technique.
But the Ki <= 100, i meant in "possible state" as all combinations of Yij, try all Yij from each clue so the total 100 ^ 9.
if i missed some thing can you please explain how (possible states should actually be bounded by 2^32)
thank you :)
k is less than x and they say "the product of the X’s will fit into a 32-bit integer"
Right, I missed that.
well done Hosen <3
it can be solved by two ways: enum the x and test whether it fits the conditions. dfs search all remainder and use chinese remainder.
luckily, there is a code by RuJia.
i will check the code, thank you