235.md (7171B)
1 Source: https://codeforces.com/blog/entry/5592 2 3 ### [236A - Boy or Girl](/contest/236/problem/A "Codeforces Round 146 (Div. 2)") 4 5 It is a very simple problem, just count how many distinct chars in the input and output the correct answer. 6 7 ### [236B - Easy Number Challenge](/contest/236/problem/B "Codeforces Round 146 (Div. 2)") 8 9 First of all, we can make a table of size a*b*c to store every number's d value. Then we can just brute force through every tripe to calculate the answer. 10 11 ### [235A - LCM Challenge](/contest/235/problem/A "Codeforces Round 146 (Div. 1)") 12 13 It is a simple problem, but many competitors used some wrong guesses and failed. First of all, we should check if n is at most 3 and then we can simply output 1,2,6. 14 15 Now there are two cases: When n is odd, the answer is obviously n(n-1)(n-2). When n is even, we can still get at least (n-1)(n-2)(n-3), so these three numbers in the optimal answer would not be very small compared to n. So we can just iterate every 3 number triple in [n-50,n] and update the answer. 16 17 ### [235B - Let's Play Osu!](/contest/235/problem/B "Codeforces Round 146 (Div. 1)") 18 19 Let us take a deep look at how this score is calculated. For an *n* long 'O' block, it contributes *n*2 to the answer. 20 21 Let us reformat this problem a bit and consider the following alternative definition of the score: (1) For each two 'O' pair which there is no 'X' between them, they add 2 to the score. (2) For each 'O', it adds 1 to the score. 22 23 We claim that this new definition of the score is equivalent to the definition in the problem statement. 24 25 Proof of the claim: For an *n* long 'O' block, there are *C**n*2 pairs of 'O' in it and *n* 'O' in it. Note that 2*C**n*2 + *n* = *n*2. 26 27 So now we work with the new definition of the score. For each event(i,j) (which means s[i] and s[j] are 'O', and there is no 'X' between them). If event(i,j) happens, it adds 2 to the score. 28 29 So we only need to sum up the probabilities of all events and multiply them by 2, and our task becomes how to calculate the sum of probabilities of all the event(i,j). Let P(i,j) be the probability of event(i,j). 30 31 We can see that P(i,j) can be computed by . Then we denote P(j) as the sum of all event(i,j) for i<j. We have dp(0)=0 and dp(j)=(dp(j-1)+*p**j* - 1)**p**j* 32 33 ### [235C - Cyclical Quest](/contest/235/problem/C "Codeforces Round 146 (Div. 1)") 34 35 This problem can be solved by many suffix structures. Probably using suffix automaton is the best way to solve it since suffix automaton is simple and clear. 36 37 Let us build a suffix automaton of the input string S, and consider the query string x. 38 39 Let us also build a string t as x concatenated with x dropping the last char. One can see that every consecutive sub-string of t with length |x| is a rotation of x. 40 41 Let us read the string t with suffix automaton we have build, and every time take the first char out and add a new char, add the answer by the number of string equal to this current sub-string of t (which is a rotation of x). 42 43 And one more thing, we should consider the repetend of x as well, check my solution here:[2403375](/contest/235/submission/2403375 "Submission 2403375 by YuukaKazami"). 44 45 Check here if you are not familiar with suffix automaton :[e-maxx's blog](http://e-maxx.ru/algo/suffix_automata) 46 47 ### [235D - Graph Game](/contest/235/problem/D "Codeforces Round 146 (Div. 1)") 48 49 First of all, let us consider the simpler case of trees. 50 51 Let us use Event(A,B) to denote the following event "when we select A as the deleting point, B is connected to A". 52 53 Clearly, if Event(A,B) happens, it would add 1 to *totolCost*. 54 55 So we can just simply calculate the probability of every Event(A,B), and add them up. 56 57 Let us consider how to calculate the probability of Event(A,B). 58 59 Assume there are n vertices in the path between A and B, we claim that the probability is simply 1 / *n*. 60 61 Let us try to prove it using induction. 62 63 First let us assume there's a connected sub-graph of the tree containing both A and B, if the sub-graph only has n vertices, then the event happens only if we select vertex A, so the probability is 1 / *n*. 64 65 Otherwise, assume it has x vertices there is two cases: whether the selected vertex is on the path between A and B or not. 66 67 In the first case, the probability of Event(A,B) happen is 1 / *x* because if we don't select A, Event(A,B) will never happen. 68 69 In the second case, the sub-graph containing A,B has become smaller, so the probability is (*x* - *n*) / *xn*. 70 71 So add them up we can prove this statement. 72 73 Then we can solve the tree case by simply add up the inverse of every path's length in the tree. 74 75 And for the original case, there's at most 2 paths between A and B. 76 77 If there's only one path, then everything is the same with the tree case. 78 79 Otherwise, the path between A and B should pass the cycle in the graph. 80 81 Let us examine this case, you can see that there 2 types of vertex: 82 83 Vertex on the path of A to cycle or B to cycle, they should not be selected before A because once they're selected, A and B lost connectivity, let us call them X. 84 85 Vertex on the cycle, the two paths from A to B, each path contains a path in the cycle, let us call them Y and Z. 86 87 So there are two possibilities: X and Y are free when A is selected, X and Z are free when A is selected. 88 89 And we should subtract the case that X and Y, Z are all free when A is selected because it double-counts before. 90 91 So the probability is 1 / (*X* + *Y* + 1) + 1 / (*X* + *Z* + 1) - 1 / (*X* + *Y* + *Z* + 1). 92 93 Check [Petr](/profile/Petr "Legendary Grandmaster Petr") 's solution for the details: [2401228](/contest/235/submission/2401228 "Submission 2401228 by Petr") 94 95 And my C++ implementation: [2403938](/contest/235/submission/2403938 "Submission 2403938 by YuukaKazami") 96 97 ### [235E - Number Challenge](/contest/235/problem/E "Codeforces Round 146 (Div. 1)") 98 99 Let us consider each prime in one step, the upper limit for *a*, *b*, *c* is recorded. 100 101 So if we fixed the power of 2 in each *i*, *j*, *k* like 2*x*, 2*y*, 2*z*, then their upper limit becomes *a* / 2*x*, *b* / 2*y*, *c* / 2*z*, and the power of 2 in their multiplication is just x+y+z. 102 103 Let us denote *dp*(*a*, *b*, *c*, *p*) for the answer to the original problem that *i*, *j*, *k* 's upper limit is *a*, *b*, *c*. And their can only use the prime factors which are not less than *p*. 104 105 Let the next prime to be *q*, so we can try to fix the power of *p* in *i*, *j*, *k* and get the new upper limit. 106 107 So we can do transform like this: *dp*(*a*, *b*, *c*, *p*) = sum of *dp*(*a* / *p**x*, *b* / *p**y*, *c* / *p**z*, *q*)·(*x* + *y* + *z* + 1) 108 109 Check my code here: [2404223](/contest/235/submission/2404223 "Submission 2404223 by YuukaKazami") 110 111 Also you can check [rng_58](/profile/rng_58 "International Grandmaster rng_58") solution here: [http://codeforces.com/blog/entry/5600](https://codeforces.com/blog/entry/5600) 112 113 If you have any problems, you can ask here :)