I wrote an N*K^2 dp getting inspiration from @carre 's NRWP subtask 2 where K^2 states for each i can be easily converted to only 2 states giving us O(N) solution- implementation.
4 Likes
I solved the first subtask with an M*N2 DP solution and then ran the code for all N ranging from 1 to ~200 and printed the outputs locally. I observed a pattern: ans(N) for N>3 can be expressed as ans(2) + (ans(3)-ans(2))*(N-2)
So for the bigger subtasks with M=2, I simply calculated answer for N=3 and N=2 and then used this formula for the given N. Not the best way to solve the problem because it allowed me to get AC without really understanding the underlying theory about Euler’s formula 
(link to my implementation).
But learnt something from reading the editorial. Nice question and neat editorial!
3 Likes
Very simple and innovative. During contest I tried to come up with NxM dp without any luck. Thank you for editorial!
Can you please explain it a little bit more ?
I’d love to but in a few hours …I’ll write in detail.
What is linearity of expectation?
Okay, Will be waiting for it 
It’s great that I could have inspired you, sadly I didn’t inspire myself and wrote a really ugly solution 
Congratulations on your approach!
3 Likes
I got some hint from this paper. I managed to derive a formula using the methods stated in it. Find the increase in the expected number of connected components after adding one column. Cool Problem
You can also solve this problem using elementary probability theory. The M = 1 case is pretty easy:
Let random variable I_i = 1 if A[i] \neq A[i+1] and 0 otherwise. Filling up the one dimensional array A from 1 to N, you can notice that every time a new component is created if and only if A[i] \neq A[i+1]. So the number of components is 1 + \sum_{i=1}^{N-1} I_i. Since the variables inside the sum are independent, the sum itself is a binomial distribution with parameters N-1 and 1 - 1/K. Formally, \sum_{i=1}^{N-1} I_i \sim B(N-1, 1 - 1/K). See Binomial distribution on Wikipedia. We know that the expectation value of the binomial distribution is the product of the two parameters so the expected number of components are: \displaystyle 1 + (N-1) \cdot \frac{K-1}{K}.
Notice that it is in the form of a constant plus (N-1) times a value that only depends on K:
c + (N-1) \cdot f(K).
Update: The discussions below this point are only valid for M=2, which has been pointed out in the comment below. I apologize for my mistake.
This is also true for higher values of M although the calculation needs a bit more work than using Euler’s theorem. The observation is that, while filling the matrix column by column, the increase in the number of components only depends on the values of the last column and the newly added column. That is, it only depends on M and K. For a fixed M, the dependence is only on K. So for M=2 we can determine f(K) by studying the configurations of 4 random variables. The constant c in the above expression is the expectation for one column which we have already calculated above.
So, I think it is possible to solve this for higher values of M but it will get complicated.
2 Likes
I don’t think this can be generalised for larger M's. This is mainly because of the “The observation is that, while filling the matrix column by column”. That’s indeed true for the M = 2 case, but for larger values we can actually have something like this:
1111
0001
0111
Consider the first 2 columns. We have no way of figuring out that the cells (1, 1) and (3, 2) will be in the same connected component based only on two adjacent rows.
3 Likes
Yes, you are right. I incorrectly generalized the M=2 case to higher. 
So, it is a good brain teaser to think about the M \geq 3 case. 
Can anyone help me understanding the time complexity accepted for various subtasks . How do we come to know what should be the time complexity to get a particular subtask accepted. Can anyone explain with current question as an example , it would be great help for a newbie like me.
Hi @ashu_3916 take a look at @betlista’s post in this thread: how many approx loops are allowed in 1 sec time limit.
With that in mind, lets take a look at what time complexities would be accepted for various subtasks of this problem:
Subtask #1: since N and K are very small (both less than 5), solutions with really bad time complexity like exponential will also be accepted.
Subtask #2: Here N can be as large as 105 and K as large as 108. So O(N) would work, O(K) probably won’t work and O(NK) or anything bigger will definitely not work.
Subtask #3: Here N and K can be at most 500, so complexities like O(NK2), O(N2K) or lower will work because these will amount to ~107 operations but higher than that like O(NK3) won’t work.
Subtask #4: Constraints on N and K are the same as the second subtask but with M=2. So again, O(N) would work but O(NK) or bigger will not work.
So with the given constraints, the worst time complexity that could give you an AC for all subtasks and a 100 score for this problem is linear in N i.e. O(N).
Hope that helps!
2 Likes
Thanks
1 Like
Thanks. It’s a really well written editorial.
1 Like
I think I also a wrote a dp solution like you but looks really ugly as I manually added all possible cases. CodeChef: Practical coding for everyone
can you tell how did you arrive at the formula?
Motivation : The problem can be thought of as dividing the rectangles into “regions”(a region consists of cell(s) sharing having the same number and sharing a common side/boundary). We want to find the expected number of regions , where the cells are filled with numbers uniformly and randomly from [1,k].
Initially, I got a combinatorics formula just for the case m=1. This was based on multinomial theorem. I tried a lot for a similar formula for the case m=2, but couldn’t find a similar formula as there were a lot of cases in the merging of two 1* N rectangles(such as overlapping regions of the two 1* N rectangles) etc which didn’t seem easy to handle.
I started taking many small examples(small values of n,k) for the case m=1. I noticed that the combinatorics formula was giving really large values(of p and q), but always simplified down to a simple small fraction(p/q). I noticed a pattern in the values of p/q to arise on comparing the answers for those small examples(such as keeping n constant, incrementing k by 1 and vice versa), so I this provided some clue to look for a simpler formula.
Logic: Since the numbers are filled randomly, By linearity of expectation, the expected number of regions over the whole rectangle = summation of expectation of increase in number of regions at each step of filling numbers in the cells(we can assume without loss of generality, that it is filled in sequence/order).
For the case m=1, for the first cell, the number of regions will always increase by 1, for any number chosen. The expected increase in number of regions for the first cell is \frac{1*k}{k}
For all the remaining n-1 cells, the number of regions would increase by 1 only if the number filled at that cell is not equal to the number filled at the previous cell. If they are the same, there is no increase in the number of regions. So the expected increase in regions for the remaining cells is \frac{1*(n-1)*(k-1)}{k}.
So the expected number of regions for m=1 is \frac{1*k}{k} + \frac{1*(n-1)*(k-1)}{k}.
the case m=2 is similar to the case of m=1, but here we must take into consideration the filling of both the rows for a given column as well as consider the numbers/conditions of both the cells of the previous column.
This is a bit long so I’ll just write down the formula:
Base case: \frac{2*k*(k-1)+1*k}{k^2}
General case: (n-1)*[2*\left(\frac{k-1}{k}*\frac{k-2}{k}*\frac{k-2}{k}+\frac{k-1}{k}*\frac{1}{k}*\frac{k-1}{k}+\frac{1}{k}*\frac{k-1}{k}*\frac{k-2}{k} \right) + 1*(2*\frac{k-1}{k}*\frac{k-2}{k}*\frac{1}{k}+2*\frac{1}{k}*\frac{k-1}{k}*\frac{1}{k}+\frac{k-1}{k}*\frac{k-2}{k}*\frac{1}{k}+\frac{1}{k}*\frac{k-1}{k}*\frac{1}{k})]
Adding the base and general case and simplifying gives the required formula.
1 Like