### albertg's blog

By albertg, history, 3 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. Tutorial of Codeforces Round #382 (Div. 2) Tutorial of Codeforces Round #382 (Div. 1) Comments (71)
 » 3 years ago, # | ← Rev. 2 →
 » 3 years ago, # | ← Rev. 2 →   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.
 » Sorry, but this contest sucks big league. Some problems I assume are good, but those C and D are terrific!
•  » » Pls make codeforces great again.
•  » » » together
•  » » » I'll create a contest and make other authors give me problems for it.
•  » » You wrote terrific, but I'm not sure whether you mean terrific or terrible. Terrific also means great :|
•  » » It's not your business! You didn't even participate in that contest.
 » 3 years ago, # | ← Rev. 2 →   Where is editorial in english?
•  » » » +1
 » 3 years ago, # | ← Rev. 2 →   I think you made a mistake. For problem A and B div 1 it should say: "Just google it"
 » 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.
•  » » Who forced you to google?
•  » » » 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.
 » Jokes aside, are there any other solutions for the Tennis contest problem (736A) not using the Fibonacci Sequence?
•  » » 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
•  » » 3 years ago, # ^ | ← Rev. 3 →   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 :)
•  » » » I found this way better than the non-intuitive fibbonacci pattern . Thanx for writing . :)
 » 3 years ago, # | ← Rev. 3 →   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)?
•  » » 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?
•  » » complexity is (n/32)^3 ~ 80^3
•  » » » 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).
 » How to solve Div2E ?
 » 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?
•  » » 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 ).
•  » » 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.
 » 3 years ago, # | ← Rev. 2 →   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 ?
•  » » 3 years ago, # ^ | ← Rev. 3 →   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.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   I do not understand this statement:"It is obvious that we want to minimize the number of matches used to maximize the answer."Why do we want to minimize the number of matches?
•  » » » » 3 years ago, # ^ | ← Rev. 4 →   there are 2 scenarios for the guy that was beaten: 1. he has played n -1 games 2. he has played n games.now, it's logical to say that the higher the value of n + 1 (defined as the total matches played by the winner) the more people are needed for the winner to play n + 1 matches right?so out of the two possibilities, you would choose the first, you choose greedily to minimise the total number of people needed for the winner to play n +1 matches.hope that helps
 » 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.
 » 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 .
•  » » I send round proposal at 20th December 2015, which is earlier than August 13, 2016.
 » In problem D, shouldn't it be O(n^3/32) instead of O((n/32)^3) ?
•  » » I think so, too
•  » » 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
 » 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.
 » How to solve div 2 E ? Editorial is also missing..
 » 3 years ago, # | ← Rev. 2 →   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.
 » Just curious: why are the limits to Div1C n=100 and k=20 when a O(n*k*k) dynamic programming solution exists?
•  » » 3 years ago, # ^ | ← Rev. 2 →   Maybe author's solution is O(n*2^k)?
•  » » Do you mind explaining your solution? It is particularly short and fast, but I can't understand it. Thanks!
•  » » 3 years ago, # ^ | ← Rev. 6 →   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] = 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].
•  » » » Wow, the representation of state is ... fantastic.
•  » » » 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?
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   .
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   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, dp, dp, dpThe initialization of dp 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.
•  » » » » » Can you elaborate a bit more on setting dp[x] = 1 and dp[x][k+1] = 1?
•  » » » » » » Quote: ----------At the beginning of the dfs, set dp[x] = 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] covers the case when it is colored black, because a node of distance 0 away (in this case x itself) is black.
•  » » » » » » » Thank you!
•  » » » 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?
 » 3 years ago, # | ← Rev. 2 →   "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.
•  » » Can you also share your approach?
•  » » » 3 years ago, # ^ | ← Rev. 2 →   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
•  » » » » Thanks a lot. Great approach. It is really unwieldy.
 » Someone please explain the solution of "Ostap and the tree". What is the recurrence state? The editorial is not very clear. Thanks
 » A non-tex editorial?
 » "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.
 » Can somebody explain the editorial for Div1D? I honestly have no idea what those three ideas are.
•  » » 3 years ago, # ^ | ← Rev. 3 →   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.
•  » » » 3 years ago, # ^ | ← Rev. 3 →   Please ignore. I miss a critical condition in the problem statement.
•  » » » » 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.
•  » » » 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.
 » 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.
•  » » I think the pair (a,b) are the last two parameters of dp table (ie. (i,j)). And also (c,d).
 » 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).
 » 3 years ago, # | ← Rev. 2 →   Can anyone explain the logic of Problem 735C to me.
•  » » Draw a tree and you will know the logic.
 » 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.
 » 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?