Well done!

well……it is very common that no one solve a Chinse Round Div1E…… :D

For example 3 5 8 2

Change 5 to 0, or some negative integers ...

negative numbers are still integers.

You can change 5 to 0.

Problem statement says that the replaced number can be any integer not positive integer.

So, this sequence can be transformed into 0 1 2 and thus the answer is 3.

I didn't code, but I came up with that.

I solved it in the way the same as the editorial. my submission..7085786 and I have found use Segment Tree to maintain Matrix can get ac too. for example:7084920

Another way to solve Div1 C would be to use a sparse table. Let dp[i][l] be the sum of fibonacci numbers from range i to i+(2^l)-1. This can be precalculated in nlog(n). Sum for any range l-r can now be calculated in log(n).

This is followed by segmented tree with lazy propagataion for each query. Time complexity for each test case is q*log(n)^2.

This is the simplest/easiest solution I could think of.

Btw:

We can do this without matrix multiplication:

1) F(a, b, k) = a * f_k - 2 + b * f_k - 1 -- k-th element of general Fibonacii sequences starting with a, b, where f_i — i-th Fibonacci numbers (starting from 1, 1).

2) sum of first k members of general Fibonacci sequence F_i equals to F_k + 2 - F₂.

So we only need to precalculate Fibonacci numbers.

Can you explain, please, solution with lazy segment tree? I can't understand how we should recalculate a[l] .. a[r] with O(log(n)) time, I know how to lazy add a one number to every element in segment with O(log(n)), but i can't understand how to add different numbers to elements in segment with O(log(n)).

why can't we just keep the cumulative sum modulo in the fibonacci array ?

I mean like Ai = (Ai-1+Ai-2)mod p . and then each query we add (Ar-Al+1)%p to the segment tree. ?

Xellos You know what you are simply awesome. Your code , your explanation everything. you are an asset to this community... Thanks for your life saving short and effective editorial for this awesome problem.

Is it possible to solve it using square-root decomposition? I tried it and it is giving memory limit exceed as it should. The space complexity of square-root decomposition is O(nsqrt(n)). Can we improve on it and solve using this method?

Incorrect, deleted.

+1 for Proofathon

In div. 1 C so F_n should be 276601605 * (691504013ⁿ - 308495997ⁿ).

Thank you author of this editorial for making that mistake :)! I just won 20zł (zł is currency in Poland) with Marcin_smu thanks to that.

He asked me which one of those two possible values of he should choose (of course if there is at least one then there are exactly two of them). I replied that it doesn't matter, because only property of mod 10⁹ + 9 is that its square is 5. He replied that if we will take second value instead of first, we will get negated sequence and offered me a bet. I looked at that formula in editorial and it convinced me even more, because I noticed that it is very probable that he thought like that because of that typo in editorial and agreed to the bet. And it was exactly as I suspected :D.

The effect of p is constant on all rows and columns ... It just depends on how many row operations you make out of the k operations.

u can do this using dynamic programming.
if u want the exact implementation, u can see my solution 7077771.

First of all , you know you can change only one number. So why not try each number for 1 to n and see if I can change this what is the value.

Now suppose you are at index i. Now the thing is , you need to know how far the decreasing goes at the left of i. for example , 12 2 3 5 1 9 , you see for i= 4 , we get 5,3,2 that is 3 length, Similarly you have to catch at right which is only 9. And now to see if you can change the value. the difference between i-1 and i+1 i.e 5 and 9 is 4 , so you can insert a number such as 6,7 or 8 there and make the sequence increasing . Now the length of the sequence is (2,3,5)->l[i] + (9)->r[i] + 1. so you take maximum of all this and you get the ans.

Now , how to calculate l[i] and r[i] ? you see , you iterate through 1 to n , now for each i , if A[i] > A[i-1] , we can increase the sequence, so A[i] = A[i-1]+1. else we start a new sequence and A[i] = 1. similar for r[i] but iterate from n to 1. Hope it clears.

We can consider the rows and columns separated. It's easy to get the largest value of choosing k rows and the largest value of choosing k columns. Then consider if we choose a row after choosing a columns. The answer should be subtract by a * p. Then for a operation sequence of choosing rows for i times and columns for k - i times. If we swap two operations, the total number which should be subtract doesn't change. So we can calculate the total number should be subtract is i * (k - i) * p. So we can enumerate i and solve this problem.

I'm sorry for our mistake. T^T

I wonder why there is no rejudge? It's not an ACM contest, so it didn't actually change anything for these guys.

The number of the trap rooms is no more than 100.

In this case both strings are valid. Note that w_b = w_c = 2.

You know, resizing is possible if you put the image in html tags.

But these formulas are worthy even of nope.avi

I haven't read that, but I will probably enjoy that problem, but sometimes I wonder why they put such tasks in contest which lasts 2 hours. It is clearly wasting interesting problem, because nobody will be even close to solving it :(.

hahaha) that's my reaction)

Surprisingly enough, the solution is very easy to code. Maybe one could derive these formulas in an hour or two, but there is no way one could have that much time left after solving the 4 previous problems.

Welcome to China.

Firstly:

1) Wolframalpha

or

2) Bruteforce (note that program finding that number doesn't have to output answer in 2s).

Secondly:

Hardcode

Доказывать нечего, если поверить, что порядок действий не имеет значения, и что горионтальные и вертикальные ходы практически независимы.

Порядок действий не имеет значения. Посмотрим на клетку матрицы. Пусть ее "трогали" К раз. Тогда она всегда даст к ответу a[i][j] * K - (K - 1) * P.

Горизонтальные и вертикальные ходы независимы. Пусть мы решили сделать К горизонтальных ходов. Тогда любой вертикальный ход будет иметь ровно К точек пересечения с любыми горизонтальными ходами. Вспомнив рассуждение про клеточку из преыдущего пункта, понимаем, что эту сумму можно вынести, решить без нее, а потом добавить.

In order to reduce the problem to a sum of geometric series, as apparently it makes it easier to solve. My solution doesn't use that either, here's roughly what I did:

• We need to be able to find the sum S_k = A₁... A_k (the answer to the second query is S_r - S_l - 1)

• First, we precompute partial sums for the initial array at the beginning

• Then, we need to include the Fibonacci segments that fully lie within range (1, k) — this is done with a simple segment tree once we have precomputed FS_k = F₁... F_k

• Now, we need to include segments that partially lie within our range. For this, we extend the segments to the left until the beginning of our array (Fibonacci sequence can be extended to the left using F_k - 1 = F_k + 1 - F_k), and use two segment trees to find the sum of the elements that appear at the first and second positions in our array. Since Fibonacci sequences are additive (assuming F^a, b is a sequence that begins with a, b, we have F^a, b + F^c, d = F^{a + c, b + d}), we now need to find the sum of the first k elements of a sequence beginning with those two numbers, which can be done by precomputing coefficients for the first two elements. Don't forget to subtract the sum of the negative Fibonacci elements from the resulting sequence (these values can be included in the first interval tree).

Your solution is greedy — it is not optimal to always choose the row/column with the largest sum.

The correct solution splits the problem into two parts. First, we try to solve it for different values of K using only rows, then only columns (both can be done greedily, like you suggested), and save the results.

Then we choose all values of R from 0 to K and try to combine the solutions that use R rows and K - R columns. The key observation is that the relative order of rows and columns doesn't matter — in any case, for each row-column pair whichever comes first will reduce the result of the other one by exactly p, so the answer will be AnsRow[R] + AnsCol[K-R] + R * (K - R) * p.

It is OK to take X best row moves and Y best column moves using greedy approach, if you have fixed X and Y. But for given K greedy approach may give not the best partition of K into X and Y. Here is counterexample:

4 4 3 1
5 5 5 1
5 5 5 1
5 5 5 1
0 0 2 0

Author's solution calculates 1, 2, 3,... k best moves on rows/columns, and then try all possibilities: do only k row moves, do k-1 row moves and 1 column move, do k-2 row moves and 2 column moves and so on.

Thank you both! The test case explained very well what I was doing wrong. I finally got accepted. :)

First, we need to reduce the graph. For each room A and a trap room B calculate the chance that the next trap room after A will be B. For a given B, we can make a list of equations for those values and solve them via Gauss elimination. For example, in the example case, let's find the probability that the room #3 will be next. P₃(1) = P₃(2), since there is nowhere else to go from room 1, and neither of those rooms are trapped. P₃(2) = 2 / 3P₃(1) + 1 / 3, because we can either go back to room 1 or forward to room 3. P₃(3) = 1 / 2P₃(2) + 1 / 2P₃(4). P₃(4) = 1 / 2. P₃(5) = P₃(4).

Once we have calculated these values, we can construct a new graph that contains only the first room and all trap rooms, and use the computed probabilities as the edges in the new graph. Now we need to calculate the chance that we will end up in room N after K-1 moves. This can be done with matrix multiplication: let V be a vector such that V_i is the probability that we are currently in room i, and let P be the matrix of probabilities we computed previously. Then, P·V is a vector of new probabilities after one step. Which means that to find the answer, we need to calculate P^k - 1·V. Raising a matrix to power of k can be done in , where T is the number of trap rooms, which is not higher than 100 (plus one).

The last complication is that Gauss elimination is O(N³), and we need to run it up to 100 times, which is too slow. This is solved by noticing that the matrix on the left hand side is always the same, and only the right hand side values change. So we can use Gauss elimination once to find the inverse of that matrix, and then use it to find the probabilities for every right hand side vector in O(N²).

I_love_Tanya_Romanova explains why this approach does not give the optimal result some comments above yours. Also, he posted a small counterexample.

Why we cant change 1 to 1000000001 ? In description we can change to any integer we want, not neccessarily <= 10^9 (although the constraint of input is between 1 and 10^9). Am i wrong?

Sequence may be 1 2 42 43 4

really?

yes you can, using general Fibonacii sequences starting with a,b as mention in this comment

and this is my implementation 17332378

Did you get any solution for this issue?

Just use BS = 700.

if we ignore the time complexity.... the greedy approach at every step gives us the optimal solution or not.