Блог пользователя BluoCaroot

Автор BluoCaroot, история, 4 недели назад, По-английски

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?.

  • Проголосовать: нравится
  • +41
  • Проголосовать: не нравится

»
4 недели назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

How to do increasing table?

  • »
    »
    4 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    4 недели назад, # ^ |
    Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

    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.

    • We can append it to the top row if $$$i+1<n$$$ (as we need at least one free space for it) and $$$i+j+1 \not\in B$$$ (if it is in $$$B$$$ we can't append it in the top row).
    • We can append it to the bottom row if $$$j+1<n$$$, $$$i+j+1 \not\in A$$$ and additionally $$$j+1 \le i$$$ (as we can't make the bottom row longer than the top row).

    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:

    	vector <vector <ll>> dp(n+1, vector<ll>(n+1,0));
    	dp[0][0] = 1;
    	const ll MOD = 998244353;
    
    	for(int i=0; i<=n; i++){
    		for(int j=0; j<=n; j++){
    			if(!B.count(i+j+1) and i+1 <= n){
    				dp[i+1][j] += dp[i][j];
    				dp[i+1][j] %= MOD;
    			}
    			if(i >= j+1 and !A.count(i+j+1) and j+1 <= n){
    				dp[i][j+1] += dp[i][j];
    				dp[i][j+1] %= MOD;
    			}
    		}
    	}
    
»
4 недели назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

Let's fix a big mod value. Then 3^k % mod == given_string % mod . Using this idea, you can pass 100%.

  • »
    »
    4 недели назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      4 недели назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      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].

»
4 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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:

$$$ 3^{d_2 \cdot d} = N $$$

Thus,

$$$ x = d_2 \cdot d $$$

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:

$$$ 3^{-i} \cdot N \mod P = 1 $$$

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.

  • »
    »
    4 недели назад, # ^ |
      Проголосовать: нравится -13 Проголосовать: не нравится

    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)

»
4 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

where can i get the scoreboard ?

  • »
    »
    4 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      4 недели назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      how long sud it roughtly take?

      • »
        »
        »
        »
        4 недели назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Last year the final scoreboard came out 2 weeks after the contest, so it should take around the same time

»
4 недели назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится
  • »
    »
    4 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    For Icarus we created a random tree with only left nodes, It don't give 100% but we pass 90% of the cases.

  • »
    »
    4 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 ).

  • »
    »
    4 недели назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    Let's make l_cnt be the count of the L, and u_cnt for the U.

    I'll explain how to solve this when l_cnt is less than or equal to u_cnt, the rest can be solved similarly.

    For l_cnt <= u_cnt, we build a chain with u_cnt + 2 nodes, and the every node of the tree only has one left node or no left node, which means the R in the input is useless. Why this? Because for this chain, we can find a starting node that make all the L and U 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 the high's left son will be the node.

    We can calculate by this code:

        if (l_cnt <= u_cnt) {
            int depth = 0;
            int high = 0;
            for (int i = 0; i < str.size(); i++) {
                if (str[i] == 'L') {
                    depth++;
                } else if (str[i] == 'U') {
                    depth--;
                    high = min(high, depth);
                }
            }
            cout << u_cnt + 2 << " " << -high + 1 << " " << u_cnt + 2 << "\n";
            for (int i = 1; i <= u_cnt + 2; i++) {
                cout << (i + 1 <= u_cnt + 2 ? i + 1 : 0) << " 0\n";
            }
        }
    

    For the rest, it's similar.

    • »
      »
      »
      4 недели назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        4 недели назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        You man not consider the l_cnt and r_cnt are zero, and the u_cnt is 1, this may make you build a tree with 3 nodes, which is more than 2. I just spj this part.

  • »
    »
    4 недели назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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:

    $$$dp[i][j] = \begin{cases} \text{Let } (f_1, s_1) = dp[i-1][0], (f_2, s_2) = dp[i-1][1] \newline \text{If } j = 0: \newline s_1 \leftarrow \max(s_1 + A_{2i-1}, A_{2i-1}) \newline f_1 \leftarrow \max(f_1, s_1) \newline s_1 \leftarrow \max(s_1 + A_{2i}, A_{2i}) \newline f_1 \leftarrow \max(f_1, s_1) \newline s_2 \leftarrow \max(s_2 + A_{2i-1}, A_{2i-1}) \newline f_2 \leftarrow \max(f_2, s_2) \newline s_2 \leftarrow \max(s_2 + A_{2i}, A_{2i}) \newline f_2 \leftarrow \max(f_2, s_2) \newline \text{if } j = 1: \newline s_1 \leftarrow \max(s_1 - A_{2i-1}, -A_{2i-1}) \newline f_1 \leftarrow \max(f_1, s_1) \newline s_1 \leftarrow \max(s_1 - A_{2i}, -A_{2i}) \newline f_1 \leftarrow \max(f_1, s_1) \newline s_2 \leftarrow \max(s_2 - A_{2i-1}, -A_{2i-1}) \newline f_2 \leftarrow \max(f_2, s_2) \newline s_2 \leftarrow \max(s_2 - A_{2i}, -A_{2i}) \newline f_2 \leftarrow \max(f_2, s_2) \newline dp[i][j] = (\max(f_1, f_2), \max(s_1, s_2)) \end{cases}$$$
    Implementation
»
4 недели назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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$$$.

»
4 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
4 недели назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

»
4 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

using namespace std;

// Memoization table
double dp[41][41][41][41][2];
bool computed[41][41][41][41][2];

// Recursive function to calculate the probability of Alice winning
double probability(int R1, int B1, int R2, int B2, int start) {
    // Base cases
    if (R1 == 0 || B1 == 0) { // Alice loses
        if (start == 0) return 0.0; // AA is Alice, she loses
        else return 1.0;             // AA is Bob, Alice loses but Bob wins
    }
    if (R2 == 0 || B2 == 0) { // Bob loses
        if (start == 0) return 1.0; // AA is Alice, she wins
        else return 0.0;             // AA is Bob, he loses
    }

    // Check if this state has been computed
    if (computed[R1][B1][R2][B2][start]) {
        return dp[R1][B1][R2][B2][start];
    }

    // Calculate probability for the current state
    double result = 0.0;
    if (start == 0) {  // Alice is AA
        double prob_red_A = static_cast<double>(R1) / (R1 + B1);
        double prob_blue_A = static_cast<double>(B1) / (R1 + B1);
        double prob_red_B = static_cast<double>(R2) / (R2 + B2);
        double prob_blue_B = static_cast<double>(B2) / (R2 + B2);
        // Alice chooses red
        result += prob_red_A*prob_red_B*(1-probability(R1-1,B1,R2,B2,1));
        result += prob_red_A*prob_blue_B*(1-probability(R1,B1,R2,B2-1,1));
        result += prob_blue_A*prob_blue_B*(1-probability(R1,B1-1,R2,B2,1));
        result += prob_blue_A*prob_red_B*(1-probability(R1,B1,R2-1,B2,1));

    } else {  // Bob is AA
        double prob_red_A = static_cast<double>(R1) / (R1 + B1);
        double prob_blue_A = static_cast<double>(B1) / (R1 + B1);
        double prob_red_B = static_cast<double>(R2) / (R2 + B2);
        double prob_blue_B = static_cast<double>(B2) / (R2 + B2);

        result += prob_red_A*prob_red_B*(1-probability(R1,B1,R2-1,B2,0));
        result += prob_red_A*prob_blue_B*(1-probability(R1-1,B1,R2,B2,0));
        result += prob_blue_A*prob_blue_B*(1-probability(R1,B1,R2,B2-1,0));
        result += prob_blue_A*prob_red_B*(1-probability(R1,B1-1,R2,B2,0));

    }

    // Memoize the result
    computed[R1][B1][R2][B2][start] = true;
    dp[R1][B1][R2][B2][start] = result;
    return result;
}

int main() {
    int R1, B1, R2, B2;
    cin >> R1 >> B1 >> R2 >> B2;

    // Initialize memoization table
    for (int i = 0; i <= 40; ++i)
        for (int j = 0; j <= 40; ++j)
            for (int k = 0; k <= 40; ++k)
                for (int l = 0; l <= 40; ++l)
                    computed[i][j][k][l][0] = computed[i][j][k][l][1] = false;

    // Compute the result and apply the 0.25 factor
    double answer = probability(R1, B1, R2, B2, 0);

    // Output the result with required precision
    cout << setprecision(9) << answer << endl;

    return 0;
}

I believe its in the probabilities of choosing or guessing which we assume is only based on the current balls each player has

»
4 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to do stones and star road?

  • »
    »
    3 недели назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
4 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How can I optimize the corporation problem? I only reach 30%

»
4 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What about Increasing-decreasing permutations

»
4 недели назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

How to solve Balls ?

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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:

    Code
»
4 недели назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

how to solve Bounded tuples

»
4 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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 $$$.

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    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 use unordered_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.

»
4 недели назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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:

$$$ 3^x = N \space (\mod 998244353 \space ) $$$

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:

Spoiler

This solution works like in $$$\approx 300 \textrm{ms}$$$, so it is fast enough.

  • »
    »
    3 недели назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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 :

    $$$ x = ans$$$
    $$$ \Rightarrow 3^{ans} \in [10^{n-1} , 10^n[\ , n := len(N)$$$

    And since we will always have an ans, it follows that :

    $$$\text{if }\ 3^{ans} \not\in [10^{n-1}, 10^n[$$$
    $$$\text{then } \ \ \ x \neq ans$$$

    And as ans is unique, there will be no other values for x to exist, therefore N is not a Power of Three.

    Code
    • »
      »
      »
      3 недели назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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$$$.

»
3 недели назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

How to solve Halving?

  • »
    »
    3 недели назад, # ^ |
    Rev. 2   Проголосовать: нравится +43 Проголосовать: не нравится

    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$$$.

    • »
      »
      »
      3 недели назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can you provide your implementation?

      • »
        »
        »
        »
        3 недели назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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.

      • »
        »
        »
        »
        3 недели назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        My code
»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Tutorial for Star-Road

»
3 недели назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

i passed 42% of the test cases at increasing table just by cout<<0<<endl

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve Another Sliding Window? My brute force approach gets 20 points and the rest TLE.

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      3 недели назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thank you! I will try implementing with this logic Do you have an idea on how to solve Doubled Sequence?

»
3 недели назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

nvm

»
3 недели назад, # |
Rev. 10   Проголосовать: нравится +19 Проголосовать: не нравится

Update 2024-11-2: The problem Balls has been solved with Romy67's help.

Update 2024-11-10: The problem IEEE754 Emulator has been solved with yanire and Romy67's help.

Update 2024-11-10: The problem Stones has been solved with cancaneed's help.

Update 2024-11-10: The problem This is not an optimization problem has been solved with cancaneed's help.

Update 2024-11-11: The problem Corporation has been solved with yanire's help.

Update 2024-11-12: The problem Queries has been solved by cancaneed.

I'm trying to solve those problem below (unsolved):

  • Disparate Data Sets (solved with Python by using csv to parse input)
  • Bounded tuple
  • Triumvirates
  • Increasing-decreasing table
  • Doubled Sequence

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.

  • »
    »
    3 недели назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    2 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    "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.

    • »
      »
      »
      2 недели назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Could you just give me a web about Taylor Shift problem? When I used google to get the results, all I got are pages realted with Taylor Swift.

  • »
    »
    13 дней назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    IEEE754 Emulator:

    Read the inputs as integers. Emulating LUT, NAND requires bitwise operations, and store is simple. To emulate FMA, cast the integers to float (using reinterpret_cast or union of float,int), use std::fma to compute result, then cast back to integer.

    Corporation:

    I'll explain how to compute the sum of salaries/happiness as average is simply sum / length. Divide the array into blocks of size K. Each block will hold the sum of salaries and happiness. If an add update covers an entire block, it is easy to recompute sum and happiness in constant time. If a set update covers an entire block, we will have to iterate over the block, but if all of the elements of the block are equal, then it is constant time. If an update/query covers only a part of a block, we will "rebuild" the block and update/query.

    Time analysis: Time for query is $$$ O(\frac{n}{k}) $$$ covered blocks times $$$ O(1) $$$ time + (1/2) uncovered blocks times $$$ O(k) $$$ = $$$O(\frac{n}{k}) + O(k)$$$. Time for add update is $$$ O(n/k) $$$ covered blocks times $$$ O(1) $$$ time + (1/2) uncovered blocks times $$$ O(k) $$$ = $$$O(\frac{n}{k}) + O(k)$$$. Time for set update is similar but covered blocks whose elements are not equal will cost $$$O(k)$$$ . Note that the number of such blocks starts at (at most) $$$O(\frac{n}{k})$$$ and decreases by 1 every time we apply a set operation over the entire block (which costs $$$O(k)$$$ time), and each update can only create 2 such blocks, so total time increases by a maximum of $$$O((\frac{n}{k}+q) \cdot k)$$$ . By choosing $$$k\approx\sqrt{n}$$$ We get $$$ O(n \sqrt{n}) $$$.

    • »
      »
      »
      13 дней назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      For IEEE754 Emulator, I did exactly the same thing, but I only got 85%. Could you just post your code?

      • »
        »
        »
        »
        13 дней назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        #define rep(i, s, e) for(int i = (s); i < (e); i++)
        #define pb push_back
        
        #define i2f(x) (*reinterpret_cast<float*>(&(x)))
        #define f2i(x) (*reinterpret_cast<int*>(&(x)))
        
        using vi = vector<int>;
        using vvi = vector<vector<int>>;
        
        int solve() {
            vi C(1);
            C[0] = get_hex();
            int L; cin >> L;
            vvi LUT(L);
            rep(i,0,L) {
                int ki; cin >> ki;
                LUT[i].resize(ki);
                for(int& x : LUT[i]) x = get_hex();
            }
            int Q; cin >> Q;
            while(Q--) {
                char op; cin >> op;
                if(op == 'C') C.pb(get_hex());
                if(op == 'N') {
                    int i,j; cin >> i >> j;
                    C.pb(~(C[i]&C[j]));
                }
                if(op == 'L') {
                    int i,j,b; cin >> i >> j >> b;
                    C.pb(LUT[i][(C[0]>>j)&((1<<b)-1)]);
                }
                if(op == 'F') {
                    int i,j,k; cin >> i >> j >> k;
                    float res = fma(i2f(C[i]),i2f(C[j]),i2f(C[k]));
                    C.pb(f2i(res));
                }
            }
            return C.back();
        }
        
        
        • »
          »
          »
          »
          »
          12 дней назад, # ^ |
          Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

          What does your get_hex and output look like?

          I just used your code and added my own get_hex and output, then I still got 85%.

          code
          • »
            »
            »
            »
            »
            »
            12 дней назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Make sure to output leading zero in your hex. So, 0 should be 00000000.

    • »
      »
      »
      11 дней назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thank you very much, I've added the code for IEEE754 Emulator and Corporation.