I learned some stuff about quadrangle inequality recently. I wanted to collect those in one place, so here goes.

Note: I use $$$A \prec B$$$ to denote that $$$A$$$ is strictly more optimal than $$$B$$$. $$$\preceq$$$ is self-explanatory. The actual order depends on problems, in some cases it's $$$<$$$, in some cases, it's $$$>$$$. All of the arrays are 1-indexed and have length $$$n$$$ (if unspecified). Also for ease of following the proofs, I have tried to maintain that $$$a \leq b \leq c \leq d$$$ wherever they are used. By the notation $$$[l,r]$$$ I mean the subarray taken by using indices $$$i$$$ such that $$$l \leq i \leq r$$$.

Quadrangle Inequality: Consider a real valued function $$$C(l, r)$$$ which is defined for $$$1 \leq l \leq r \leq n$$$. Let us call this function the cost function. The cost function is said to satisfy the quadrangle inequality iff $$$C(a, c)+C(b, d) \preceq C(a, d) + C(b, c)$$$ for $$$a \leq b \leq c \leq d$$$. Intuitively this implies that for $$$C()$$$, "wider is worse". Let us call the cost function Quadrangle Friendly (or QF in short) iff it satisfies the quadrangle inequality.

Let us also define the function $$$opt(r)=$$$ rightmost $$$l$$$ such that $$$C(l, r)$$$ is optimum where $$$1 \leq l \leq r \leq n$$$.

Fact 1) If cost function is QF then $$$opt()$$$ is non-decreasing.
Proof: Suppose for some $$$1 \leq c < d \leq n$$$, we have $$$b = opt(c) > opt(d) = a$$$ so ($$$a < b \leq c < d$$$. Then by definition of $$$opt()$$$ we have $$$C(b, c) \preceq C(a, c)$$$ and $$$C(a, d) \prec C(b, d)$$$. Adding these two we get, $$$C(a, d) + C(b, c) \prec C(a, c) + C(b, d)$$$, a contradiction with quadrangle inequality. □

Remark: It is not required that $$$opt(r)$$$ is the rightmost optimal $$$l$$$. That is only used for the function to be well defined. In fact, the proof can be imitated to show the same fact iff $$$opt(r)$$$ is defined as leftmost optimal $$$l$$$ too.

Array Partition DP: Suppose we want to partition an array into $$$k$$$ non-empty subarray and if the subarrays are $$$[l_1, r_1], \cdots, [l_k, r_k]$$$ ($$$r_i + 1 = l_{i+1}$$$ and $$$l_1 = 1, r_k = n$$$) then the cost of the partition is $$$C(l_1, r_1) + \cdots + C(l_k, r_k)$$$. To find the optimal partition cost, we perform a dp where $$$dp[i][k] = $$$ optimal cost to partition subarray $$$[1, i]$$$ into $$$k$$$ subarrays. Then, we have
$$$dp[0][0] = 0$$$
$$$dp[i][0] = dp[0][k] = \infty $$$ ($$$i, k \geq 1$$$)
$$$dp[i][k] = \min \limits_{1 \leq j \leq i} \{ dp[j-1][k-1] + C(j, i) \} $$$ ($$$i,k \geq 1$$$)
Note that, the $$$\min$$$ and $$$\infty$$$ are all in terms of $$$\prec$$$.

Fact 2) Let us define $$$f_k(l, r) = dp[l-1][k-1] + C(l, r)$$$ for $$$k \geq 1$$$ and $$$1 \leq l \leq r$$$. If $$$C()$$$ is QF, then $$$f_k$$$ is QF.
Proof: $$$a \leq b \leq c \leq d$$$, then
$$$f_k(a, c) + f_k(b, d)$$$
$$$= dp[a-1][k-1] + dp[b-1][k-1] + C(a, c) + C(b, d)$$$
$$$\preceq dp[a-1][k-1] + dp[b-1][k-1] + C(a, d) + C(b, c) $$$
$$$= f_k(a, d) + f_k(b, c)$$$. □

Remark: So when we compute $$$dp[i][k]$$$, what we want is $$$opt(i)$$$ for the function $$$f_{k}$$$. And when $$$C()$$$ is QF, $$$f_{k}$$$ is also QF which lets us know $$$opt(i)$$$ is non-decreasing and we can apply Divide and Conquer Trick. Another interesting fact is that if we create the partition right to left instead of left to right i.e. $$$dp'[i][k] = $$$ optimal cost to divide $$$[i, n]$$$ to $$$k$$$ subarrays, then the corresponding $$$f'_k(l, r) =$$$ $$$ dp'[r+1][k-1] + C(l, r)$$$ is also QF. The proof is almost same as the one given above.

Fact 3) Let us define $$$opt_k(r)$$$ for $$$f_k$$$ i.e. $$$opt_k(r) = $$$ the rightmost $$$l$$$ such that $$$f_k(l, r)$$$ is optimum. If $$$C()$$$ is QF then $$$opt_k(r) \leq opt_{k+1}(r)$$$ ($$$k \geq 1$$$).
Proof: If $$$k = 1$$$, the fact is true by default. Suppose $$$k > 1$$$ and $$$opt_k(r) > opt_{k+1}(r)$$$. So that means we can find an optimal partition for $$$dp[r][k]$$$: $$$[a_k, d_k], \cdots, [a_1, d_1]$$$ and an optimal partition for $$$dp[r][k+1]$$$: $$$[b_{k+1}, c_{k+1}], \cdots, [b_1, c_1]$$$ where $$$a_1 = opt_k(r) >$$$ $$$ opt_{k+1}(r) = b_1$$$. Note that the subarrays are numbered in reverse order (first interval is rightmost), this is to make the proof writing a bit easy.

let $$$i$$$ be the minimum index such that $$$a_i \leq b_i$$$. There is at least one such $$$i$$$ as $$$a_k < b_k$$$ and $$$i > 1$$$ as $$$a_1 > b_1$$$. Then $$$a_{i-1} > b_{i-1} \implies d_{i} > c_{i}$$$. In particular $$$a_i \leq b_i \leq c_i \leq d_i$$$. Intuitively what we just did is choose a $$$i$$$ such that $$$[b_i, c_i]$$$ is inside $$$[a_i, d_i]$$$.

Now we'll create a contradiction with 3 inequalities. First, consider the partition $$$[b_{k+1}, c_{k+1}], \cdots, [b_{i+1}, c_{i+1}], [b_i, d_i], [a_{i-1}, d_{i-1}], \cdots, $$$ $$$[a_1, d_1]$$$. This is a $$$k+1$$$ size partition and thus it's cost will be strictly worse than the partition using only $$$[b_j, c_j]$$$ (Due to the definition of $$$b_1 = opt_{k+1}(r)$$$). So we can infer that $$$C(b_i, c_i) + \cdots C(b_1, c_1) \prec C(b_i, d_i) + C(a_{i-1}, d_{i-1}) + \cdots + C(a_1, d_1)$$$

Second, by quadrangle inequality, $$$C(a_i, c_i) - C(b_i, c_i) \preceq C(a_i, d_i) - C(b_i, d_i)$$$. Adding this inequality with that of last paragraph gives $$$C(a_i, c_i) + C(b_{i-1}, c_{i-1}) + \cdots C(b_1, c_1) \prec C(a_i, d_i) \cdots + C(a_1, d_1)$$$

Thirdly and finally, The last inequality implies that the partition $$$[a_k, d_k], \cdots, [a_{i+1}, d_{i+1}], [a_i, c_i], [b_{i-1}, c_{i-1}], \cdots, [b_1, c_1]$$$ has better total cost than $$$[a_k, d_k], \cdots, [a_1, d_1]$$$, A contradiction. So $$$opt_k(r) \leq opt_{k+1}(r)$$$. □

Remark: By last two facts, $$$opt_{k-1}(r) \leq opt_k(r) \leq opt_k(r+1)$$$. This lets us apply Knuth's optimization to partition dp too.

Monotonicity: The cost function $$$C()$$$ is said to be monotonous iff for $$$a \leq b \leq c \leq d$$$, we have $$$C(b, c) \preceq C(a, d).$$$

Note that monotonicity is not implied by quadrangle inequality. We can come up with cost functions that are QF but not monotonous.

Array Merging DP: Suppose we have to create an array elements of which are initially broken into 1-length arrays $$$[i, i]$$$ (i.e. the $$$i$$$-th entry). At any point, we can merge two subarrays $$$[p, q]$$$ and $$$[q+1, r]$$$ to form the subarray $$$[p, r]$$$, incurring a cost $$$C(p, r)$$$. We want the optimal way to merge the elements from the single subarrays to the full array. Then we can form the definition $$$dp[l][r] = $$$ the optimal cost to merge single subarrays to form the subarray [l, r]. Then
$$$dp[l][l] = C(l, l)$$$
$$$dp[l][r] = C(l, r) + \min \limits_{l \leq m < r} \{ dp[l][m] + dp[m+1][r]\} $$$ ($$$l < r$$$)

Note that even though we define $$$dp[l][l] = C(l, l)$$$, this has no overall effect, since in the end we can subtract all $$$C(i, i)$$$ from $$$dp[1][n]$$$ to negate the contributions. Also, we can redefine the problem to incur cost $$$C(p, q) + C(q+1, r)$$$ when merging $$$[p, q]$$$ and $$$[q+1, r]$$$. The problem is still equivalent, but our DP would have an extra $$$C(1, n)$$$. And, sometimes problems are formulated in terms of splitting the array instead of merging the arrays.

Fact 4) If $$$C()$$$ is QF and monotonous then, $$$dp[][]$$$ is also QF.
Proof: We'll use induction on $$$d-a$$$ of $$$a \leq b\leq c \leq d$$$. If $$$a = b$$$ or $$$c = d$$$ then the inequality $$$dp[a][c] + dp[b][d] \preceq dp[a][d] + dp[b][c]$$$ turns to equality and is true. This handles the base cases. Now suppose, we have fixed $$$a, b, c, d$$$ and have proved the fact for shorter $$$d-a$$$. let $$$a \leq d' < d$$$ be the splitting point of $$$dp[a][d]$$$ i.e. $$$dp[a][d] = C(a, d) + dp[a][d'] + dp[d'+1][d]$$$. There are two cases.

First case, $$$d' < b$$$ or $$$c \leq d'$$$ i.e. the subarray [b, c] is contained in one of the two parts. WLOG $$$c \leq d'$$$ (other case is similar). Then $$$dp[a][d] + dp[b][c] =$$$ $$$C(a, d) + dp[a][d'] + dp[d'+1][d] + dp[b][c] $$$
$$$\succeq C(a, d) + dp[a][c] + dp[b][d'] + dp[d'+1][d]$$$     (Since $$$a \leq b \leq c \leq d'$$$ and inductive hypothesis)
$$$\succeq C(b, d) + dp[a][c] + dp[b][d'] + dp[d'+1][d]$$$     (monotonicity)
$$$\succeq dp[a][c] + dp[b][d]$$$     (definition of $$$dp[b][d]$$$)

Second case, $$$b \leq d' < c$$$ i.e. the splitting point is inside [b, c]. Note that in this case $$$b \neq c$$$. Let us define $$$b \leq c' < c$$$ to be the splitting point of $$$dp[b][c]$$$ I.e. $$$dp[b][c] = C(b, c) + dp[b][c'] + dp[c'+1][c]$$$. WLOG $$$c' \leq d'$$$ (the other case is similar). Then $$$dp[a][d] + dp[b][c] =$$$ $$$C(a, d) + C(b, c) + dp[a][d'] + dp[d'+1][d] + dp[b][c'] + dp[c'+1][c]$$$
$$$\succeq C(a, c) + C(b, d) + dp[a][d'] + dp[d'+1][d] + dp[b][c'] + dp[c'+1][c]$$$    ($$$C()$$$ is QF)
$$$\succeq C(a, c) + C(b, d) + dp[a][c'] + dp[b][d'] + dp[d'+1][d] + dp[c'+1][c]$$$    ($$$ a\leq b \leq c' \leq d'$$$ and inductive hypothesis)
$$$\succeq C(a, c) + dp[a][c'] + dp[c'+1][c] + C(b, d) + dp[b][d'] + dp[d'+1][d]$$$     (rearranging)
$$$\succeq dp[a][c] + dp[b][d]$$$     (definition of $$$dp[a][c]$$$ and $$$dp[b][d]$$$) □

Remark: The monotonicity is actually required for the last fact, it is possible to define $$$C()$$$ such that it is QF, non-monotonous and corresponding $$$dp[][]$$$ is not QF. Also, note that the function $$$f(l, r) = dp[l][r] - C(l, r)$$$ is also QF if C() is QF and monotonous. This fact can't be inferred from the last fact, but we can mimic the proof.

Fact 5) If we define $$$opt(l, r)$$$ = right most $$$m$$$ such that $$$dp[l][r] = C(l, r) + dp[l][m] + dp[m+1][r]$$$ then if $$$C()$$$ is QF and monotonous then $$$opt(l-1, r) \leq opt(l, r) \leq opt(l, r+1)$$$
Proof: If we fix $$$l$$$ then $$$f_l(r) = dp[l][r] - C(l, r)$$$. Then $$$f_l(r)$$$ satisfies the hypothesis for fact 2 (due to fact 4), so $$$opt(l, r) \leq opt(l, r+1)$$$ (the $$$-C(l, r)$$$ have no effect on $$$opt(l, r)$$$). And if we fix $$$r$$$ then $$$g_r(l) = dp[l][r] - C(l, r)$$$. Then $$$g_r(l)$$$ is also QF by remark of fact 2, so $$$opt(l-1, r) \leq opt(l, r)$$$ □

Remark: due to the last fact, we can apply Knuth's optimization in array merging DP.

A final thing to remember is that these facts are not if and only if i.e. the facts can be true for non-QF cost functions too.

Let me know if there are any mistakes.

Consider $$$n$$$ 2d disks, suppose I want to find out the shape of their common area. This shape would be made up of some arcs of the disks. How many arcs can there be at most? My intuition says it should be $$$O(n)$$$, but I can't prove it, any help would be apreciated.

I was happily browsing internet 2 days ago until I saw this problem String Transform. Been stuck at it for two days now, and the best I could come up with is a rough $$$O(n^2)$$$ idea. Would be greatful for some hints.

Hello, Codeforces community.

It is my pleasure to invite you all to the replay contest of National High School Programming Contest 2020 (National Round), which took place some weeks back with the young contestants of Bangladesh as participants. The contest is loosely based on IOI rules and syllabus, with problems having subtask-based scoring system.

The contest will begin at 13:00 UTC on 15 July, 2020 and will run for 5 hours. There will be 12 problems in total.

The contest platform is toph.co, you can register for the contest here.

The problems of the contest were authored and reviewed by curly_braces, fsshakkhor, gola, rebornplusplus, Hasinur_, Hasnaine_, Moshiur_, I_love_ProParThinkNot, ishtupeed, ovis96, SiamH, Shefin_, solaimanope, tanus_era, upobir.

You can use C++11 GCC 7.4, C++14 GCC 8.3, C++17 GCC 9.2, C11 GCC 9.2, PyPy 7.1 (2.7), PyPy 7.1 (3.6), Python 2.7 and Python 3.7 in this contest.

We look forward to your participation and hope that you enjoy the problemset, best of luck in the contest.

As the title says, I wanna generate random graphs that are connected. Now there are some details herr, obviously I want the graph to have $$$n$$$ nodes which is predetermined. Something else that arises in competitive programming is that the graph should have $$$m$$$ edges(also predetermined). Now how does one do that in an intelligent way.

Now I have done a little bit of googling, and it seems there are no 'good' way of getting a perfectly 'random' such graph i.e. pick one uniformly from all connected graphs with n nodes and m edges. But that's okay, approximately random is also good.

One way I have considered is to make a spanning tree first, then add extra edges. But this has horrible bias for certain graphs. For example for $$$n$$$ node $$$n$$$ edge graph, a cycle graph $$$(1-2-3-...-n-1)$$$ is $$$\frac{n}{3}$$$ times more likely than path $$$(1-2-3-4-...-n)$$$ + edge $$$(1-3)$$$. So what process can be a good choice?

One of my favorite algorithms out there is FWHT, but sadly there are not many tutorials about it. So here's a simple attempt by me (feedback is appreciate).

Note: I will be explaining FWHT via DFT/FFT and as such good understanding of theory behind DFT/FFT is required. Also, I won't be going into Hadamard matrices, since I don't know much about them myself.

What is FWHT? Suppose you have two sets $$$ (1, 2, 2) $$$ and $$$(3, 4, 5)$$$ and want to perform all possible xor operations between these two sets, the resulting set being $$$(1, 1, 2, 4, 5, 6, 6, 7, 7)$$$. This is commonly called xor convolution. Naively you'd do this in $$$O(n^2)$$$ time, where $$$n=2^k$$$, $$$k$$$ = maximum number of bits (you maintain a frequency count for each possible value and loop on all possible pair). FWHT let's you do this in $$$O(n\log n)$$$ time via some black magic FFT tricks. We first build the frequency arrays upto $$$n=2^k$$$, apply FWHT to turn them into some mysterious point-value form, perform pointwise multiplication and finally perform inverse FWHT on the resulting array to recover resultant frequency array. But how does this work? And why should you know it?

Let's answer the first question. Though we will need to learn two facts about FFT first:

Fact 1) When we want to multiply $$$(1+2x)$$$ and $$$(3+4x)$$$, we first extend their size to 4, then transfer them to point-value form, then perform pointwise multiplication, and then finally perform inverse transform. Notice the first step, we extend the size because their product is of size 3 and so will require at least 3 distinct $$$(x, y)$$$ point-value pairs (we use 4 cause it's a power of two). What if we didn't do this size extention? You will see that after the last step you get the polynomial $$$(11+10x)$$$ instead of $$$(3+10x+8x^2)$$$. The explanation is that we used quadratic roots of unity $$$1, -1$$$. They don't have any square, instead for them, $$$x^2=1$$$, so the quadratic term "wraps around", contributing to the constant term. The lesson is that if you don't use sufficiently granular roots, the larger powers "wrap around".

Fact 2) We use FFT to multiply monovariable polynomials, what about multivariable polynomials? Everything is same as before, we just need a suitable point value form so that we can recover the polynomial back from it. For a monovariable polynomial of size $$$n$$$, we need $$$n$$$ distinct values (we use roots of unity in FFT for divide and conquer speeed up). In a multivariable polynomial, take $$$P(x, y)$$$ $$$= (1+2x+3y+4xy)$$$ for example, all we need is distinct value sets for each of the variables. Here, x is of degree 1 and y is of degree 1. So we can just use two distinct value sets for them. For example, we can use $$$10, 20$$$ and $$$30, 40$$$ for $$$x$$$ and $$$y$$$ respectively. Then the values $$$P(10, 30), P(10, 40), P(20, 30), P(20, 40)$$$ uniquely define the polynomial $$$P(x, y)$$$. We could've used $$$10, 20$$$ for both variables and that'd also work.
We incorporate this into multivariable FFT by by dividing the polynomials into polynomial of $$$x$$$ grouping by $$$y$$$'s power, like $$$P(x, y) = (1+2x) +y(3+4x) = Q_0(x) + yQ_1(x)$$$. First let's apply the FFT on the $$$Q_i$$$, to get $$$Q_0(1), Q_0(-1), Q_1(1), Q_1(-1)$$$. Then we just note that applying FFT on $$$Q_0(1)+yQ_1(1)$$$ and $$$Q_0(-1)+yQ_1(-1)$$$ will give us $$$P(1,1), P(1, -1)$$$ and $$$P(-1, 1), P(-1, -1)$$$. So the lesson is, multivariable FFT is just normal FFT with some grouping of values.

Now to FWHT

Like it was,previously said, FWHT will convert the frequency arrays to some magical form where performing pointwise multiplication somehow performs xor. Note the similarity with polynomial multiplication here. In polynomial multiplication, $$$ax^i$$$ and $$$bx^j$$$ multiply to merge into $$$abx^{i+j}$$$, we perform this merging for all possible pairs and group them according to $$$x$$$'s power. In FWHT, what we want is for $$$ax^i$$$ and $$$bx^j$$$ to merge into $$$abx^{i \oplus j}$$$ (considering the frequency array as a polynomial). We can do an interesting thing here, break variables into more varibles, utilizing a number's binary form! Let me explain. Suppose in a problem xor convolution requires 3 bits maximum, then terms like $$$ax^3$$$ and $$$bx^5$$$ are brokem into $$$ax_2^0x_1^1x_0^1$$$ and $$$bx_2^1x_1^0x_0^1$$$ (cause 3 is 011 and 5 is 101).
In this new form, there are variables representing each bit. So if we can somehow make multiplication behave well in single bit powers, then xor convolution will become easy! More formally, if we can somehow make it that $$$x_i^0 \cdot x_i^0=x_i^1\cdot x_i^1=x_i^0$$$ and $$$x_i^0 \cdot x_i^1 = x_i^1$$$ then $$$ax_2^0x_1^1x_0^1$$$ and $$$bx_2^1x_1^0x_0^1$$$ will multiply to form $$$abx_2^1x_1^1x_0^0$$$ ($$$3 \oplus 5 = 6$$$). This is last obstacle. But if you notice the equations, you will see that they are basically $$$x_i^p \cdot x_i^q= x_i^{(p+q) \pmod 2}$$$. And now you can see why I had talked so much about FFT with limited domain at the beginning. If we use the numbers $$$1, -1$$$ then as $$$x^2=1$$$, behavior's $$$x_i^p \cdot x_i^q= x_i^{(p+q) \pmod 2}$$$ has been achieved!

Now bringing it all together, we think of the terms $$$ax^i$$$ as being broken upto variables that represent the exponent's binary form. We will multiply this new polynomial using multivariable FFT. And to make sure that they behave like xor-ing, we use the domain $$$1,-1$$$ for each variable.(this wraps the $$$x^2$$$ term back to constants). So FWHT is now just a fancy FFT, huzzah!

Of course we don't need to do actual FFT algorithm for the variables, a polynomial $$$a+bx$$$ can be converted to point value form of $$$(a+b, a-b)$$$ by simply hardcoding it. And for inverting the transform, observe that if $$$u=a+b$$$ and $$$v=a-b$$$ then $$$a=\frac{u+v}{2}$$$ and $$$b=\frac{u-v}{2}$$$. This is why codes for FWHT perform division by 2 in inverting (after doing ordinary FWHT).

I am not providing any code since one can find many good implementations online.

But now to the second question I asked at the beginning, why should you learn it? The answer is simple really, I believe you should understand an algorithm to be able to modify it to specific needs. For example, I set a problem in Codechef's November Long challenge, where you will definitely need to modify the traditional FWHT (along with some more tricks). If you have found more problems requiring modifications on FWHT, please comment so. Also, constructive criticism is appreciated.

EDIT: Forgot to add two things. First of all there are some well known common modifications of FWHT: "Or convolution" and "And convolution". They are the same thing as xor convolution, except you do, 'or' or 'and'. The "or convolution" is almost the same except the behavior we want is $$$x_i^0 \cdot x_i^0 = x_i^0$$$ and $$$x_i^0 \cdot x_i^1 = x_i^1 \cdot x_i^0 = x_i^1 \cdot x_i^1 = x_i^1$$$. For this, obviously $$$1$$$ is a candidate, another illegal cunning candidate is $$$0$$$ (we'll use $$$0^0 = 1$$$). So we use the domain $$$1, 0$$$. "And convolution" is just "Or convolution" on complements, which in terms of implementation is just reversing the logic of "Or convolution".
And finally, I learned this interpretation of FWHT from this helpful blog. But I believe the explanation there is not elaborate. Thus my attempt to write this blog.

What is the best process to see if a problem's idea has already been used somewhere or not? There are so many online judges and contests. Is there any good way to find out? It sucks to propose a problem somewhere and later find out it's an almost copy from some oj.

Sometimes when you are getting WA on a problem, possibly due to missing some corner case or a bug in your code, all you really need are the perfect test cases. Of course you don't know the perfect test cases, so you have to resort to something else. And that something else is checking your code on a bunch of randomly generated testcases. I recently learnt about it and so, am writing this so other noobs like me can get a little help.

First of all, this isn't an unique idea. I myself learnt about it from Errichto's youtube video. You should check it out if you haven't seen it before. So the idea is simple, you will write two new c++ programs, one to generate random test cases. And another to get solution for those test cases, but unlike your actual solution code, this will definitely give the correct answer (perhaps not efficiently/ via brute force). You run the test generator a bunch of times and save the tests in a fine input.in. After each generation, you also solve the problem for the test case in output.out (your original solution) and output2.out (your brute force solution). And then you compare the solutions with a script code of your OS.

The test generation part is easy for a lot of problems, you need to just randomly generate a bunch of data. Sometimes these need to follow a strict restriction but that depends on the problem. For random numbers I use

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
long long random(long long a, long long b){
    return a + rng() % (b - a + 1);
}

Anyways, about the script part, which is the main goal of this blog. For linux script you can just see errichto's video. For windows sctipt, put all three codes TestGenerator.cpp, solution.cpp, brute.cpp in one folder, compile them, and write the following code in checker.bat file.

@echo off
for /l %%x in (1, 1, 100) do (
    TestGenerator > input.in
    solution < input.in > output.out 
    brute < input.in > output2.out
    fc output.out output2.out > diagnostics || exit /b
    echo %%x
)
echo all tests passed

The code basically runs a loop 100 times. Each time it calls TestGenerator.exe and puts the randomly generated output in input.in (the > command redirects stdout to input.in). Then solution.exe and brute.exe are run by redirecting stdin to input.in. The output are put in output.out and output2.out respectively. fc is the command for comparing files, if the files have difference then "exit /b" command stops the batch file. Otherwise if there is no difference, the test case number x will be printed showing you the progress. The advantage of the exit command is that after exiting, you will find the corner test case in input.in and you can debug your code. So all you gotta do is just open cmd in the folder of the files and write checker.bat and run.

I myself don't know that much windows scripting, I learned about it from yeputons's comment in this post. Anyways hope this helps. Forgive any mistakes please.

I have been stuck at this problem for quite a long time now. Can someone please provide a detailed solution. I know the trick to be used is broken profile dp, but after that I am in a dead end. Thanks in advance.