https://www.geeksforgeeks.org/minimum-number-of-increasing-subsequences/

Use multiset in C++ STL

Iterate from a1 to an. For each element a_i color it with the color which has the largest last element smaller than a_i. If there isn't any, color it with a new color.

Greedy works for E. Make another array, X.

In step $$$1$$$, place $$$A_1$$$ in X. In step $$$i$$$, check if $$$X$$$ contains an element that is strictly less than $$$A_i$$$. If there exists such an element in $$$X$$$, replace the first such element in $$$X$$$ with $$$A_i$$$ else append $$$A_i$$$ to $$$X$$$.

The answer will be the final size of $$$X$$$.

Note that the array $$$X$$$ will always remain sorted and hence you can use binary search in each step, giving a final time complexity of $$$O(n \log n)$$$.

You can visualise it as stacking number of discs on top of each other, the array $$$X$$$ contains only the top of each stack, the "representative" element. Each new stack corresponds to a new colour and we can add an element to a stack only if it is larger than every element in that stack. However since the representative element is the largest element of the stack you just need to check if the element to be added is larger than the representative element of the stack.

The problem gets reduced to finding longest non increasing sub-sequence of the given sequence. The reason being Dilworth's Theorem

Never

Answer is never -1.

The answer always exist.

There is always a good set of choice.

Never.

If $$$x_i$$$ is the number of balls in the box $$$i$$$. The problem is equivalent to finding equivalent to solving a system of $$$n$$$ linear equations in $$$x_1, x_2, \dots, x_n$$$ modulo $$$2$$$.

The matrix of this sysetm of linear equation was upper triangular and all the diagonal elements were non-zero and hence it will always have a solution. The proof of this is the algorithm used to solve the problem. You can find $$$x_i$$$ by simply setting

Then simply iterate from bottom to top, first find $$$x_n$$$, then $$$x_{n - 1}$$$, then $$$x_[n - 2}$$$ and so on... This is known as back substitution.

The time complexity will be

For any with box you always have the option to make the total ball in its multiples odd or even depending on whether you fill the with box with ball or not. So answer can never be -1

One solution is to OEIS : http://oeis.org/A062869/b062869.txt
The other solution is to use DP.

and D to E ?

For D, you can start from N and go backwards till 1, at each stage check the parity of all multiples of the current number which are <=N, and accordingly set or don't set the bit for the current number depending on Ai.

in standings then click on multiplying glass near the name

Could you tell me your DP solution please? I haven't any idea about it.

All you need to do is find the largest and second largest numbers. The second largest number can be equal to the largest number. Thus if the current number is equal to the largest number, then print the second largest number; else, print the largest number.

Here is my code: https://atcoder.jp/contests/abc134/submissions/6467493

just bcoz ur approach is wrong. why r u asking the wrong approach to be a correct.

Look at this 12 1 1 2 2 3 3 3 3 2 2 1 1 Answer:8 Output:9 Expect 8 find 9

The editorial in japanese says that we should assume the problem as pairing task.
The state of dynamic can be

• i: i-th pair we are looking at (<=n)
• j: number of pairs you skipped and kept unconnected (<=n)
• k: determined oddness till i-th operation (<=n^2)

then we can update the state like dp[i+1][j][k+j] = dp[i][j][k] in O(n^4).
My code here https://atcoder.jp/contests/abc134/submissions/6504932

Editorial is out: here
You can find the editorials on Twitter

thanks man.

This one helps a lot, Thanks! it's so cool to reshape it into another equivalent solvable one. after the reshape, the transition of DP becomes comparatively clearer.