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.
You can even check for one x, because the range is bounded by 3 and we know for each x what 3^x mod 10 should be so we can check only the x for which it's correct (if there's one)
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
For invertible pairs, i came up with the following solution: Similar to kadane's algorithm, let $$$dp[i][j]$$$ be the tuple of the global maximum, and the current maximum up to the $$$i^{th}$$$ pair, $$$j = 0$$$ if you choose to not invert, and $$$j = 1$$$ otherwise. So we get the following recurrence:
How to solve two fridges? https://vjudge.net/contest/667221#problem/B
It's easy to check every possible temp value for the first fridge, call it $$$temp1 \in [-100, 100]$$$ and every possible value for the second fridge, $$$temp2 \in [temp1, 100]$$$. For each pair, check if all the items are placed in one of the two fridges meaning $$$a_i \leq temp1 \leq b_i$$$ or $$$a_i \leq temp2 \leq b_i$$$.
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
And by "our solution" you mean "Chat GPT", right?
Rashed_Khalil Awab unknownSolver the_last_smilodon
How to do stones and star road?
Here is my code of star road: star_road.cpp
I will post the tutorial about 12 hours later. I should have posted it a few hours ago, but you know codeforces just occur sever dump.
BTW, if you know Chinese, you can read the tutorial of Chinese editon: Tutorial of Chinese edition.
Tutorial is coming:
We can solve this problem with segment tree and merging of segment trees. First, we need to discretize the stars to make them between $$$[1, len]$$$, $$$len$$$ is the number of different stars. Then we do dfs from any node, when we reach a node, we build a segment tree for this node. For the leaf nodes of the segment tree within $$$[l, l]$$$, it will hold two values: * $$$LIS$$$: LIS ended with $$$l$$$. * $$$LDS$$$: LDS ended with $$$l$$$.
For the non-leaf nodes within $$$[l, r]$$$, it will hold two values: * $$$LIS$$$: the maximum value of its sons' $$$LIS$$$. * $$$LDS$$$: the maximum value of its sons' $$$LDS$$$.
When we start going back, we can get: * $$$son[i].LIS$$$: the son $$$i$$$'s $$$LIS$$$ within $$$[1, star[u] - 1]$$$ from the segment tree $$$i$$$. * $$$son[i].LDS$$$: the son $$$i$$$'s $$$LDS$$$ within $$$[star[u] + 1, len]$$$ from the segment tree $$$i$$$.
We use $$$star[u] - 1$$$ and $$$star[u] + 1$$$ to make sure $$$star[u]$$$ can be picked, so if we pick $$$u$$$, we will get $$$ans = max(ans, son[i].LIS + 1 + son[j].LDS), i \ne j$$$, and we can sort the sons by $$$LIS$$$ and $$$LDS$$$ to avoid the enumeration of $$$i, j$$$.
How to get the part if we don't pick $$$u$$$? We can solve this part during merging of two segment trees. During the merging of segment tree $$$a$$$ and segment $$$b$$$, we'll be in a section $$$[l, r]$$$, we can get the maximum value of $$$LIS$$$ within $$$[l, mid]$$$ from $$$a$$$ (or $$$b$$$), and $$$LDS$$$ within $$$[mid + 1, r]$$$ from $$$b$$$ (or $$$a$$$). , then those two parts can be combined, and those combinations include the part if we don't pick $$$u$$$. In other words, we can get $$$ans = max(ans, LIS[lc[a]] + LDS[rc[b]], LIS[lc[b]] + LDS[rc[a]])$$$.
When we finish all merging of node $$$u$$$, we must do two updates: * If $$$max(son[i].LIS + 1)$$$ is larger than the $$$LIS$$$ of segment tree $$$u$$$ at $$$star[u]$$$, we need to update it to $$$max(son[i].LIS + 1)$$$, this means the LIS ended with $$$star[u]$$$ has changed. * If $$$max(son[i].LDS + 1)$$$ is larger than the $$$LDS$$$ of segment tree $$$u$$$ at $$$star[u]$$$, we need to update it to $$$max(son[i].LDS + 1)$$$, this means the LDS ended with $$$star[u]$$$ has changed.
How can I optimize the corporation problem? I only reach 30%
Maybe you can use Segment Tree or Fenwick Tree.
What about Increasing-decreasing permutations
How to solve Balls ?
I tried using the inclusion exclusion principle,
Since it's given k <= 100 computations would go upto 2 power 100 with the normal brute force way but it's also given that gcd of any Ei,Ej = 1. So I had figured the product of all given Ei would eventually exceed the limits of N (go greater than 1e14) so that optimisation was there.
I also had this case where if we encounter Ei = 1 for any i, answer would be n
But it still passed only 90%. Couldn't figure out how to optimise it more/find a better solution. Anyone have any ideas?
Code I submitted:
how to solve Bounded tuples
For the problem called "Cheap construction," I hashed all the substrings in O(n^2) time. After that, I got the answers to all the substrings and then printed the answer. I still got TLE, even though n <= 5000. Can someone help?
Actually, my algorithm's time complexity is $$$ O(n^2) $$$, too. However, I got a $$$ TLE $$$ at first. Then, I just try to optimize it. I don't calculate all the sub-strings at first; I just calculate sub-strings with one, two, ..., n characters. For every type of sub-strings, we calculate the number of components, this may run more quickly, but with the same time complexity $$$ O(n^2) $$$.
Here is my code cheap_construction.cpp. This is rather close to $$$ TLE $$$. The slowest sample got $$$ 946ms $$$.
did u got 100%
i did almost the same thing i got mle and only 50% passed
Yeah, 100%.
I think the bottleneck in hashing solutions comes from the data structure that maps hashes to occurrences. For example, if we use C++
map
, a log factor gets added to the time complexity, and if we useunordered_map
, the constant factor might get too big.The model solution uses suffix array to identify groups of occurrences and their resulting connected components. Its time complexity is $$$O(N^2)$$$ and runs in 74 ms.
I solved the problem "Power of three" with my teammate abner_vidal
We solved this problem using the discrete logarithm.
It's important to remember what a primitive root is: In modulo $$$p$$$, where $$$p$$$ is a prime number, $$$g$$$ is considered a primitive root if each element in the set $$${1, 2, ..., p-1}$$$ can be expressed as a power of $$$g$$$ modulo p.
We chose $$$p = 998244353$$$ (well known NTT prime number), and 3 is a primitive root of this prime number. Then we realized that calculating the smallest power of 3 that reaches $$$N$$$ is equivalent to finding the discrete logarithm, so we need to calculate:
Using an algorithm like Baby-step Giant-step, we can calculate this quickly.
There is an issue with only using one prime number: it fails quickly because may find solutions that only works within the modulo $$$p$$$. To avoid this we ended using 3 differents prime numbers similars to $$$998244353$$$ with primitive root of 3, these are: $$${998244353, 469762049, 167772161}$$$
If they all give the same solution, then the answer is correct; otherwise, we return $$$-1$$$.
It’s a probabilistic solution, but it’s very unlikely to fail in all three cases at the same time. It’s a solution we came up with quickly, and we didn’t question it much, really haha.
Solution here:
This solution works like in $$$\approx 300 \textrm{ms}$$$, so it is fast enough.
Gj, a smart solution.
I think you could have found the deterministic one if you thought more about it.
Otherwise, here's my way of doing it. A quick note : By choosing to work with the discret log, we have to make sure that the range $$$[0,\phi (p)] $$$ contains all possible values of $$$x$$$. Because when we find a valid
ans
, it has to be equal to the real $$$x$$$, otherwise another layer of complexity will be added.We know that if an $$$x$$$ do exist, then :
And since we will always have an
ans
, it follows that :And as
ans
is unique, there will be no other values for x to exist, therefore N is not a Power of Three.Figured out that my solution could have failed ($$$N$$$ being equal to something like $$$(3^x + k.p)$$$).
Additionally, the condition introduced above is not complete. Still need to verify that $$$3^{ans}$$$ exactly matches $$$N$$$.
How to solve Halving?
First check for some cases that makes the answer $$$0$$$. (if some value occurs in $$$C$$$ but not in its correct position, or if theres a pair that cant be replaced because of $$$R_i$$$)
now you should have pairs of the following type (assume $$$R_i = x, B_i = y$$$):
$$$1- (-1, -1).$$$
$$$2- (y, -1).$$$
$$$3- (n, z).$$$ ($$$z$$$ is $$$-1$$$ or $$$y$$$)
First case you need to find some element smaller or larger than $$$y$$$ (depending on $$$x$$$), and then multiply the answer by two because there are two ways to place them.
Second case is the same but dont multiply by two.
Third case you should ignore both $$$n$$$ and $$$y$$$.
now in order to match them, we will do dp on the values $$$1,2,3..2 \cdot N$$$.
lets use $$$dp[i][\text{count of values in B unused}][\text{count of values not in B unused}]$$$ to find the number of ways to match the elements in $$$B$$$ with the elements not in $$$B$$$ uptill the $$$ith$$$ element.
we skip the elements in case $$$3$$$. Elements in $$$B$$$ we either match them with a smaller element or match them with a later element depending on $$$R$$$. and finally elements not in $$$B$$$ can be paired with any element smaller or larger in $$$B$$$.
you can optimize the memory by noticing that you only need $$$i$$$ and $$$i+1$$$ while calculating the $$$dp$$$.
Can you provide your implementation?
I just have a smae solution, if you want the code, here is my implementation: halving.cpp.
If you know Chinese, here is a more detailed tutorial with Chinese: Tutorial of Chinese edition.
Both links, go to the Chinese webpage.
Fixed.
Tutorial for Star-Road
i passed 42% of the test cases at increasing table just by
cout<<0<<endl
How to solve Another Sliding Window? My brute force approach gets 20 points and the rest TLE.
Sliding window.
For each position calculate POS[i], the furthest index j you can match with.
Now if a interval [X,Y] is good then POS[X] >= Y and POS[X+1] >= Y — 1 and so on until the middle.
Now it's a bit annoying since to test [X,Y] it's still O(N), but if you add X to POS[X], now to test if [X,Y] works you just do MIN in the interval [X,MID], and if it's big enough, then you're good. Now just do sliding window on this, extend while you can.
Here's my code: https://pastebin.com/39RQx8UZ
Thank you! I will try implementing with this logic Do you have an idea on how to solve Doubled Sequence?
nvm
Update 2024-11-2: The problem
Balls
has been solved with Romy67's help.I'm trying to solve those problem below (unsolved):
Python
by usingcsv
to parse input)The problems not in the list have been solved, if you want the code, here is the repo: IEEExtreme-18-code.
If you know Chinese, here is a tutorial for those sovled problems: Tutorial of Chinese Edition
Any ideas related to the unsolved problmes are welcome.
For Balls, I find the exact same problem here, Lostborn . You can use recursive dfs and precompute for small values. The complexity is O(K sqrt(N)), but in reality it is much faster, I guess.
Thank you very much, I've added the code for balls.
"This is not an optimization problem" is a nice problem which could be transformed into a Taylor Shift problem. And Taylor shift is solvable in N*log(N) using Number Theoretic Transform.