IEEEXtreme 18.0 was held yesterday, and there are problems to upsolve, so let's discuss them here.
If there's a problem you couldn't solve mention it in a comment and someone might help you.
I'll start, in the problem Power of three I couldn't get past 60%, I tried looking for any special properties of powers of 3 that I can use to solve for large numbers but I couldn't find anything that is unique to powers of 3 other than the 2nd to last digit being even and the last digit being either 1, 3, 9 or 7. That still doesn't reach the answer though, if anyone solved it could you share the idea?.
How to do increasing table?
Since both rows and columns are sorted then 1 must always come in the top left cell, after that the next number should be placed either next to me, or under me. I can check if the number was given to me in the input then I will know where it should go, or I can do dp to try and place it in either places and count how many ways are valid.
Let's fix a big mod value. Then 3^k % mod == given_string % mod . Using this idea, you can pass 100%.
Let $$$ N = 3^x $$$,
Let $$$\text{len}$$$ be the number of digits in $$$ N $$$.
Define $$$ d = \log_{10}(N) $$$, so $$$ d \in [\text{len} - 1, \text{len}) $$$.
Also, let $$$ d_2 = \log_3(10) $$$, where $$$ 3^{d_2} = 10 $$$.
From $$$ 10^d = N $$$, we can express this as:
Thus,
This means $$$ x \in [d_2 \cdot (\text{len} - 1), d_2 \cdot \text{len}) $$$.
The length of this range is small, so you want to check for every $$$ i $$$ in the range $$$ [d_2 \cdot (\text{len} - 1), d_2 \cdot \text{len}) $$$ whether $$$ 3^i = N $$$.
To verify if $$$ 3^i = N $$$, check if:
Where $$$ P $$$ is a prime number greater than 3.
Repeat this check for multiple primes $$$ P $$$, and if the result is always 1, then $$$ N $$$ is a power of 3.
where can i get the scoreboard ?
it's supposed to be here but it's not loading right now, they should release an updated scoreboard later on their site after filtering out cheaters and like so.
how long sud it roughtly take?
Last year the final scoreboard came out 2 weeks after the contest, so it should take around the same time