### gridnevvvit's blog

By gridnevvvit, 7 years ago, translation,

### 544A - Set of Strings

In that task you need to implement what was written in the statements. Let's iterate over all characters of string and keep array used. Also let's keep current string. If current character was not used previously, then let's put current string to the answer and after that we need to clear current string. Otherwise, let's append current character to the current string. If array, that contain answer will have more then k elements, we will concatenate few last strings.

The jury solution: 11035685

### 544B - Sea and Islands

It's clear to understand, that optimal answer will consists of simple cells, for which following condition fullfills: the sum of indices of row and column is even. We will try to put k islands in such way, and if it's impossible, we will report that answer is NO. Try to prove that this solution is optimal.

The jury solution: 11035691

### 543A - Writing Code

Let's create the solution, which will work too slow, but after that we will improve it. Let's calculate the following dynamic programming z[i][j][k] — answer to the problem, if we already used exactly i programmers, writed exactly j lines of code, and there are exactly k bugs. How we can do transitions in such dp? We can suppose that we i-th programmer will write r lines of code, then we should add to z[i][j][k] value z[i - 1][j - r][k - ra[i]]

But let's look at transitions from the other side. It's clear, that there are exactly 2 cases. The first case, we will give any task for i-th programmer. So, we should add to z[i][j][k] value z[i - 1][j][k]. The second case, is to give at least one task to i-th programmer. So, this value will be included in that state: z[i][j - 1][k - a[i]]. In that solution we use same idea, which is used to calculate binomial coefficients using Pascal's triangle. So overall solution will have complexity: O(n3)

The jury solution: 11035704

Let's solve easiest task. We have only one pair of vertices, and we need to calculate smallest amout of edges, such that there is a path from first of vertex to the second. It's clear, that the answer for that problem equals to shortest distance from first vertex to the second.

Let's come back to initial task. Let's d[i][j] — shortest distance between i and j. You can calculate such matrix using bfs from each vertex.

Now we need to handle two cases:

1. Paths doesn't intersects. In such way we can update the answer with the following value: m - d[s0][t0] - d[s1][t1] (just in case wheh conditions on the paths lengths fullfills).
2. Otherwise paths are intersecting, and the correct answer looks like a letter 'H'. More formally, at the start two paths will consists wiht different edges, after that paths will consists with same edges, and will finish with different edges. Let's iterate over pairs (i, j) — the start and the finish vertices of the same part of paths. Then we can update answer with the following value: m - d[s0][i] - d[i][j] - d[j][t0] - d[s1][i] - d[j][t1] (just in case wheh conditions on the paths lengths fullfills).

Please note, that we need to swap vertices s0 and t0, and recheck the second case, because in some situations it's better to connect vertex t0 with vertex i and s0 with vertex j. Solutions, which didn't handle that case failed system test on testcase 11.

The jury solution: 11035716

### 543C - Remembering Strings

First that we need to notice, that is amout of strings is smaller then alphabet size. It means, that we can always change some character to another, because at least one character is not used by some string.

After that we need handle two cases:

1. We can change exactly one character to another. The cost of such operation equals to a[i][j] (which depends on chosed column) After that we can remember string very easy.
2. We can choose some column, and choose some set of strings, that have same character in that column, By one move we can make all these strings are easy to remember.The cost of such move equals to cost of all characters, except most expensive.

As the result, we will have following solution: d[mask] — answer to the problem, when we make all strings from set mask easy to remember. We can calculate this dp in following way: let lowbit — smallest element of set mask. It's clear, that we can do this string easy to remember using first or second move. So we need just iterate over possible columns, and try first or second move (in second move we should choose set that contain string lowbit) Overall complexity is O(m2n), where m — is length of strings.

The jury solution: 11035719

Let's suppose i is a root of tree. Let's calculate extra dynamic programming d[i] — answer to the problem for sub-tree with root i We can understand, that d[i] equals to the following value: — where j is a child of the vertex i. It's nice. After that answer to problem for first vertex equal to d[1].

After that let's study how to make child j of current root i as new root of tree. We need to recalculate only two values d[i] and d[j]. First value we can recalculate using following formula d[i]: suf[i][j] * pref[i][j] * d[parent], where parent — is the parent of vertex i, (for vertex 1 d[parent] = 1), and array suf[i][j] — is the product of values d[k], for all childs of vertex i and k < j (pref[i][j] have same definition, but k > j). And after we can calculate d[j] as d[j] * (d[i] + 1). That is all, j is root now, and answer to vertex j equals to current value d[j]

The jury solution: 11035737

### 543E - Listening to Music

Let's sort all songs in decreasing order. We will iterate over songs, and each time we will say, that now current song will fully satisfy our conditions. So, let's si = 0, is song i was not processed yet and si = 1 otherwise. Let . It's clear, when we add new song in position idx then we should do  + 1 for all on segment [max(0, idx - m + 1), idx] in our array v. So, when we need to implement some data structure, which can restore our array v to the position when all strings have quality  ≥ q. It also should use very small amout of memory. So, answer to the query will be m - max(vi), lj ≤ i ≤ rj.

We will store this data structure in the following way. Let's beat all positions of songs in blocks of length . Each time, when we added about songs as good, we will store three arrays: first array will contain value vi of first element of the block of indices. second array will contain maximum value of v on each block and also we will keep about of ''small'' updates which doesn't cover full block. Using this information array v will be restored and we process current query in easy way.

The jury solution: 11035739

• +31

 » 7 years ago, # | ← Rev. 3 →   0 I think in part 543A - Writing Code, fourth line shoud be z[i][j][k] value z[i - 1][j - r][k - ra[i]] not can z[i][j][k] value z[i][j - r][k - ra[i]].I still don't understand about The second case, is to give at least one task to i-th programmer.So, this value will be included in that state: z[i][j - 1][k - a[i]]. In that solution we use sameidea, which is used to calculate binomial coefficients using Pascal's triangle.. Can you explain clearly for me. Thanks !Sorry for my bad English
•  » » 7 years ago, # ^ |   -9 Ok, we have current state z[i][j][k]. we perform transitions, first z[i + 1][j][k] +  = z[i][j][k], second z[i + 1][j + 1][k + a[i]] and so on. You can see, that when we calculate value z[i + 1][j + 1][k + a[i]] we already have z[i][j][k] in state z[i + 1][j][k].
•  » » » 7 years ago, # ^ | ← Rev. 3 →   -9 [EDIT]: I had a huge misconception. I created a blog for this question. Hopefully this will help. Let's call a sequence of non-negative integers v1, v2, ..., vn a plan, if v1 + v2 + ... + vn = m.can v1, v2, ..., vn be zero? sorry I got confused because of example input 3. as the answer is 0.
•  » » » » 7 years ago, # ^ |   0 Yes, "non-negative integers" means any number >= 0.
•  » » » » 7 years ago, # ^ |   0 yes, any of v1, v2, ..., vn can be zero.
•  » » » 7 years ago, # ^ |   -12 Same thing using the recursive formula: = dp(i, j - 1, k) + dp(i - 1, 0, k - jai)
 » 7 years ago, # |   0 English Version plss . Translator works badly for eg for Div1C .
 » 7 years ago, # |   0 On 543D, I don't understand why
•  » » 7 years ago, # ^ | ← Rev. 2 →   -9 The road between i and j can be good for all cases, totally d[j] The road between i and j can be bad if and only if all roads in the subtree of j is good, totally 1 For each children of i, the states of roads between i and any child are independent of each other, so d[i] is the product of them.
 » 7 years ago, # |   0 For problem B, "Let's come back to initial task. Let's d[i][j] — shortest distance between i and j. You can calculate such matrix using bfs from each vertex. ", so the complexity is O(n*E), and E may be n*(n-1)/2, so the complexity in worst situation is O(n^3), why it can be figure out in 2 seconds? Or the test data is weak?
•  » » 7 years ago, # ^ |   0 notice that: E <= min(3000, n(n-1)/2)
•  » » » 7 years ago, # ^ |   0 oops, I'm silly, I found the solution in the contest time, but I have not writen it, because I was under the misapprehension that E maybe reach n(n-1)/2.
 » 7 years ago, # |   -11 although i fail to solve anyone in the contest, but i still think the problem is very good. Thank you!
 » 7 years ago, # |   0 Failed C WA #11 but have the same idea as you and fell from 16th to 140th place because this in first contest :( :( :(I want ask can't paths in D intersect more times not just once?
 » 7 years ago, # |   0 For 544A, I am getting the correct output but the Checker log says wrong answer s_1 + s_2 + .. + s_k != q. I know it is trivial but do help me understand.Submission 11025841
•  » » 7 years ago, # ^ |   0 I resubmitted your exact code and it got Accepted. So I don't get why your code didn't get Accepted the first time around.
•  » » » 7 years ago, # ^ |   0 Wondering the same thing myself.
 » 7 years ago, # |   0 Would anyone please discuss the recursive dp approach to DIV 2 C ? In editorial solution of DIV 2 C , why we are taking the array dp[2][N][N] ? As there are i people shouldn't it be dp[N][N][N] (which will cause memory limit though) ? What's the trick behind this implementation ?
•  » » 7 years ago, # ^ |   0 To compute dp[i][][], you only need values from dp[i-1][][]. So you only maintain 2 positions (current and previous).
 » 7 years ago, # | ← Rev. 3 →   0 In 543 B why is it necessary that we have to consider the shortest paths only ? Can't there be a case where there are two paths that intersect to an extent that the number of edges on these paths is lesser than the edges on the shortest paths in cases where the shortest paths dont intersect at all ? Like for example if shortest path from s1 to t1 has 4 edges and that from s2 to t2 has 4 edges as well but they dont intersect so we can destroy m-8 edges but what if there is another path from s1 to t1 which has 5 edges and also from s2 to t2 which has 5 edges and 3 of these 5 edges are common. So total distinct edges will be 5+5-3=7 and we can destroy m-7 roads which is better than m-8. Sorry for the long post but it would be great if someone could clear this for me :p
•  » » 7 years ago, # ^ |   +1 In the intersecting case, you don't have to find the shortest path from s1 to t1 and from s2 to t2 and then remove the common edges. Consider a H-shape with the horizontal line as common path with end points p1 and p2. You need to consider shortest distances from s1 to p1 (upper left vertical line), s2 to p1 (lower left vertical line), p1 to p2 (horizontal line — representing common path), p2 to t1 (upper right vertical line) and p2 to t2 (lower right horizontal line).
•  » » » 7 years ago, # ^ |   0 Ok seems like I misunderstood then. Thanks.
 » 7 years ago, # |   0 Can someone please explain 543A? I understood it using 2D dp solution 2D DP but dont understand what is given in the tutorial. How are you making the recursion?
•  » » 7 years ago, # ^ |   0 I created a blog. Hopefully this will help.
 » 7 years ago, # | ← Rev. 2 →   +5 problem e is clearly google translated, its hard to understand anything from it
 » 7 years ago, # |   +5 div1.A can be solved by two dimension complete_knapsack.
•  » » 7 years ago, # ^ |   0 I can't agree more
 » 7 years ago, # |   0 In 543 B, why are we swapping only s0,t0? Shouldn't we swap s1,t1 too and check for that case?
•  » » 7 years ago, # ^ |   0 got it.
•  » » » 6 years ago, # ^ |   0 OK You got it, can you tell me why?
 » 7 years ago, # | ← Rev. 2 →   0 For Div1 — D, the statement said:"Next line contains n - 1 positive integers p2, p3, p4, ..., pn (1 ≤ pi ≤ i - 1) — the description of the roads in the country."But I didn't see anything talk about this before. So, what do these numbers mean?
•  » » 7 years ago, # ^ |   -8 Let's suppose that we have an query [li, ri]. First, we can notice, that li sometimes is not a start of some block. In that case, let's use value vj, where j — is first element of same block with element i. We need update value vj with no more then updates, after that we can get original value vi using array with quality — a. Same thing we can do with ri, if ri is not a finish of some block. After that, we will have only full blocks. First thing, that we need to do, we need to apply ''small'' updates, for some blocks. For example, we have block [0, 50], then ''big'' update will update full block, and small only some part, [1, 4], [0, 20], [1, 50]. This updates we have when some updates doesn't cover full block. After that, let's process few queries [lk, rk] and full blocks, that this blocks cover. We can not do this in naive manner, but we use following trick: let's g is a first full block that is covered but query and f is last. We will do push[g] +  = 1 and push[f + 1] -  = 1 and after that we need to calculate partial sums here. So, now we can answer to query on such blocks. Is it clear now?
•  » » » 7 years ago, # ^ |   0 We have a slight language barrier, but we're making progress. Sorry that some people downvoted you for that.If l_i is not the start of a block, you use O(sqrt(n)) brute force to make it the start of a block, same for r_i. Understood.For each update, updating the blocks that are fully covered is easy, just use prefix sums. Got it.But what do you do about the updates that don't start at the beginning of a block? You don't even store all v values inside a block, so how do you do this update?
•  » » » » 7 years ago, # ^ |   +8 General idea — is to separate updates that fully cover some block, and ''small'' updates that doesn't cover full block. In first case we process such updates using prefix sums when we need to answer the query, and ''small'' updates we can process in naive way, and after that keep only maximal value after update for block.
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   +8 What do you mean by naive way?You don't store all values of v, so how can you update them?EDIT: Nevermind, got it. You don't just start a new block after every sqrt(n) indices, you also start one whenever an update starts or ends. So 3*sqrt(n) blocks in total for each stored point.Thanks for the patience.
•  » » » » » » 7 years ago, # ^ |   0 Would you be so kind and answer following question: why it is sufficient to store O(sqrt(n)) information at each store point? How it is possible to restore information inside the block using the stored information?
•  » » » » » » » 7 years ago, # ^ | ← Rev. 6 →   +3 A single store point is responsible for the queries with qi in some interval [a,b], such that the interval [a,b) contains O(sqrt(n)) songs (it doesn't matter how many songs have value b). For this store point, we partition the v array (which contains information about all songs with value in [b,infinity) ) into blocks with the following properties:First property: For every song i with a_i in [a,b], a new block starts at i and at i+m.Second property: For each k, a new block starts at k*sqrt(n).These two properties can be satisfied with O(sqrt(n)) blocks, since k is between 0 and sqrt(n), and there are O(sqrt(n)) songs with a_i in [a,b). For each block, we store the first, last and best v_i inside that block (so 3 values per block).The two properties guarantee that we need O(sqrt(n)) time per query: The second property makes sure the start of a block is always nearby, and the first property makes sure that we have enough information to process all songs between the store point and the query point in O(1) time each (that's O(sqrt(n)) songs with O(1) time for each song).Restoring the information works, because each song covers only complete blocks (first property), not any partial block. So, the first, last and best v of a block are all increased by 1 when you add a new song that affects that block. The first and last let you convert the query so it starts where a block starts and ends where a block ends, while the best lets you process each block in O(1).
•  » » » » » » » » 7 years ago, # ^ | ← Rev. 3 →   0 But what do you do if li=j is inside any block? You have to restore (find maximum) from vj, vj+1, ... , vj+O(sqrt(n)). Do we use array of qualities? How? Thank you.Update. Looks like this: We have v1 and we can go from vi to vi+1 in O(1) using quality array. Thank you.
•  » » » » » » » » » 7 years ago, # ^ |   +3 We don't have just v_1, we have v_i if i is the start of a block (so distance at most sqrt(n) from j).
 » 7 years ago, # |   0 I think my algorithm for problem D (Div.1) is correct but get wrong on test 10 :((Who can help me ?CODEsorry for bad English:|
•  » » 7 years ago, # ^ |   +15 It seems that you are using division by 0 modulo P somewhere, and result isn't correct in this case.
•  » » » 7 years ago, # ^ |   0 tanks a lot!:)How to fix it?
•  » » » » 7 years ago, # ^ |   +7 Present any number x as pair  < x / Pα, α > , where α is maximal degree such that x is divisible by Pα. So, 1 =  < 1, 0 >  and 2P3 =  < 2, 3 > .
•  » » » » » 7 years ago, # ^ |   0 tanks!
•  » » » » 7 years ago, # ^ |   +8 In this problem, you just can calculate prefix and suffix product
•  » » » » » 7 years ago, # ^ |   0 thank you so much. and I will try to learn more about prefix and suffix product.
•  » » 7 years ago, # ^ |   0 Hi. Do you know that a / b = a * inv(b) mod p if gcd(b,p) = 1? Are you sure that the condition gcd(b,p) = 1 is satisfied in your solution?
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 There's some misunderstanding. If p is prime and b % p != 0, a/b=a*b^(p-2) If p is prime and gcd(b, p) == 1, b % p != 0. So, there isn't any problem.
•  » » » » 7 years ago, # ^ |   0 I'll give you an example.a = 24; b = 6; p = 3; inv(b) mod p = b ^ (p - 2) mod p = 6 mod 3 = 0;(a / b) mod p = 1(a * inv(b)) mod p = 0 != 1So as you can see the requirement of b and p being coprime is important here.
•  » » » » » 7 years ago, # ^ |   +8 0 / 0. Good example.
•  » » » » » » 7 years ago, # ^ | ← Rev. 2 →   0 0/0? Are you serious?:) I didn't write it like a / (b mod p) as you can see, which is absolutely different example.
•  » » » » » » 7 years ago, # ^ |   0 I suggest that you look here where it's clearly stated.
 » 7 years ago, # |   -8 Can someone help me optimize this code? http://codeforces.com/contest/542/submission/11055397 I essentially just implemented the solution given in the editorial, but it runs in about 2.3 seconds.. I tried some small optimiziations you can see in my submission history but to no avail (the answer is printed but still shows TLE)
•  » » 7 years ago, # ^ | ← Rev. 2 →   +1 You could try doing this HashSet set = m.get(j); if(set == null) { set = new HashSet(); m.put(j, set); } set.add(count); //if(!m.containsKey(j)) m.put(j, new HashSet()); //m.get(j).add(count); 
•  » » » 7 years ago, # ^ |   0 I tried this (and the below suggestions) and now the code runs in 1.7 seconds on my machine but still gives TLE ?!?!?!!? why is this happening? (this is my new code http://codeforces.com/contest/542/submission/11066406)
•  » » » » 7 years ago, # ^ |   0 http://codeforces.ru/contest/542/submission/11056795 The most of the time takes the last cycle. You should precalculate pows.
•  » » 7 years ago, # ^ |   +1 int sqrt = Math.sqrt(i-1); for(long j=2; j<=sqrt; j++) {} //for(long j=2; j<=Math.sqrt(i-1); j++) {} 
•  » » » 7 years ago, # ^ |   0 Or better: //int sqrt = Math.sqrt(i-1); //for(long j=2; j<=sqrt; j++) {} //for(long j=2; j<=Math.sqrt(i-1); j++) {} for(long j = 2; j * j <= i; j++) {} 
•  » » 7 years ago, # ^ |   0
 » 7 years ago, # |   -39 Codechef's snackdown is here.Prizes:1) For Non-Indians:1st : Prize: Macbook Pro for team members2nd: Prize: Drone Quadcopters for team members3rd: Prize: Go Pro Cameras for team members2) For Indians1st: Prize: 3 Lakhs + Job offer with directi + Goodies2nd: Prize: 2 Lakhs + Job offer with directi + Goodies3rd : Prize: 1 Lakhs + Job offer with directi + Goodies
 » 7 years ago, # |   -16 For problem Destroy Roads. I am getting TLE for test 8, and I think that I am essentially doing the same things as the sample solution, but cant figure out why is it slower. Any pointers will be appreciated.This is the code
•  » » 7 years ago, # ^ |   -8 Apologies first time I have tried to link to a submission, Here is the correct link
•  » » 7 years ago, # ^ |   -10 Why the minuses ?
 » 7 years ago, # |   +16 What a great editorial for 544B:It starts off by saying: "It's clear to understand". If it's clear then what are editorials for, you idiot? IF SOMEONE IS READING THE EDITORIAL, IT MEANS THAT IT IS NOT CLEAR TO THEM. IF IT WAS CLEAR THEY WOULD NOT BE READING THE EDITORIAL, YOU DUMB ASS. Then it gives the answer in one line without explaining AT ALL how to reach the answer. And in the end, instead of giving the proof it says: "Try to prove that this solution is optimal." TRY TO PROVE THAT IT IS OPTIMAL?? THEN WHAT THE HELL IS THE EDITORIAL FOR?WHY DO YOU EVEN BOTHER TO WRITE THESE 2-3 LINES? WHY NOT SAY GO FIGURE IT OUT YOURSELF. At least you can be honest then, instead of writing this fake ass editorial.
•  » » 7 years ago, # ^ |   0 You made my day man (LOOOOOL)
•  » » 6 years ago, # ^ |   0 Die of laughing so hard, lol
•  » » 2 years ago, # ^ |   0 I know it's late but I have to agree with you. I am sick of wasting time on the question, then when I check editorial for the solution, it doesn't help at all.
 » 7 years ago, # |   0 In 544B why do we get wrong answer if we place Land(L) on cells whose sum of row and column is ODD, instead of EVEN?
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 For example, you need to place 5 islands on 3x3 land. So the only answer is thisLSL SLS LSLIf we try to place land when (i+j) is odd, then the most we can get isSLS LSL SLSso this way we can only place 4 islands.
 » 7 years ago, # |   0 What's the time complexity of 543E
 » 7 years ago, # |   0 Does anyone know a similar task to 543A — Writing Code?
 » 6 years ago, # |   0 In problem B case 2 , why is taking only H shaped paths optimal not paths having some common path and then uncommon and then common ...?? Please do answer anyone!!
 » 6 years ago, # |   +1 sorry to say, but i really dislike tutorials on Codeforces in general as usual they are very short and all i see is brief idea. 5 line of div1 D problem seems very far from enough. is it to hard to explain problem with more details like on Topcoder?. for me i can't understand well 543D div1 problem,it is not simple problem for me.i am glad, if someone can to explain it with more detail.thanks
•  » » 6 years ago, # ^ |   0 Hopefully you are still lurking around this post after six weeks, here is a zero to one hundred explanation of Div1D.First of all, let's simplify the problem. What if we are trying to solve the problem for a fixed capital X? Consider a dp[node][bad_road_cnt] array for processing the answer. It is not hard to see that dp[node][0] is always 1, because there is only one way to fix all the roads. For dp[node][1], there are two ways to reach this state. 1: dp[child][0] ways, we leave the road from child to node bad; 2: dp[child][1] ways, we fix the road from child to node. It is not hard to see it is unnecessary to keep dp[node][0] to calculate dp[node][1], so we will just keep a dp[node] for simple purpose. It's not hard to see the ways of dp[node] for a subtree of nodes is the (dp[child1]+1) * (dp[child2]+1) ... of all children (Remember dp[node][0]=1). By recursion we can see that we can solve the subtrees one by one until we reach the node.Now we can solve the problem for a fixed capital x, and that will take us O(n) time. Obviously if we stop from here we will need O(n^2) time to solve the original problem, so we still have to work better.(The following is not the same approach as the editorial)Consider moving the root from u to v, the only difference between the original and the new tree is that v is no longer u's child and u is v's child. Obviously we can just take away node v from dp[u] by multiplying (dp[v])^-1 = MOD, and then update dp[v] by multiplying (dp[u]+1) since it is now a parent of v.The last thing we have to handle is zero problems. Check the comment below to learn more about it.
 » 6 years ago, # |   0 My implementation on 543D: http://codeforces.com/contest/543/submission/19879959For those who are not familiar with prefix/suffix product, or doesn't have a clear visualized picture of what the prefix/suffix product is doing (just like me), here's a method using the Fermat's little theorem.When moving the root from vertex u to v, we can simply transfer the state by d[u]*=(inverse(d[v])), d[v]*=(d[u]+1). The only problem that this method has is it is vulnerable to zero modules (Since MOD-1 is not a prime, that means we run a risk that we compute an incorrect inverse(d[v]) ).Fortunately this is the only exception we have to handle, just keep a zero flag when handling d[u]. Whether a node where it's actual value + 1 == MOD is handled, just manipulate the zero flag of it before further calculating the value of it.
•  » » 6 years ago, # ^ |   0 Great post.thanks a lot.
•  » » 5 years ago, # ^ |   +6 Instead of d[u]*=(inverse(d[v])) why you are not doing d[u]*=(inverse(d[v]+1)) ?? As while multiplying when v was a children of u then also for calculation of d[u] you have multiplied (d[v]+1).
•  » » » 5 years ago, # ^ |   0 I am doing dp[u] *= d[v]^-1, the brackets just juked you. :P
•  » » » » 5 years ago, # ^ |   +6 I m saying when v was a child of u for calculating dp[u] you have multiplied with a factor (dp[v]+1) now as you are shifting from u to v i.e making u as a child of v then to nullify the effect of vertex v on u previously why you are dividing it by (dp[v]) only instead of (dp[v]+1) ??
•  » » » » » 5 years ago, # ^ |   0 In function move(u, v):pwr( (zero[v]?0:dp[v]) +1, MOD-2)Sorry for the typo in the reply, instead of dp[v]^-1 it was (dp[v]+1)^-1
•  » » 5 years ago, # ^ |   0 What does zero modules mean in here? Could you elaborate " (Since MOD-1 is not a prime, that means we run a risk that we compute an incorrect inverse(d[v]) "?
•  » » » 5 years ago, # ^ |   0 There exists cases where d[x] = 0 mod (MOD-1) since (MOD-1) = 2*500000003, and 0^-1 mod (MOD-1) does not exist, therefore we need to hardcode to handle this case.
 » 5 years ago, # | ← Rev. 2 →   0 Can you help?Div1 DWhy this code got WA5, but this code got AC?!Mystic...
 » 4 years ago, # | ← Rev. 2 →   0 Division 1 — Problem D: I will appreciate if someone can let me know why I am getting TLE for this submission: http://codeforces.com/contest/543/submission/37541129I use DP, and I assign an index to each edge in the tree. There can be at most O(n) edges in the tree. Therefore, I would need O(n) in total. I am guessing maybe the recursive function goes in depth too much, and it causes TLE. However, I see that Judge's solution also uses a recursive function for DFS.
•  » » 4 years ago, # ^ |   0 I figured out that when we are given a star, the recursive function turns out to be slower than I expected. This is because there are n queries, and the inside the recursive function can be called n times. This would yield O(n2) which definitely leads to TLE. I should have been careful about the in my recursive function.
 » 4 years ago, # | ← Rev. 3 →   -8 [Deleted]
 » 18 months ago, # |   0 Is is possible to write top down(memoization) approach for 543 A(Writing Code) within the memory limit ? I can write a O(N^3) time and O(N^3) memory solution which is giving MLE.
 » 12 months ago, # |   0 For 543D, why can't you implement rerooting by multiplying dp[vertex] by the inverse of (dp[child] + 1) then multiply dp[child] by (dp[vertex] + 1)?
 » 4 months ago, # |   +10 There's an alternative solution to problem D. So the main idea is again to do tree DP on the subtrees. $sub[x]$ is the number of ways to formulate it such that there's at most one bad road from any node in the subtree of $x$ to the "root" node $x$. There's a nice recurrence relation for $sub[x]$, namely: $sub[x] = \prod_{i \in \text{children}[x]} sub[i] + 1.$Let's look child by child. We could have a bad edge from the "root" node to one of its children, in which case there is 1 way to proceed for that child's subtree. Or we can have a good edge from the root to the child, in which case it's just $sub[i]$. Take the product because they're independent events (one child doesn't affect the other).The problem now is how to recompute the various values in $sub$. Good thing is that $sub$ actually doesn't change much. If we re-root the tree from $y$ to $x$, where $x$ and $y$ are adjacent, the only values that change are $sub[x]$ and $sub[y]$. They can be recomputed fairly easily too: $sub[y] = (sub[x] + 1)^{-1} \cdot sub[y]$ and $sub[y] = (sub[x] + 1) \cdot sub[y]$.All done? Nope. There's a subtlety I missed, causing a wrong answer on the 10th test case. The issue is that if $sub[x] = MOD - 1$, then we have a 0 inverse. This doesn't happen too often, so when it does happen, all we have to do is recompute $sub[y]$ manually as $\prod_{i: adj[y], i \ne x} sub[i] + 1.$Footnote: If we have small modulo (which we don't thankfully), my solution won't work, since we're going to have too many collisions.