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.
Key observations
One way of building any valid solution is inserting the numbers $$$1, 2, ..., 2n$$$ in that order. When inserting each number, you can append it to the top row or bottom row, and both rows start empty.
Notice that in each step you can't make the bottom row longer than the top one, because the number you will later append in the top row will be bigger than the one below it.
Solution
With this knowledge we can calculate $$$dp(i,j)$$$ as the number of ways to fill the first $$$i$$$ positions of the top row and $$$j$$$ positions of the bottom row. If we build a solution using the previous idea, the next number we have to append is $$$i+j+1$$$. This tells us that calculating $$$dp$$$ as a forward DP is easier.
To deal with the restrictions we will create two sets $$$A$$$ and $$$B$$$. $$$A$$$ contains the numbers that have to go in the top row and $$$B$$$ in the bottom row.
Think about the transitions. From $$$dp(i,j)$$$ we can either append the next number $$$i+j+1$$$ to the top or bottom.
So because we are doing forward DP we just add $$$dp(i,j)$$$ to $$$dp(i+1,j)$$$ and/or $$$dp(i,j+1)$$$ if they meet the previous restrictions.
The relevant part of the code looks like this:
Let's fix a big mod value. Then 3^k % mod == given_string % mod . Using this idea, you can pass 100%.
How do we choose k?
My approach was just naive divide string by 3 (wrote function to divide the string directly by 3). To optimize this a bit, I first divided string by 729 (so that it converges to small values faster) while it was divisible by it, and then divided it by 3. Instead of 729, I tried to divide string by 3**8 and 3**10, but that seemed to counter productively increase the run time for large strings, so I couldn't optimize any further.
Suppose len = size of string. Then k will be always greater than or equal to len*2-1. So i just checked all k = [len*2-1,len*2+1000000].
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
how to solve Icarus , invertible pairs ...
For Icarus we created a random tree with only left nodes, It don't give 100% but we pass 90% of the cases.
Hint: creating a line with 2n nodes will always work ( the remaining part is seeing when to start from the first node or from the 2*n node ).
Let's make
l_cnt
be the count of theL
, andu_cnt
for theU
.I'll explain how to solve this when
l_cnt
is less than or equal tou_cnt
, the rest can be solved similarly.For
l_cnt <= u_cnt
, we build a chain withu_cnt + 2
nodes, and the every node of the tree only has one left node or no left node, which means theR
in the input is useless. Why this? Because for this chain, we can find a starting node that make all theL
andU
move legal and after every turn, the depth of the ending node will not be bigger, this means the deepest node can never be reached.Therefore, we just need to consider which node meets this. We just need to consider during one turn the minimum depth, let's call it
high
(the highest one), then thehigh
's left son will be the node.We can calculate by this code:
For the rest, it's similar.
Do you know about the last test case they added, after rejudging? My solution uses similar idea and it passed 100% of cases before the re-judgement but only 90% of cases after that.
You man not consider the
l_cnt
andr_cnt
are zero, and theu_cnt
is1
, this may make you build a tree with3
nodes, which is more than2
. I just spj this part.damn you are right, thank you very much!
for invertible pairs let dp[i][j] denote the maximum subarray sum ending at the ith position and weather we used the operation on the last 2 positions lets only consider even position now to find the solution ending at an odd position it'll be dp[i][j] — a[i] * (-1 if j is equal to 1 in other words we used the operation on the last position
How to solve two fridges? https://vjudge.net/contest/667221#problem/B
How to solve Digit Swap? https://vjudge.net/contest/667221#problem/X
i have a question about this problem even tho its from ieee 16
https://csacademy.com/ieeextreme-practice/task/array
how to find a solution by fixing the prefix sum for 1 element in a component since it determines every other prefix sum in the component now i was able to find an array but not the lexicographically smallest
Hello, I have a question about stones. Our solution was a 5d DP[R1][B1][R2][B2][Start] which holds the probability of the player starting to win given the state of the balls (R1,B1,R2,B2). This is our code :
include
include
include
I believe its in the probabilities of choosing or guessing which we assume is only based on the current balls each player has
Rashed_Khalil Awab unknownSolver the_last_smilodon