This solution comes from cancaneed.

There were some Chiness comments before which were deleted by the system.

I'll explain this below. We first define something:

• $$$(R1, B1, R2, B2)$$$: the probability that the guesser wins, when the hider has $$$R1$$$ red ones and $$$B1$$$ blue ones, and the guesser has $$$R2$$$ red ones and $$$B2$$$ blue ones.
• $$$p$$$: the probability hidng a red one.
• $$$q$$$: the probability guessing red.
• $$$rr$$$: the probability that the hider hides a red one and the guess guesses a red one.
• $$$rb$$$: the probability that the hider hides a red one and the guess guesses a blue one.
• $$$br$$$: the probability that the hider hides a blue one and the guess guesses a red one.
• $$$bb$$$: the probability that the hider hides a blue one and the guess guesses a blue one.

We have this transformation below：

For the guesser and the hider are maximizing the probability of winning, so we must make the partial of $$$q$$$ and $$$p$$$ be $$$0$$$, we'll get those:

The result should be:

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

非常感谢，已经添加代码。

OH， You are right, thank you very much, I've passed it.

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

#include <bits/stdc++.h>

using namespace std;

#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 get_hex() {
    string s; cin >> s;
    unsigned int x; stringstream(s) >> hex >> x;
    return *reinterpret_cast<int*>(&x);
}

string int_to_hex(int x) {
    stringstream ss;
    ss << hex << *reinterpret_cast<unsigned int*>(&x);
    return ss.str();
}

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();
}

int main() {
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
        cout << int_to_hex(solve()) << '\n';
    }
    return 0;
}

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

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.

Thank you very much, I've added the code for balls.

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.

Fixed.

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.

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.

Yeah, 100%.

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

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.

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.

I made the same mistake hah

I thought about clean cnt with n but I didn't fix it

You are supposed to swap reduce(decrease is better) and increase in the first line of your reply.

First, let me tell you why we are setting ai = max(ai, -bi):let's talk both the situations: ai >= -bi and ai < -bi , if ai >= -bi, that means ai doesn't change, when ai < -bi, the problem let us ensure r > 0, when we do this project i, r will be r + bi(bi if negative), so it's obviously why we let ai be max(ai, -bi), we must ensure r+bi > 0, that means we let ai = -bi(the case 2), we can decrease the judgement.Second, why sorting in the order of ai + bi can work? This problem trouble me for a long time at first, when we let ai be max(ai, -bi), we can ensure ai >= -bi, that means ai + bi is not negative, but it can be zero, if we can't do project i, for j (aj + bj < ai + bi) we must can't do all of this, too.That is because aj is greater than ai or not, if aj >= bi , we can't do project j, if aj is smaller than ai, and aj + bj < ai + bi, we can't do project i that means r < ai, when we do the left thing, r will be smaller, that means we can't do project i, either. So this can work.