3D - Least Cost Bracket Sequence

This is my solution for 2040E - Control of Randomness. It passed the tests, but I’m not sure whether deriving the DP formula in this way (splitting the min, solving the equation, and then putting the min back) is rigorous.

More formally, if we have $$$x_0$$$ is the only number that satisfies $$$x_0=f(x_0)$$$, and so do $$$x_1$$$ and $$$g(x_1)$$$, can we say that $$$x=h(f(x),g(x))\Leftrightarrow x=h(x_0,x_1)$$$? What if $$$h(x,y)=\min(x,y)$$$?

https://arxiv.org/pdf/2411.19826

Amazed by the perseverance, intellect, and exploratory spirit of mathematicians.

There are some functions $$$T_y$$$, which are defined as:

• $$$\forall j\le 1,y\in (0,1):T_y(j):=1$$$
• $$$\forall y\in (0,1):T_y(x):=T_y(xy)+T_y(x-xy)+1$$$

Find $$$y$$$ (s) so that the order of $$$\lim_{x\rightarrow+\infty}T_y(x)$$$ is minimized.

If you have like 6 to 8 hours to do cp, but you can only do cp, what will you do?

Learn new algorithms (by videos / blogs )

Write blogs (about algos / problems )

Write codes (easy problems / difficult or challanging problems ) (problems with specified tags / random problems )

When to use this:

• getting Wrong Answer but don't know why, or in a non-real-time-feedback contest and to check whether your code is right
• have a program to generate random input data
• for standard problems: have a code that will not output the wrong answer (time limit exceedings are acceptable)
• for special judge problems (example: problems that allow you to output one of the multiple answers): have a program to check if the answer is right
• for interactive problems: too weak in coding to know how to use :( if you know, comment below plz ˋ( ° ▽、° )
• if you are in a contest: make sure you have enough time to write these codes (data generator, bruteforce, checker, etc.)

You should have these files below in the same folder:

• 1.cpp (or other languages): Your code that got Wrong answer.

• For standard problems: std.cpp (or other languages): Code that will not output the wrong answer

• For special judge problems: checker.cpp (or other languages): To check if your output is right, returns 0 in main() if wrong, and returns 1 if correct

• gen_data.cpp (or other languages): To generate random input data

• hacker.sh/bat (or other languages that can run bash/cmd command): main program

Details of implementation:

For gen_data.cpp: use mt19937 and chrono::high_resolution_clock().now().time_since_epoch().count() to generate random integer instead of rand() and srand(time(0)). Tutorial of mt19937

For Windows, standard problems, the hacker.cpp: (sorry for not knowing much about batch)

#include <bits/stdc++.h>
using namespace std;

int main() {
	// ↓ compile your code here ↓
	// ↑ compile your code here ↑
	int i = 0;
	do {
		system("gen_data.exe > in.txt");
		system("1.exe < in.txt > out.txt");
		system("std.exe < in.txt > ans.txt");
		cout << ++i << endl;
	} while (!system("fc out.txt ans.txt"));
	cout << "in: " << endl;
	system("type in.txt");
	cout << "ans: " << endl;
	system("type ans.txt");
	cout << "out: " << endl;
	system("type out.txt");
	return 0;
}

For Windows, special judge problems, the hacker.cpp:

#include <bits/stdc++.h>
using namespace std;

int main() {
	// ↓ compile your code here ↓
	// ↑ compile your code here ↑
	int i = 0;
	do {
		system("gen_data.exe > in.txt");
		system("1.exe < in.txt > out.txt");
		cout << ++i << endl;
	} while (system("checker.exe"));
	cout << "in: " << endl;
	system("type in.txt");
	cout << "out: " << endl;
	system("type out.txt");
	return 0;
}

For Linux/macOS, standard problems, the hacker.sh:

if ! [ -e 1.cpp ]; then
    echo "file doesn't exist"
    exit
fi
# ↓ compile your code here ↓
shopt -s expand_aliases 
alias comp_cpp="g++ -O3 -Wall -Wextra -Wshadow -std=c++14"
comp_cpp std.cpp -o std.out
comp_cpp 1.cpp -o 1.out
comp_cpp gen_data.cpp -o gen_data
# ↑ compile your code here ↑
i=0
while true
do
    ./gen_data > in
    ./std.out < in > ans
    ./1.out < in > out
    diff -b -B ans out > dif
    if [  -s ./dif ]; then
        echo $i
        echo "hack:"
	cat in
        echo "ans:"
        cat ans
        echo "out:"
        cat out
        rm -f 1.out bruteforce.out gen_data dif
	exit
    else
        let i++
        echo $i
    fi
done

For Linux/macOS, special judge problems, the hacker.sh:

if ! [ -e 1.cpp ]; then
    echo "file doesn't exist"
    exit
fi
# ↓ compile your code here ↓
shopt -s expand_aliases 
alias comp_cpp="g++ -O3 -Wall -Wextra -Wshadow -std=c++14"
comp_cpp 1.cpp -o 1.out
comp_cpp gen_data.cpp -o gen_data
comp_cpp checker.cpp -o checker
# ↑ compile your code here ↑
i=0
while true
do
    ./gen_data > in
    ./1.out < in > out
    diff -b -B ans out > dif
    if [  ! checker ]; then
        echo $i
        echo "hack:"
	cat in
        echo "out:"
        cat out
        rm -f 1.out bruteforce.out gen_data dif
	exit
    else
        let i++
        echo $i
    fi
done

The main usage of this is to generate small-scale data for debugging.

It's bad for training