Codeforces Round #FF(255) Editorial

#	User	Rating
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

The editorial is updated.

447A - DZY Loves Hash

We just need an array to store the numbers inserted and check whether a conflict happens. It's easy.

Firstly the optimal way is to insert letter with maximal w_i. Let $\text{[math]}$ {w_i}. If we insert this character into the k'th position, the extra value we could get is equal to $\text{[math]}$ . Because of w_{s_i} ≤ num, when k = n + 1, we can get the largest extra value.

So if we insert the k letters at the end of S, we will get the largest possible value.

446A - DZY Loves Sequences

We can first calculate l_i for each 1 ≤ i ≤ n, satisfying a_{i - l_i + 1} < a_{i - l_i + 2} < ... < a_i, which l_i is maximal.

Then calculate r_i, satisfying a_i < a_i + 1 < ... < a_{i + r_i - 1}, which r_i is also maximal.

Update the answer $\text{[math]}$ , when a_i - 1 + 1 < a_i + 1.

It's easy to solve this problem in O(n).

446B - DZY Loves Modification

If p = 0, apperently the best choice is choosing the row or column which can give greatest pleasure value each time.

Ignore p first,then we can get a greatest number ans. Then if we choose rows for i times, choose columns for k - i times, ans should subtract (k - i) × i × p.

So we could enumerate i form 0 to k and calculate ans_i - (k - i) * i * p each time, max {ans_i - (k - i) * i * p} is the maximum possible pleasure value DZY could get.

Let a_i be the maximum pleasure value we can get after choosing i rows and b_i be the maximum pleasure value we can get after choosing i columns. Then ans_i = a_i + b_k - i. We can use two priority queues to calculate a_i and b_i quickly.

446C - DZY Loves Fibonacci Numbers

As we know, $\text{[math]}$

Fortunately, we find that $\text{[math]}$

So, $\text{[math]}$

With multiplicative inverse, we find,

$\text{[math]}$

Now, $\text{[math]}$

As you see, we can just maintain the sum of a Geometric progression $\text{[math]}$

This is a simple problem which can be solved with segment tree in $\text{[math]}$ .

446D - DZY Loves Games

Define important room as the trap room. Let w(u, v) be equal to the probability that DZY starts at u (u is a important room or u=1) and v is the next important room DZY arrived. For each u, we can calculate w(u, v) in O(n³) by gauss elimination.

Let A_i be equal to the i'th important room DZY arrived. So A_k - 1 = n, specially A₀ = 1. Let ans be the probability for DZY to open the bonus round. Easily we can know $\text{[math]}$ . So we can calculate ans in $\text{[math]}$ (a is equal to the number of important rooms) by matrix multiplication.

So we can solve the problem in $\text{[math]}$ . we should optimize this algorithm.

We can find that each time we do gauss elimination, the variable matrix is unchanged. So we can do gauss elimination once to do preprocessing in O(n³). Then for each time calculating w(u, v), the only thing to do is substitute the constants. In this way we can calculate w(u, v) in O(n³).

In this way, we can solve this problem in $\text{[math]}$

446E - DZY Loves Bridges

Let n = 2^m. For convenience, we use indices 0, 1, ..., n - 1 here instead of 1, 2, ..., n, so we define a₀ = a_n.

Obviously this problem requires matrix multiplication. We define row vector $\text{[math]}$ , and matrix $\text{[math]}$ , where b_ii = 1, $\text{[math]}$ . The answer is row vector $\text{[math]}$ .

Since n can be up to 3 × 10⁷, we need a more efficient way to calculate. Let $\text{[math]}$ denote the matrix $\text{[math]}$ when m = k. For example, $\text{[math]}$

Define $\text{[math]}$ , then we can easily find that

$\text{[math]}$

where $\text{[math]}$ denotes the identity matrix.

For an n × n matrix $\text{[math]}$ and a constant r, we can prove by induction that $\text{[math]}$

Let α₁, α₂ be two 1 × n vectors, then we have $\text{[math]}$

This result seems useful. Suppose we want to find $\text{[math]}$ , where $\text{[math]}$ , we have

$\text{[math]}$ so we just need to find $\text{[math]}$ , which is a self-similar problem. By recursion, it can be solved in time T(n) = T(n / 2) + O(n) = O(n).

int i=0,j=1,dec=0,ans=1; while(j<n) { if(arr[j]>arr[j-1]) { ans=max(ans,j-i+1); j++; } else { dec++; if(dec>1) { i++; dec--; } else ans=max(ans,j-i+1); j++; } } cout<<ans<<endl;

Comments (138)

Show archived | Write comment?

yash.15296

10 years ago, # |

I think I found this editorial first!

→ Reply

Thomas_Ahle

10 years ago, # ^ |

Well done!

foreseeable

wow so fast Editorial.. such a hard round..

JuanMata

-7

nobody solved Div-1 E. did u have to go and make the explanation so scary? :D

Shana

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

anirudhalampally

I have a small query in 446A — DZY Loves Sequences question.

For the input :

3 5 1 2

The output should be 2 because the value should be strictly > 1 right ?

But in the test cases, it is given 3. Why?

hhsaffar

For example 3 5 8 2

Codephile

← Rev. 2 →

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

k790alex

negative numbers are still integers.

You can change 5 to 0.

J-C

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.

sandy999

9 years ago, # ^ |

Replaced number is ANY integer, ah! No wonder I was getting WA repeatedly.

I looked at the range of inputted integers (1<=ai<=10^9) and assumed that the replaced integer falls in that range as well.

.o.

+51

Is there anybody who solved Div1C in that way?

Swistakk

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

+13

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

sgtlaugh

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.

did you solve it in that way? I would like to see your code.

its better to build an array of fibonacci sum from 1 to i, O(N) memory instead of O(N logN).

I implemented a segment tree with lazy updates but I always got TLE. (7087584

Sorry I misunderstood the problem which messed up my thinking. Forget about what I said.

Xellos

No, your solution should work. It's just that you don't need a sparse table (but you can work with it) and the hard part of the solution is the lazy propagated segment tree.

Xellos, can you tell me why my solution is too slow?

Instead of trying to decipher a Java code (it's an alien language to me :D), I'd take a guess that your lazy updates aren't implemented well and actually take O(interval size) and not O(1) for updating a vertex containing that interval. Your code takes 3 seconds on N = 10⁴, from which you can guess that something's extremely wrong.

I gonna check that, my implementatigor AC in spoj (Horrible queries) but I may made a mistake while editing it.

thanks.

Or weak cases in that problem. Or something. Anyway, if it takes 4 seconds on 10x smaller inputs than max, it can't be ok asymptotically.

+54

Uh... the editorial for C is way too much magic. There are simpler solutions, if we just use general Fibonacii sequences (starting with a, b). Then, using matrix multiplication, we can compute the coefficients c_a, c_b of the k-th element of this sequence (ac_a + bc_b) and s_a, s_b of the sum of the first k elements (as_a + bs_b). The rest is just a standard lazy-loading interval tree (e.g. segment tree with lazy propagation), where we just remember that we want to add to the whole interval of vertex v sequences with sums starting with v.a, v.b, the sum in this interval, and are able to compute the changes in sum and what the k-th elements of this sequence will be.

Code: 7092191. Works comfortably in less than a second.

cmd

+49

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.

+22

Yeah, I know. Still, I think using matrix multiplication is kind of closer to a programmer's mindset and writing it takes about as much time as checking if you've got the exactly correct formulas (which I didn't, that's why I didn't even bother writing them :D).

tau0

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)).

+14

Check my code for exact formulas; the idea is that if we add to the same interval a Fibonacci sequence starting with a₁, b₁ and another sequence starting with a₂, b₂, then it's the same as adding a sequence starting with a₁ + a₂, b₁ + b₂, and that's the same as adding (for a matrix A, whose powers I compute as pw[]) the bottom element of $\text{[math]}$ (it's a vector, not a binomial coefficient) to the k-th element of this interval. This also allows us to know what this sequence looks like from the c-th (not 0-th) element: it's just a Fibonacci sequence starting with $\text{[math]}$ . Using this property, we can convert a sequence (given by its first 2 elements) that's added to an interval into 2 sequences (also given by first 2 elements) that are added to 2 subintervals, which forms the basis of lazy propagation. Using precalculated $\text{[math]}$ , we can easily calculate the sum of any Fibonacci sequence just based on its first 2 elements.

Thanks a lot. I think that i understood your solution :)

qw4990

Amazing solution, thanks a lot :P

jibon_ebong_shomoy

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. ?

I'm not sure what you mean, and I think if you didn't just write "add [constant] to the segment tree", I'd understand it better. Maybe your idea is the same as what I wrote, just with Fibonacci numbers instead of matrices (whose elements are Fibonacci numbers, anyway).

No , I meant that I generate all the Fibonacci numbers modulo from 1 to 3000005. so , I have got this Fibonacci array fib , where fib[i] = (fib[i-1]+fib[i-2]) % 100000009. now I create another array cumulative Fibonacci , cumfib , where cumfib[i] = (cumfib[i-1] + fib[i])%1000009

Now , when we got a query l,r on the segment tree for values l...r , we just add cumfib[r]-cumfib[l] to the interval l...r of the tree. Will this work ?

You're wrong. Suppose you had an array of size 2 and an "add" query on the interval [1,2]. Your cumfib[] should be 2 (as F₁ + F₂), so you'd add 2 to the interval [1,2]. But if you then had to find the sum from interval [1,1], how would you do that? You only know that you added 2 to [1,2], but not what sequences formed it.

You're probably missing the whole concept of segment trees with interval updates and queries.

yeah , I understand now... thanks! but can you please explain your soln a bit more? I mean what are a,b and ca,cb ?

a, b are the first and second element of the sequence and c_a, c_b, s_a, s_b are just some coefficients (obtained by matrix multiplication, I don't want to just rewrite the formulas from my code, but you can try yourself that they produce the desired results... or just google something about how Fibonacci numbers work with matrix multiplication). There are 2 main and well known concepts here: using matrices to compute Fibonacci numbers and lazy-loading interval tree (lazy propagation segment tree), the rest is mostly about rewriting the formulas into the code correctly.

My solution here http://codeforces.net/contest/446/submission/7094142 is without matrix operations. It just uses standard identities for summing fibonacci numbers.

Deleted, wrong place (a few comments too high) and time (3 at night) to post...

ds_95

Hi Xellos, I think this approach might work if we propagate to children more carefully!! I tried my best to implement but ,stuck with a bug Please take a look at my submission here:14316365

ivplay

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.

yeah ... really big thanks from me too.... Just awesome ..

mayank_ag

5 years ago, # ^ |

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?

adnan_toky

3 years ago, # ^ |

+10

Solved it using square root decomposition with $$$O(n\sqrt{n})$$$ time and $$$O(n)$$$ memory. The submission is here, 155232894

The simpler approach for Div. 1 C using square root decomposition:

Let's divide the array into $$$\sqrt{n}$$$ smaller blocks of size $$$\sqrt{n}$$$. For each query, we will iterate through the list of the blocks. Let $$$sum[i]$$$ be the sum of elements of the $$$i$$$-th block.

For the first type of query,

If the $$$i$$$-th block is completely outside of the update range, just skip it.
If the $$$i$$$-th block is completely inside the update range and we need to add $$$x$$$-th and $$$y$$$-th fibonacci numbers with the first and the last element of the block respectively, update the value of $$$sum[i]$$$ with the sum of $$$x$$$-th to $$$y$$$-th fibonacci numbers (precalculate the prefix fibonacci sum). Store the value which will be added with the first two elements of the block (it will be used later).
If the $$$i$$$-th block partially intersects with the update range (at most two such blocks exist of this type), manually update each element of the block (which is inside the update range) and the value of $$$sum[i]$$$.

For the second type of query,

If the $$$i$$$-th block is completely outside of the query range, just skip it.
If the $$$i$$$-th block is completely inside the query range, add $$$sum[i]$$$ with the answer.
If the $$$i$$$-th block partially intersects with the update range, first update each value of the block iterating over the block (use the stored value which will be added with the first two elements of the block to update the next values). Then manually add the value of each element that is inside the query range.

Complexity $$$O(q\sqrt{n})$$$ for time & $$$O(n)$$$ for space.

My submission: 155232894

+24

"As you see, we can just maintain the sum of a Geometric progression .

This is a simple problem which can be solved with segment tree in O(q log n)."

Hm, I came up with that reduction and with maintaining the sum of a geometric progression, but I definitely won't call that maintaining easy. Btw that solution exists, because square root of 5 mod 1e9 + 9 exists, but it can still be done by some standard operations on matrices (assuming we already know how to maintain sum of a geo progression) even if 5 is a quadratic nonresidue.

Incorrect, deleted.

Wasn't that comment meant to be a reply to Xellos' comment above?

Yeah, may be :)

mbrc

-33

This was nice (AC before System Test) :

garakchy

+1 for Proofathon

kmjp

+20

In Div1C, Fn=sqrt(5)/5*(((1+sqrt(5))/2)^n - (((1-sqrt(5))/2)^n)) so Fn should be 276601605*(691504013^n - 308495997^n).

adamant

In div. 1 C $\text{[math]}$ so F_n should be 276601605 * (691504013ⁿ - 308495997ⁿ).

Thank you for decoration. I did not find how to use tex markup here.

+11

You write math the same way you'd do it in any TeX document: put the formulas in $.

Put your formula inside the $$

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 $\text{[math]}$ 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 $\text{[math]}$ 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.

I_love_Hoang_Yen

That was a bit confusing @@. So we can choose both values of sqrt(5) ?

Yyy, yes, I just explained that. We don't need anywhere exact value of $\text{[math]}$ . It's not important that its decimal representation is sth like 2.2 and it's not important that mod 10⁹ + 9 it can be 383(...) but one thing which is important is that its square is 5.

About the answer to 446B, can somebody please explain this to me:

"Ignore p first,then we can get a greatest number ans. Then if we choose rows for i times, choose columns for k - i times, ans should subtract (k - i) × i × p."

What does it mean to ignore p first? Isn't it important what rows and columns we are choosing? Why?

TsunamiNoLetGo

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.

__builtin__wolfy

For Div2. C. how can we calculate L_i and R_i for all i in linear time?

-9

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

Thanks!

Equilibrist

How can we came up with such solution of Div 2C problem? What is first step for such problems? Maybe that is easy but it seems tricky magic for me

Can someone explain this issue, please?

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.

Thank you. It's clear right now. I used the similar idea in my solution but I used one iteration through 1 to n.

← Rev. 4 →

Can someone please explain DIV2-D DZY loves modification? The editorial is so short and brief I can't find a clue what's going on.

jiry_2

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_love_Tanya_Romanova

+42

Test cases for Div1B/Div2D are weak.

Solution 7093794 uses int instead of long long for row/column sums (in order to fit into TL with O(k * (n + m))).

For test

1000 1 987900 100
0
0
...
0
0

it gives answer 8418438592 because of overflow. It is clearly wrong, because every operation on such array will give <=0 additional happines (and correct answer for this test is -48747930000).

upd. problem statement says ar[i][j]>0, my first example is not valid. We may change matrix of 0's to matrix of 1's, and for this test we'll have 9406338592 instead of -48746942100.

upd2. i've read some random solutions from contest. gchebanov, flashmt have this bug (and most probably few others).

I'm sorry for our mistake. T^T

Rubanenko

+32

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

riadwaw

D: Am I tight that if all (except the first one) rooms are with traps than solution works in just O(n^3 log k)? My O(n^3 log k) was too slow:(

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

Oh, I didn't notice that:(, sorry

Okay

Hey. I misunderstood condition second task decided to try the greedy algorithm tried passed. I have a question for the problem in Example abc 3 1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 if the answer to take letters, could receive only «abcbbc»??? or could even «abcbbb»? thanks for the earlier

sergioRG

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

+103

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

But these formulas are worthy even of nope.avi

+16

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 :(.

ilidar

hahaha) that's my reaction)

Rivx

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.

rpeng

Welcome to China.

ashu1461

Fortunately, we find that 383008016² = 5(mod10⁹ + 9)

How did we find this number ?

Firstly:

1) Wolframalpha

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

Secondly:

Hardcode

IvayloS

Why do we need this observation for Fibonacci problem? i simply precomputed first 300 000 Fibonacci numbers in an array.

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).

But when we have fixed size static values we don't need this optimization. I used an array with the prefix sums of the Fibonacci numbers up to 300010 and I can find the sum of any interval in constant time.

I did not finish my problem because I spend too long trying to challenge, but I believe it should work. I used bucketing in 548 buckets of size 548. Each query would only perform in the order of 548 operations which should be fast enough I think,

As I said, it is definitely possible to solve the problem directly, its just a different solution from the one mentioned in the editorial.

I'm not sure what you do with buckets — for buckets fully covered by the "add" query, I suppose you simply maintain the first two elements, and for end buckets you add the values directly to the original array?

Exactly.

I just tried writing a solution with buckets, I'm getting TLE on the maximum test (300000 N/M and all queries span almost the entire array takes about 5-6 seconds). My submission is 7103071, I don't see how it can be improved without using interval trees.

Nice :-) My draft was way longer. 5-6 seconds it's motivating because it seems it can be optimized enough. I would try to avoid ',' operator.

Its great for squeezing several small operations inside an if/for without using {}, which sometimes makes it more readable (though with the way I used it here it probably doesn't really help with readability). Problem is, the small optimizations like not using division inside the loop are probably done by the compiler anyway. Changing BUCKET to 512 should auto-optimize the modulo with & but it doesn't make it much faster.

← Rev. 6 →

You may try some other solution with $\text{[math]}$ working time.

Lets divide queries by blocks of $\text{[math]}$ size (or even $\text{[math]}$ for a little bit faster solution). Then for every update query you just remember "i'll have to do that update later", and for sum query you first take old value of partial sums, and then for every update that you still have to do — intersect it with your sum query range and add required fibonacci partial sum to your answer. At the end of every block just do all updates that you need in O(N) (moving from left to right over your array) and update partial sums.

This solution works 2-3 seconds and passes TL without any problems. Here is mine: 7087032

mxh1999

It's really a hard round.(a math round again?) congratulations to the winners and thanks to DZY!

andrew.volchek

+29

It seems that tests for Div1 D are weak, for test

this AC solution 7089186 gives 0.5 which is wrong. Other AC solutions, for example this 7086133, gives 0.3333333.

sorin

Could somebody explain more clearly the author's solution for Div1B?

I had the following idea: Store the sums for rows and columns in two heaps. Every time I choose a row, that row's sum will decrease by n * p and every column's sum will decrease by p.

For each of the k steps I choose the maximum from the heaps. Suppose the maximum value is a column. I add its value to the answer, update it, and substract p from every line. The substraction from every line is done in O(1) using an auxiliary variable (substract_row in my code).

I get WA on test 4. My code is here: http://codeforces.net/contest/447/submission/7102900.

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:

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. :)

Just thought I'd mention, it seems you forgot to multiply the character weight by the character position in the string in the explanation for Div2.B.

p-space

← Rev. 3 →

may someone make a detailed explanation of the solution for problem Div1 D?

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 $\text{[math]}$ , 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²).

Hah, in course on Computational Math at my university I was taught that finding inverses of matrices is a crime on numerical correctness :P. What Gauss elimination gives us is a PLU = A representation of matrix A, where P is a matrix of permutation, L is a down-triangle matrix and U is an upper-triangle matrix. Then, when we want to solve equation Ax=b with fixed A and given b, we can do it by solving consecutively Pc = b, Ld = c, Ux = d :P. However I will be curious if there was ever a case such that finding inverse got bad numerical properties and such solution was demanded to fit answer into wanted precision :P.

It is probably not the best idea to find the inverse of a real-valued matrix but it seems to work in this case. You suggest not finding the full inverse, but instead leaving it at LU decomposition in order to improve precision?

I wonder if its possible to make a test that would really force some significant precision loss out of this.

My lecturer suggests (or even insists :P) not finding inverses and so I am, but I guess that for contest's purposes finding inverse will be sufficient in >=95% of cases, so profits resulting from that PLU factorization are probably too small to give a %&*^ about this :P.

Interesting.. I made a test with N=5, M=10^5, K=10^9, only the last room is trapped, and all edges are chosen randomly, and every accepted solution I tried printed something like 0.9992 (the correct answer is obviously 1).

Weak tests eh?

You don't really need to find the inverse, you can simply do GEM with a matrix as the right side of the augmented matrix (instead of just a vector).

I don't see how inverses could be so imprecise, though, since they can also be found using GEM.

"Because computing inverse is not numerically correct"

It does what we want just as well as GEM does, since we can compute inverses using GEM. How is that not numerically correct?

I_so_sad

Is the inverse the probability from w to v? If is so,why is it?

what's the right hand side vector?

add1ctus

-11

I need help with 446B. Here's my code: 7118091

My approach is the following.

Input and summing all rows and columns
Inserting all rows in one and all columns in other priority_queue
For each step (K), check what row or column can give me the most value
Pop the maximum row or column, reduce it's value by P * number of elements in row/column, push it back
If I pick a row, I reduce the value of all columns for P and vice versa (I have two variables — rowreduction and columnreduction tracking this, I don't actually pop and push all rows/columns).

I get WA on the 4th test, it's too big for me to analyse it (I can't even get access to the full example), nor I can get access to the full test data. Would this approach satisfy the time limits, and where is my mistake?

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

vipul.jain

Can anyone please elaborate the reasoning behind the solution of DIV2 DZY Loves Sequences. The solution works but I don't understand why?

yomin

I have a problem in 446A — DZY Loves Sequences. I have found a tricky test data: 7, 1000000000,1 . According to the description, the segment sequence must be strictly increasing and thus we cannot change any number(1000000000 or 1). Thus the answer is 2. But I test my AC code and some other users' code, the output is 3. My submission ID is 7422755

afrizal

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?

Thanks, I did not look into the description carefully and I've got wrong idea.

I_love_tigersugar

In problem D, I don't know why you said "So we can solve the problem in O(n^4+a^3log(k)). we should optimize this algorithm." I think the complexity is already O(n^3+a^3log(k)).

kautsiitd

DIV 2C(DZY Loves Sequences): should not output of test case 30: 1 2 42 3 4 be 3 instead of 4?

Guts

Sequence may be 1 2 42 43 4

sonjoydabnath

9 years ago, # |

I tried to solve 446C - DZY Loves Fibonacci Numbers using sqrt-decomposition technique but got TLE on case 10. Does anbody solved it using this technique ? Or is it solvable using this technique ?

here is my submission 12033435 .

johann_wang

Well, the presenter of these problems is just an eighteen-year old boy from China, hasn't gone to university yet. I know him and I am speechless. TAT -_-|| TAT I can just explain that, the one who almost participates in IOI, but finally dropped out from China Team, has a really really really deep hatred for the world. We are just the victim.

jcvb

really?

m.ajaj94

Question about problem Div 2-E

can i solve it with segment tree and lazy propagation ?

if so ... how is the lazy propagation implemented here ??

aka.Sohieb

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

and this is my implementation 17332378

priojeet_priyom

6 years ago, # |

-8

446B — DZY Loves Modification: maintained two sets for row values and column values. in every iteration 1<=i<=k took the current maximum from row and colum set and picked the greater one. added it to answer and deleted the value from respective set and inserted it after substracting (p* (n or m) ) from it. also maintained two offset variables for row and column as deleting picking one row will effect all column values to decrease by p and vice versa. getting WA. my submision

rsrkpatwari

Did you get any solution for this issue?

ivan100sic

I used eigendecomposition for Div1-E. Fortunately there's a sparse set of eigenvectors (with total size $$$O(n \log n)$$$ and eigenvalues are also easy to compute. I wonder why the problemsetters needed to make this problem so brutal, like they purposely wanted $$$O(n \log n)$$$ solutions to fail. $$$m \le 18$$$ would have been challenging enough, without the need for insane constraints and I/O format.

t1war1

5 years ago, # |

How to implement div2 C using 2 pointers? I implemented it but it was failing on many cases.

Periquito

Using your solution of Div1A, doesn't this testcase print 2 instead of 3?

4
1 2 1 3

The $$$l_i$$$ would be

1 2 1 2

and the $$$r_i$$$ would be

2 1 2 1

The only elements that satisfy $$$a_{i - 1} + 1 < a_{i + 1}$$$ are the first and the last if you interpret the element before the first and after the last as $$$-\infty$$$. And for those, $$$l_{i - 1} + 1 + r_{i + 1} = 2$$$ ($$$l_{i - 1} = 0$$$ when $$$i = 1$$$, and $$$r_{i + 1} = 0$$$ when $$$i = n$$$). So the answer is 2. But there is a subsegment of length 3: we could choose the last 3 elements 2 1 3 and change the 2 to a 0, and we would have the sequence 0 1 3, which is strictly increasing.

aditya_sheth

I know the contest was long time ago, but why is sqrt decomposition method giving TLE in div 1 C. The time limit is given to be 4s and the total number of operations are around 2e8. My code

OOOOOOOOO0

2 years ago, # ^ |

Just use BS = 700.

sm1ley

Can some one explain solution D with fenwick trees. I have seen plenty of solutions with this code

adding on range

//fenwick trees t1,t2,t3
        //l,r are ranges

        add(t1,l,f[l]*s); 
        add(t1,r,f[l]*s*(-1));

        add(t2,l,f[l+1]*s*(-1));
        add(t2,r,f[l+1]*s);

        add(t3,l,-1);
        add(t3,r,f[r-l+2]);

output-query

l--;
       ll sum1 = get(t1, l)*f[l+4] + get(t2, l)*f[l+3] + get(t3, l);
       ll sum2 = get(t1, r)*f[r+4] + get(t2, r)*f[r+3] + get(t3, r);
       ll ans = sum2 - sum1;

cout<<(ans+mod)%mod<<endl;