### albertg's blog

By albertg, history, 7 years ago, translation,

735A - Ostap and Grasshopper

Problem on programming technique. You have to find at which positions are grasshoper and insect. If k does not divide the difference of position, then answer is NO. Otherwise we have to check positions pos+k, pos+2k, ..., where pos is the minimal poisiton of grasshoper and insect. If somewhere is an obstacle, then answer is NO, otherwise the answer is YES.

735B - Urbanization

First of all, note that n1+n2 chosen ones should be people with top (n1+n2) coeficients. Secondly, if the person with intelegence C will be in the first city then he will contribute to our overall IQ with C/n1 points. So, if n1<n2, then top-n1 ratings should be in the small city and the top-n2 from others — in the big city.

736A - Tennis Championship

Let us solve the inverse problem: at least how many competitors should be, if the champion will have n matches. Then there's obvious reccurrent formula: f(n+1)=f(n)+f(n-1) (Let us make the draw in a way, where the champion will play n matches to advance to finals and the runner-up played (n-1) matches to advance the final). So, we have to find the index of maximal fibunacci number which is no more that number in the input.

736B - Taxes

The first obvious fact is that the answer for prime numbers is 1. If the number is not prime, then the answer is at least 2. When is it possible? It is possible in 2 cases; when it is sum of 2 primes of its maximal divisor is 2. If 2 divides n, then so does integer n/2. n/2<=2=>n<=4=>n=4, where n is prime. According to Goldbach's conjecture, which is checked for all numbers no more than 10^9, every number is a sum of two prime numbers. Odd number can be sum of two primes, if (n-2) is prime (the only even prime number is 2). Otherwise, the answer is 3 — n=3+(n-3), (n-3) is sum of 2 primes, because it is even.

736C - Ostap and Tree

First of all, thanks to albert96 and GlebsHP for their help with the tutorial of this problem. Secondly, sorry for being late.

Problem can be solved by the method of dynamic programming. Let dp[v][i][j] be the number of possibilities to color subtree of vertex v in such a way that the closest black vertex is on depth i, and the closest white vertex — on depth j (we also store dp[v][-1][j] and dp[v][i][-1] in the cases where there are no black and white vertexes in diapason k of v respectively). In order to connect two subtrees, we can check all pairs (i,j) in both subtrees (by brute-force algorithm). Then let we have pair (a,c) in the first subtree and pair (b,d) in the second one. If min(a,c)+max(b,d)<=k, then we update value of current vertex.

Complexity of the algorithm O(n*k^4), which is acceptable for this particular problem (n — the number of vertexes, k^4 brute force search of pairs (a,b); (c,d)).

736D - Permutations

This problem consists of 3 ideas. Idea 1: remainder modulo 2 of the number of permutation is equal to the remainder modulo 2 of the determinant of the matrix whose entries are 1 if (ai,bi) is in our list and 0 otherwise. Idea 2: If we cahnge 1 by 0, then the determinant will differ by algebraic compliment. That is, if we count inverse matrix, than it will reflect reminders modulo 2 (B(m,n)=A'(m,n)/detA, detA is odd). Idea 3: Inverse matrix can be counted for O((n/32)^3) time. However, we can work is field of integers modulo 2. The summation can be replaced by XOR. So if we store in one "int" not a single but 32 numbers, then we can reduce our assymptocy to O(n^3/32), which is OK.

736E - Chess Championship

Suppose set (a1,a2,...,am). Then the list is valid if set {2m-2, 2m-4, 2m-6, ..., 0} majorizes the set {a1,a2,...,am}. Let us prove it! Part 1: Suppose n<=m. Top n players will play n(n-1)/2 games with each other and n(m-n) games with low-ranked contestants. In these games they will collect 2*n(n-1)/2 points (in each game there is exactly 2 points) for sure and at most 2*n*(m-n) points in games with others. So they will have at most 2*(n*(n-1)/2+n*(m-n))=2*((m-1)+(m-2)+...+(m-n)) points. Now construction: Let's construct results of participant with most points and then use recursion. Suppose the winner has even number of points (2*(m-n) for some n). Then we consider that he lost against contestants holding 2,3,4,...,n places and won against others. If champion had odd number of points (2*(m-n)-1 for some n), then we will construct the same results supposing that he draw with (n+1)th player instead of winning agianst him. It is easy to check that majorization is invariant, so in the end we will have to deal with 1 men competition, when set of scores {a1} is majorized by set {0}. So a1=0, and there is obvious construction for this case. So we have such an algorithm: we search for a compiment set which is majorized by {2m-2,2m-4,...,0}. If there is no such set answer is NO. Otherwise answer is YES and we construct our table as shown above. Assymptosy is O(m^2logm) (calling recursion m times, sorting the array (we can lose non-decreasing order because of poor results) and then passing on it linearly.

• -229

| Write comment?
 » 7 years ago, # | ← Rev. 2 →   +34
•  » » 14 months ago, # ^ |   0 thanks a lot it helped me a lot
 » 7 years ago, # | ← Rev. 2 →   +69 Dear Codeforces administration and contest preparation team,Should we all copy our comments from the neighbouring thread to this one (just like you did with the C/A problem statement) or would you please explain why this round is rated and why is this allowed to reuse the same problem?The final decision is obviously yours, I'm just politely asking for the commentary on this.
 » 7 years ago, # |   +61 Sorry, but this contest sucks big league. Some problems I assume are good, but those C and D are terrific!
•  » » 7 years ago, # ^ |   +231 Pls make codeforces great again.
•  » » » 7 years ago, # ^ |   0 together
•  » » » 7 years ago, # ^ |   +82 I'll create a contest and make other authors give me problems for it.
•  » » 7 years ago, # ^ |   +29 You wrote terrific, but I'm not sure whether you mean terrific or terrible. Terrific also means great :|
•  » » 7 years ago, # ^ |   +7 It's not your business! You didn't even participate in that contest.
 » 7 years ago, # | ← Rev. 2 →   +8 Where is editorial in english?
•  » » 7 years ago, # ^ |   +107 In Google.
 » 7 years ago, # | ← Rev. 2 →   +28 I think you made a mistake. For problem A and B div 1 it should say: "Just google it"
 » 7 years ago, # |   -35 Let me tell you, this round was so bigly good, it was so good folks. I had so much fun googling problems, let me tell you, you have no idea how much fun I had.
•  » » 7 years ago, # ^ |   +6 Who forced you to google?
•  » » » 7 years ago, # ^ |   -12 I actually didn't google problem C. For problem D, I knew it was some type of well known theorem, so I just googled it with no shame, since such problem shouldn't have been on a contest anyway.
 » 7 years ago, # |   +5 Jokes aside, are there any other solutions for the Tennis contest problem (736A) not using the Fibonacci Sequence?
•  » » 7 years ago, # ^ |   +4 this is actually a problem on calculating the worst-case height of the AVL-Tree.http://pages.cs.wisc.edu/~ealexand/cs367/NOTES/AVL-Trees/index.html
•  » » 7 years ago, # ^ | ← Rev. 3 →   +5 So the fibonacci pattern wasn't very intuitive to me. Hence I solved this question with a basic recurrence as described. Let us define a f(N) as minimum number of people required for a person to win N matches. If we have this, our answer is simply the greatest value of N where f(N)>=n, where n is the input, i.e. the number of people.So, for N match wins, we need N losers, hence we add N to the answer(ret). Now we run recurrence over these losers, if we notice the number of wins required for these losers will be [0,N-2], inclusive, as only if the highest player had N-2 matches won, could he have played the winner who was at N-1, leading him to N victories. Hence we iterate over [0,N-2] and find the number of people needed for those players.Hence we had all the losers counted, We add 1 to f(n) to get the total player count.Here is the recursive method. Add memoization for AC. long long f(int n){ long long ret = n; for(int i = 0; i<=n-2; i++) ret+=f(i); return ret; } This recurrence, naturally turned out give same output as fibonacci, but it is a non-experimantal way of solving this problem. Thanks :)
•  » » » 7 years ago, # ^ |   +3 I found this way better than the non-intuitive fibbonacci pattern . Thanx for writing . :)
•  » » » 3 years ago, # ^ |   0 I know that this is an old comment, but I just wanted to say thank you for sharing your approach. Helped me a lot!
 » 7 years ago, # | ← Rev. 3 →   +7 In problem D, If there are no solution without using bitset, you should set contraint for n is 500 instead. Making problem harder by bitset is not good idea!Is the complexity using bitset O(n3 / 32)?
•  » » 7 years ago, # ^ |   +23 Why do you think bitset problem is not a good idea? Many people regard a single 32-bit integer arithmetic as a single unit time operation. Then why not a bitset?
•  » » 7 years ago, # ^ |   -56 complexity is (n/32)^3 ~ 80^3
•  » » » 7 years ago, # ^ |   +28 The complexity is O(N^3 / 32). Using bitsets only reduces a factor of 32 in one dimension (the row XOR operations). The outer loops for Gaussian elimination are still O(N^2).
 » 7 years ago, # |   +36 How to solve Div2E ?
 » 7 years ago, # |   +13 Why has the determinant of a 0-1 matrix anything to do with the number of valid permutations? Can somebody explain the intuition behind this?
•  » » 7 years ago, # ^ |   +39 Actually, the Permanent of a matrix counts the number of valid permutations. However, calculating the permanent is a hard problem. But we only need the parity of the number of permutations, i.e. the parity of the permanent. For that, we can calculate the determinant of the matrix over a field of size 2 (the permanent and determinant are equal in ).
•  » » 7 years ago, # ^ |   +10 The permanent of an adjacency matrix counts the number of perfect matchings in bipartite graph of rows-columns. Since the determinant is something like a - b and permanent is a + b, they have the same parity. The number of perfect matchings in bipartite graph rows-columns is the number of vertex-disjoint covers of cycles in the original graph (every vertex will have one incoming edge and one outgoing edge). This is basically the number of valid permutations when you look at them as cycles.
 » 7 years ago, # | ← Rev. 2 →   +10 Tennis Championship : "Then there's obvious recurrent formula: f(n+1)=f(n)+f(n-1)", is it really obvious ? Can someone explain the obviousness of the formula without a rigorous mathematical demonstration ?
•  » » 7 years ago, # ^ | ← Rev. 3 →   +20 Assuming we want a guy to have played n + 1 matches:First of all, he must have played exactly n matches.Secondly, he must have beaten someone else who had played at least n - 1 matches. It is obvious that we want to minimize the number of matches used to maximize the answer. Therefore, we just assume that the guy that was beaten had played n - 1 matches before.Thus the recurrence formula comes to the surface, which is F(n + 1) = F(n) + F(n - 1), where F(n) represents the number of people we need to have one guy who has played n matches.The base case are F(0) = 1, F(1) = 2.
 » 7 years ago, # |   +15 In Problem D, I didn't know the determinant will differ by algebraic compliment. Here is my approach I tried(ultimately same as calculating inverse). We know that the original matrix has inverse, which means the rows are linearly independent. So for every row vector e_i^T, there exists a unique combination of rows that make e_i^T. We can determine the combination with row-echelon form.Next, if the matrix is singular, there exists a set of rows that XOR sum of it is zero. That is, if we change one 1 to 0 and the matrix becomes singular, we should be able to make zero with some rows, including the changed row. It is obvious that the combination originally produces e_i^T. Now we can determine the answer. (i,j) is NO if row i is included in the combination of e_j^T, YES otherwise.
 » 7 years ago, # |   +9 The Problem D ( Div2 ) can be found HereWhich is a Contest Problem. Herethat Arranged in : Sat, Aug 13, 2016Common for Some Guy. I got this problem by a Friend's resource. And Surprised .
•  » » 7 years ago, # ^ |   -13 I send round proposal at 20th December 2015, which is earlier than August 13, 2016.
 » 7 years ago, # |   +28 In problem D, shouldn't it be O(n^3/32) instead of O((n/32)^3) ?
•  » » 7 years ago, # ^ |   0 I think so, too
•  » » 7 years ago, # ^ |   0 Actually if you are going to use big O notation, then both are wrong, correct order is O(n3). But yes you are right it should be n3 / 32, at least for most accepted solutions, have not seen author's code, but i'm pretty sure he could not reduce the outer N loop, so it would never be (n / 32)3
 » 7 years ago, # |   0 Why is this article downvoted so much? By the way, about the solution for D, I think it takes n*(n-1)/2 * (2*n/32) iterations for computing an inverse matrix in the worst case because it's based on the Gaussian elimination algorithm.If someone knows a way with (n/32)^3 iterations, let me know ><.Anyway, you shouldn't use Big-O notation for explaining time complexity with constants. So, O((n/32)^3) is not good notation in the first place.
 » 7 years ago, # |   +8 How to solve div 2 E ? Editorial is also missing..
 » 7 years ago, # | ← Rev. 2 →   -11 Such bad formatting. Please make use of break tag in appropriate places, at least. Coming with so much enthusiasm to read the editorial of problems I couldn't solve and it is just disappointing to see what we get.
 » 7 years ago, # |   +5 Just curious: why are the limits to Div1C n=100 and k=20 when a O(n*k*k) dynamic programming solution exists?
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 Maybe author's solution is O(n*2^k)?
•  » » 7 years ago, # ^ |   0 Do you mind explaining your solution? It is particularly short and fast, but I can't understand it. Thanks!
•  » » 7 years ago, # ^ | ← Rev. 6 →   +34 O(n*k*k) solution: (EDIT: I think I made a mistake in the explanation for i > k) (Note: I am not good at explaining solutions, so this might not make much sense). Let us say a node q reaches a black node if for some p distance(q, p) <= k and p is black. The problem wants us to find the number of ways to color nodes such that all nodes can reach a black node.First root the tree at any node.dp[x][i] keeps track of info for node x, and 0 <= i <= 2*k.If i <= k, then node x is a distance of i from the nearest black child, and all of its children can reach a black child.If i > k, then some node in the subtree of node x is i-k-1 (<----EDIT) edges away and cannot reach a black node (there may be multiple nodes that cannot reach a black node, but it is OK to just select the farthest one, because if the farthest one is able to reach a black node in the future, then any closer ones will be able to too).Examples: If i = 0, then node x is colored black and all of its children can reach a black node.If i = k+1, then x cannot reach a black node, but all of its children can. (<----EDIT)If i = 2*k, then node x is not colored black, and there is a node in the subtree of node x that is k edges away and cannot reach a black node.At the beginning of the dfs, set dp[x][0] = 1 (this is the case when we color the node black) and dp[x][k+1] = 1 (this is the case when we don't color the case black).During the dfs call on each child (call it j), update dp[x]. This can be done by iterating over dp[x][f] and dp[j][g] for 0 <= f, g <= 2*k.There are 4 cases when updating. First let Y denote the union of x and the subtrees of the children that have already been visited (not including j). (For example, if there are edges 1-2, 1-3, 1-4, 1-5, then when j=4, Y = {1, subtree(2), subtree(3)}).f<=k, g<=k: All nodes in Y and j can reach black nodes. Update nxtDP[min(f, g+1)] because that's the distance to the nearest black node.f>k, g>k: Y and j both have a node that can't reach black nodes. Update nxtDP[max(f, g+1)] because some node max(f, g+1) edges away from x can't reach a black node.f<=k, g>k: All nodes in Y can reach a black node, but some node in g can't. If the nodes in g that currently can't reach a black node can reach black nodes in Y, update nxtDP[f]. Otherwise update nxtDP[g+1].
•  » » » 7 years ago, # ^ |   0 Wow, the representation of state is ... fantastic.
•  » » » 7 years ago, # ^ |   +13 I don't really understand the Sentence　"If i <= k, then node x is a distance of i from the nearest black child, and all of its children can reach a black child." if the distance between node x and the nearest black child is exactly k,and,so the children of the x node might have a (k+1) distance from the nearest black child (of node x). Can you explain a little?
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   0 .
•  » » » » 7 years ago, # ^ | ← Rev. 3 →   0 I don't completely understand your question, but here's an example when i <= k:Let the tree be rooted at 1 and k=5Edges are 1-2, 2-3, 3-4, 1-5If 4 is colored black but none of the other nodes are, then this would correspond to dp[4][0], dp[3][1], dp[2][2], dp[1][3]The initialization of dp[5] would NOT be affected.Note that dp[x] only contains information about subtrees of children that have already been visited. If a child has not been visited, then it will NOT affect dp[x] until it is visited.
•  » » » » » 7 years ago, # ^ |   0 Can you elaborate a bit more on setting dp[x][0] = 1 and dp[x][k+1] = 1?
•  » » » » » » 7 years ago, # ^ |   +1 Quote: ----------At the beginning of the dfs, set dp[x][0] = 1 (this is the case when we color the node black) and dp[x][k+1] = 1 (this is the case when we don't color the case black). When we initialize the DP, the only node in the subtree of x that we have currently visited is x, so this is why dp[x][k+1] is used when the node is not colored black (a node of distance k+1-k-1=0 away cannot reach a black node). dp[x][0] covers the case when it is colored black, because a node of distance 0 away (in this case x itself) is black.
•  » » » » » » » 7 years ago, # ^ |   0 Thank you!
•  » » » 7 years ago, # ^ |   0 Exactly, what does the entry dp[i][j] represent? It seems as if it represents "number of ways to color subtree rooted at i, such that the closest black node to i is j units away". Is my understanding correct?
 » 7 years ago, # | ← Rev. 2 →   +6 "Then let we have pair (a,c) in the first subtree and pair (b,d) in the second one. If min(a,c)+max(b,d)<=k, then we update value of current vertex."Can anybody clarify this? Should it mean "pair (a,b) in the first subtree and pair (c,d) in the second one"? What does it mean if min(a, c) + max(b, d) > k, and why is the converse a sufficient condition for satisfiability?I solved the problem using a completely different DP recurrence, so I would appreciate if somebody could provide some more intuition about this particular recurrence.
•  » » 7 years ago, # ^ |   0 Can you also share your approach?
•  » » » 7 years ago, # ^ | ← Rev. 2 →   +21 Sure, I'll try. Let f(x, l, d) = the number of ways to color the subtree rooted at x, where l is the distance of nearest black node to x that is NOT in the subtree rooted at x, and d is the distance to the nearest black node in the subtree of x (both can not exist, signalled by -1). The transition is very unwieldy: If min(l, d) > k, the solution is 0. If d = 0, we have to place a black node at x and we can use f(y, 1, d) for all of the children y of x and all d <= 2*k. If d > 0, one of the children must have a black node that is at distance d — 1 of its root, and all of the other children must have d' >= d — 1. I solved this case via a second DP over the children of x. Seems overly complicated... My code is here in case you want to check it out: http://codeforces.com/contest/736/submission/22556505
•  » » » » 7 years ago, # ^ |   0 Thanks a lot. Great approach. It is really unwieldy.
 » 7 years ago, # |   +38 Someone please explain the solution of "Ostap and the tree". What is the recurrence state? The editorial is not very clear. Thanks
 » 7 years ago, # |   -10 A non-tex editorial?
 » 7 years ago, # |   0 "According to Goldbach's conjecture, which is checked for all numbers no more than 10^9, every number is a sum of two prime numbers."Actually, it states that every even number (integer, obviously), not every number is a sum of two prime numbers. A small lapse, I believe, for the rest of the solution is correct and based on the correct statement.
 » 7 years ago, # |   0 Can somebody explain the editorial for Div1D? I honestly have no idea what those three ideas are.
•  » » 7 years ago, # ^ | ← Rev. 3 →   +8 The determinant of a matrix is the sum of every combination of ((-1)^inv)*(the product of all the a[i][j] chosen) where every i and j doesn't repeat itself on another chosen pair and inv is the number of inversions on the number of columns/rows chosen. This means that it has information about the sum of every possible product without repeating the same row/column inside this matrix. A key observation: -1=1 on MOD 2. The inverse matrix is the transpost of the matrix of the cofactors. You get the cofactor of some position i,j by excluding the row i and column j and getting the determinant of the rest of the matrix and multiplying it by (-1)^(i+j). This means that the inverse matrix has information about every cofactor. Also, because of 2, you don't need to worry about the (-1)^(i+j) If you change some a[i][j] from 1 to 0, the determinant will differ by the value of the cofactor associated to it because the 1 was originally multiplying cofactor and being summed to the original determinant. Think about Laplace's formula to calculate the determinant and you will understand. Since the inverse matrix has information about every cofactor, you can use it to get every single cofactor efficiently. This is my take on this problem, it might have some mistake but I think that's it.
•  » » » 7 years ago, # ^ | ← Rev. 3 →   0 Please ignore. I miss a critical condition in the problem statement.
•  » » » » 7 years ago, # ^ |   0 Just so anyone seeing this will understand: the problem would be when you can't get the inverse but since the number of permutations is always odd at the start, the determinant will be 1 on MOD 2. That means it is not equal to 0 and that's enough to say that you can get the inverse.
•  » » » 7 years ago, # ^ |   0 Thanks for the detailed explanation, it made me realise that my high school math has left me a huge hole in the concepts of matrix. If it wasn't you I wouldn't have thought of representing the combination of permutations in matrix. (They only bothered to teach me about finding the determinant of matrix using recursion in high school.) PS: In case if anyone also got TLE using 2D array, use bitset should solve the problem.
 » 7 years ago, # |   +8 can anybody explain the solution of [Ostap and Tree] not able to understand the part of editorial "Then let we have pair (a,c) in the first subtree and pair (b,d) in the second one. If min(a,c)+max(b,d)<=k, then we update value of current vertex."what is the meaning of min(a,c) and max(b,d) here , what is the significance of this condition. and how to calculate the final answer ? I tried for two days but unable to grasp the solution. sorry for bad english.
 » 7 years ago, # |   0 For Problem E, Chess Championship, you're proof is that if there exists a solution, then set {2m-2, 2m-4..} majorizes {a1, a2..}, not the other way around, which is what you want. How do you prove that if set {2m-2, 2m-4..} majorizes {a1, a2..} then there exists a solution?Also, another condition for the existence of a solution is that the sum of all a[i] is equal to m*(m-1).
 » 7 years ago, # |   +3 Not able to understand the solution of 736C - Ostap and Tree. Can someone please explain this -> 22656733. What does dp[x][i] represent and also the transitions.
 » 4 years ago, # |   0 How does someone solve problem like D (Taxes), if he doesn't know the property of Goldbach's Conjecture. Is he supposed to derive this property on his own during a 2 hour contest?
•  » » 2 years ago, # ^ | ← Rev. 3 →   0 Deleted