We will hold AtCoder Regular Contest 159.

- Contest URL: https://atcoder.jp/contests/arc159
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20230408T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: m_99
- Tester: maspy, Nyaan
- Rated range: — 2799

The point values will be 300-400-500-600-900-900.

We are looking forward to your participation!

Scoring distribution looks friendly! I'll surely participate. GLHF!

Nice round! I can get a large positive delta this time.

Wrote a strange solution of B and it passed quickly. Idk whether it's right or weak data.

Ok. It's $$$\mathcal O(\sqrt N \log N)$$$.

C++20 support when

2032

Good luck! Scoring distribution DOES look friendly! Wish everyone's rating increases!

Great problem D, awesome generalization of the classic LIS (and hence a very natural problem statement).

Got TLE again and again on B problem (36/41). This 2sec time limit sucks :(

Can someone tell me how I can optimize this further..

My Code (B-problem)Brute force only have no idea to pass this problem.

can anyone explain how to solve B? The editorial is slightly confusing.

My code is giving TLE after some test cases, could you please look once and optimize it?

codeyou are manually performing the operations, ofcourse it will give TLE

Let $$$g = \text{gcd}(a, b)$$$. Suppose $$$a < b$$$.

For some reason I still can't understand the idea behind B? I don't get why you can take a, b and perform a//g and b//g, when g != 1 for starters. How can that be the same thing?

Try to simulate operations starting from $$$(a, b)$$$ and from $$$(a/g, b/g)$$$. You will notice that all the partial results in the first case are the same as in the second case, multiplied by $$$g$$$ (and it should be easy to prove). So, you will reach $$$0$$$ at the same moment.

Another round with 3200perf+unr_reg

Why my D code always Runtime Error and Wrong Answer? Can anyone help me? Code Link

Actually, we can find the minimum number of operations required for problem C (code). Though it was much harder to implement than simply constructing one, and I couldn't manage to finish it during contest time :(

Do you mind explaining the idea?

First we iterate through all $$$s$$$, and check whether we can make all elements equal using exactly $$$s$$$ steps. We can easily get rid of the case where the sum doesn't fit and some other trivial cases, so now we try to find a way to make every element $$$V$$$ in $$$s$$$ steps.

Note that if we construct a $$$n\times n$$$ matrix $$$M$$$ where $$$0\le m_{i,j}\le s$$$ denotes the number of permutations where $$$p_i=j$$$, if the matrix satisfy the constraint that every row and every column sum up to $$$s$$$, we can always find $$$s$$$ permutations that corresponds to this matrix. This can be done using bipartite matching in $$$O(sn\sqrt n)$$$ time, which is obviously enough since $$$s\le 10^4$$$. Thus we try to find this matrix with the additional condition that for all $$$i$$$ , $$$\sum_{j=1}^n j\times m_{i,j}=V-a_i$$$.

Instead of the original matrix, we try to construct the suffix sum matrix $$$A$$$, such that $$$A_{i,j}=\sum_{k=j}^n m_{i,j}$$$, now we re-write the constraints on $$$A$$$: row sum equals $$$V-a_i$$$, column sum equals $$$(n-i+1)s$$$, $$$A_{i,1}=s$$$, and $$$A_{i,j}\ge A_{i,j+1}$$$.

Since the constraint on row sum is annoying, we first construct any such matrix without this condition. This can be done easily by greedy or whatever method. Then we try to adjust this matrix so that every row satisfy the constraint without breaking the other ones. Let $$$b_i=V-a_i-\sum_{j=1}^n A_{i,j}$$$, then if all $$$b_i=0$$$, we are finished. Otherwise, WLOG, suppose $$$b_1$$$ is the smallest one, then we need to move some other elements to this row to make this row good. To do this, we simply iterate through all $$$i$$$ such that $$$b_i\ge 0$$$, and for every $$$j$$$, we can calculate the maximum value that can be subtracted from $$$A_{i,j}$$$ and can be added to $$$A_{1,j}$$$ without violating other constraints (we can only care about whether $$$A_{i,j}\ge A_{i,j+1}$$$ here because the other conditions are always ok). We keep doing this until all $$$b_i=0$$$, in which case we have constructed the matrix succesfully, or we can't make the smallest value bigger, which results in a failure.

Now we analyse the complexity. Let $$$v$$$ be the number of $$$i,j$$$ such that $$$A_{i,j}\ne A_{i,j+1}$$$. Since when we move every time, we make at least one $$$A_{i,j}=A_{i,j+1}$$$ or we make at least one $$$b_i=0$$$. Though it is possible that previously $$$A_{i,j}=A_{i,j+1}$$$, and later we make $$$A_{i,j+1}=A_{i,j+2}$$$, when we iterate through all $$$j$$$, $$$v$$$ decreases by at least $$$1$$$ every time we move from an $$$i$$$, and $$$v$$$ never increases. Since $$$v$$$ is at most $$$O(n^2)$$$, and it takes $$$O(n)$$$ time to move from $$$i$$$, the complexity for checking is $$$O(n^3)$$$. Since the answer is always less than $$$O(n^2)$$$, the total complexity is $$$O(n^5)$$$. However, we can never actually reach this upper bound since 1. the minimum number of operations is far fewer than $$$n^2$$$, and 2. the number of operations needed to adjust the matrix is far fewer than $$$n^3$$$ since it is just a theoretical bound.

Note: if it's possible in $$$s$$$ steps, it's also possible in $$$s+2$$$ steps. So, you can binary search odd and even $$$s$$$, and the complexity becomes $$$O(n^3 \log n)$$$.

Can anyone explain the O(n) solution of the F problem (official editorial)? Even though I've gotten AC, I still can't understand the official editorial.

For D what should be the solution for this input?

1 1, 2 7, 4 7, 10 15

An Accepted solution return the result = 11. But I think the solution is 13 is it not? Writing this out I get X = 1, 2, 3, 4, 5, 6, 7, 4, 5, 6, 7, 10, 11, 12, 13, 14, 15 It seems plain to me that I would take 1,2,3,4,5,6,7,10,11,12,13,14,15 as the longest strictly increasing subsequence?

Maybe I found a missing testcase actually cause If I try

1 1, 2 7, 4 8, 10 15

The same accepted solution gives 14, which is the answer I would expect for this.

This is the solution that seems to give these, It was written from someone else I was just learning it, and realized it didn't make sense on a test input I came up with.