### NelsonMondialu's blog

By NelsonMondialu, 8 years ago,

463A - Caisa and Sugar. This is a simple implementation problem.

Sample solution.

463B - Caisa and Pylons. We have to use greedy method. Start from the first element and pass all the elements in order(also update by the energy).When energy < 0, add abs(energy) to solution and energy becomes 0 or we can find the answer by binary search.

Sample solution.

463C - Gargari and Bishops. We preprocess the sum for all the diagonals(principals and secondary diagonals) in two arrays(so that for every element i,j we can find sum of elements which are attacked in O(1) time).Also for avoiding the intersection,we need to find two cells so that for one the sum of row and column is even and for the other one the sum of row and column is odd.Finally,we analyze every cell ,we see if the sum of row and column is even or odd,and update that two positions(solutions).

Sample solution.

463D - Gargari and Permutations.We can build a directed acyclic graph with n nodes.If j is after i in all vectors then we add in graph edge (i,j).Now we have to find the longest path in this graph. Another way is using dp.

Sample solution with graph.

Sample solution with dp.

463E - Caisa and Tree. We use an array of dynamic stacks for every prime factor.We start a DFS from node 1.For node 1 we decompose its value in prime factors and push it to every prime factor's stack.To answer the question for x,we need to see the y (y belongs to the chain from 1 to x) that has a common prime factor with x,so the stacks will help us to see the earliest update(so the nearest y). For every x ,we decompose x to prime factors,look in the array and see the earliest update of the prime factors' stacks(if exists,of course). Also when we get back to fathers recursively,we need to pop from the prime factors' stacks. For every update we have to start dfs again.

Sample solution.

• -15

 » 8 years ago, # |   +3 Can someone explain the another way "Dp" of problem D ??
•  » » 8 years ago, # ^ |   +9 dp[i] = longest common subsequence which is finished at position i (i is position in first vector) dp[i] = max(dp[j])+1 with j < i and position of a[j] < position of a[i] in all vectors. The answer is maximum value of dp.
•  » » » 8 years ago, # ^ |   0 is a[i] and a[j] are the element from first vector ???
•  » » » » 8 years ago, # ^ |   0 yes
•  » » » » » 8 years ago, # ^ |   0 if you explain it with more detail then it is more understandable and may be then i can get it clearly
•  » » » » » » 8 years ago, # ^ | ← Rev. 2 →   0 i get it "get AC" AFTER 3WA :)
 » 8 years ago, # | ← Rev. 2 →   0 Problem D: it can be solved by DP...Well... Do you mind explaining?People who read the editorial are the people who didnt solve the problem, saying that it can be solved in a certain way is not helpful
•  » » 8 years ago, # ^ |   0 Firstly lets create a position array for each sequence and call it pos[k][n]. In this array we store the positions of each of the n numbers (from 1 to n) to know where they occur in each of the sub sequences. Now the dp solutions starts. dp[i] marks the maximum length common sequence we can generate by using the first i elements of the first sequence. For this we iterate over all possible previous numbers (j) and see if we can extend dp[j] to dp[i]. This can be done only when positions of number a[j] is less than positions of a[i] for each of the sequence. Then we can extend j to i. Finally we take the maximum of values in dp array. Refer to my solution in the contest. Link
•  » » » 8 years ago, # ^ |   0 Nice explation. Thanks a ton!
•  » » » 5 years ago, # ^ |   0 thanks for this :)
 » 8 years ago, # |   +16 B question can be done by just taking the maximum of all the heights :D
•  » » 8 years ago, # ^ |   0 Can anyone explain why this solution works?
•  » » » 8 years ago, # ^ |   +15 the law of conservation of energy（http://en.wikipedia.org/wiki/Conservation_of_energy）.You need to have max(h) energy at the beginning to make sure that you can pass through the highest point.
•  » » » » 7 years ago, # ^ |   0 My Idea : for h[]= { 0, 3, 4, 3, 2, 4 } energy required from 0->1= h[0]-h[1] energy required from 1->2= h[1]-h[2] energy required from 2->3= h[2]-h[3] energy required from 3->4= h[3]-h[4] energy required from 4->5= h[4]-h[5]and when i add the energy i always get h[5] ?
•  » » » 8 years ago, # ^ |   +3 Just to be good guy. In order to climb to the a[i], you need to have starting energy more or equal to a[i]-a[i-1]+a[i-1]-a[i-2]+.... which equals to a[i], and you need to be able to climb to a[i] for 0<=i
•  » » » 8 years ago, # ^ |   0 You can consider it in my way below: 1. you must confirm that height sequence 1 2 2 3 3 4 4 4 is same with 1 2 3 4 right? if you think it's good, then you can prepare the input sequence as totally distinct element in it:) 2. troughs undo peaks right? 3. so finally the max height left:) hope my explanation helps u:)
•  » » 8 years ago, # ^ |   0 yep, you said what I want to say:)
•  » » 3 years ago, # ^ |   0 First sample : i can add 2 to 3 thus it becomes 5. Then 5-4 =energy 1 4-3=e 1+1=2 3-2=e 2+1=3 2-4=-2 Thus energy 3-2=1 So paid should 3 right? How it can be 4!!
 » 8 years ago, # |   0 E's test is too weak.Many brute force can pass.And can you share the standard solution of E?
•  » » 8 years ago, # ^ |   0 Maybe they pass because TL is 10 sec and there are no more than 50 queries that changes the value of a vertex. Isn't it?
•  » » » 8 years ago, # ^ |   0 Yes. It means that the queries of type 2 are not more than 50.But if there are many queries of type 1, then it will TLE.The case is: the tree is a long link with all nodes is 2 with the deepest node is 3. And I query the last node every time.Look at this data maker:(use python to make it) n = 100000 print n, n for i in range(n - 1): print 2, print 3 for i in range(n - 1): print i + 1, i + 2 for i in range(n): print 1, n 
 » 8 years ago, # | ← Rev. 3 →   +32 463A — Caisa and Sugar. This is a simple implementation problem.This is a simple way to offend people. I'm sure that there are some coders who couldn't get AC on this problem and they will probably feel like sh*t if they come here and read "this is easy". If you don't want to write editorial for this problem don't even mention it.
•  » » 8 years ago, # ^ |   0 This is CODEFORCES!!!1111oneoneone
 » 8 years ago, # | ← Rev. 2 →   -8 I would never thought that brute force can pass problem E.
•  » » 8 years ago, # ^ |   -8 Me, too... The test must be too weak.
 » 8 years ago, # |   0 Is there anyway to solve problem D if the k arrays aren't permutations of 1, 2, .. n ?
•  » » 8 years ago, # ^ |   0 I believe complexity would become an issue — see here. (If I'm reading that correctly, it looks like it's O(kn + 1)).
•  » » 8 years ago, # ^ |   0 I doubt, except exponential, you can find longest common subsequence in O(len1*len2) and keep searching for same one in other arrays, that would be O(d*n^2) best case, but if you have more longest common subsequences it could lead to exponential time complexity.
 » 8 years ago, # | ← Rev. 3 →   0 Nice(!!!) Tutorial !!!
 » 8 years ago, # | ← Rev. 2 →   +16 I don't think the explanation of A is helpful. If people didn't get it, it should be explained, and I saw people who got problem D that didn't get AC on problem A.The solution is to check each type of sugar and determine if you can buy it. If you can, the number of sweets you will receive is 100 - yi for that type of sugar, except for the case where yi = 0, in which case you will receive 0 (thank you to yash.15296 for catching that this was missing). The goal is to maximize that value on a type of sugar you can buy.Pseudocode: ans = -1 for i = 0..n: if s > x[i]: if y[i] == 0: ans = max(ans, 0) else: ans = max(ans, 100 - y[i]) if s == x[i] and y[i] == 0: ans = max(ans, 0) The first condition (s > x[i]) is the case in which you have more money than the sugar costs, and the second condition (s == x[i] and y[i] == 0) is the case in which you have exactly enough to buy the sugar.Note that initializing ans = -1 will also handle the case where you can't buy any of the types of sugar, since neither condition will ever be met and therefore the value of ans will never change.One thing that I feel could've been stated better in the problem was that you are only buying one unit of sugar, regardless of how much money you have, so in the case 1 6 2 60 The answer is 40 (buying one unit will leave you with 3 dollars and 40 sweets) and not 80 (if you could buy two units, you would receive 0 dollars and 80 sweets), even though you can logically afford two units of that type of sugar.
•  » » 8 years ago, # ^ |   +10 Hack : 1 9 8 0
•  » » » 8 years ago, # ^ |   0 Thanks, good catch. I knew I was missing something.
•  » » 8 years ago, # ^ |   +2 Thanks! It seems like almost everyone who submitted and didn't pass pretests got it wrong because of You are only buying one unit of sugar, regardless of how much money you have. , myself included.
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 Not quite correct; as stated, the hack 1 9 8 0 works (expected 0, output 100). You need to modify the cases: for i from 0 to n-1 if x[i] <= s and y[i] == 0 answer = max(answer, 0) else, if x[i] < s answer = max(answer, 100 - y[i]) This handles the case where if the cents is 0: you should enter the first case, where you receive 0 sweets, instead of the second case where you (wrongly) receive 100 sweets.EDIT: I should refresh the page before posting a comment.
 » 8 years ago, # | ← Rev. 3 →   0 Please answer to this questions, NelsonMondialu!Problem C:We preprocess the sum for all the diagonals(principals and secondary diagonals) in two arrays(so that for every element i,j we can find sum of elements which are attacked in O(1) time)How? For what time complexity do you do the preprocessing?...we analyze every cell... What particularly do you analyze? The PH of the sell?Give some examples please!P.S. One of the worst editorials I've ever seen.
•  » » 8 years ago, # ^ |   +1 Couldn't agree more. A real explanation or pseudo-code of problem C would be highly appreciated. I actually thought pretty much the same solution but I couldn't implement it.
•  » » 8 years ago, # ^ |   0 Read a[i][j] Lets call the \ diagonals as 0 and / diagonals as 1. Make some way of hashing the diagonals, and then just do dia[0/1][numOfDiagonal]+=a[i][j], where numOfDiagonal is some number that depends on i and j, and could be achieved only by i and j in that diagonal. That would be the preprocess.
 » 8 years ago, # |   0 Tutorials are supposed to help people who couldn't figure out the solution or the implementation part of the question. That is definitely not an editorial.
 » 8 years ago, # |   0 Can you provide link to your solutions!!!
 » 8 years ago, # |   +1 Am sorry but these are really poor Editorials :(
 » 8 years ago, # |   0 Can anyone explain, How to solve the problem D with graph, I am not getting the editorial??
•  » » 8 years ago, # ^ | ← Rev. 3 →   0 Another way to think about problem D is like this : Consider two sequences, how to find out the lcs in an optimal way. Because all the numbers are distinct in the first sequence, one of the way is to re-number the second sequence according as the order in which the numbers appear in the first sequence. Then an lcs of both is just a longest increasing sub-sequence of the second(because after re-numbering the first sequence becomes 1,2,3...,n). For multiple sequences we have to just find lis in one of them according to re-numbering in all the other sequences. Or re-numbering implies for the standard lis update equation dp[i] = dp[j]+1 if i>j & a[i]>a[j], we have also to make sure that a[i] and a[j] appear in the same order in all other sequences. That's why we have to make such graph. Or just check these conditions in all other sequences. Time = O(n*n*k). For a simple implementation see : http://codeforces.com/contest/463/submission/7631750
 » 8 years ago, # |   0 Someone explain me Problem C please..
•  » » 8 years ago, # ^ |   0 Well that's how an editorial should look like. +1 from me
•  » » » 8 years ago, # ^ |   +7 Well , maybe only freshmen knows what other freshmen needs.A professional may think it weird to make any mistake on div 2 problem A and B ,so they think explanations are unnecessary and skip those.I'm just a Newbie in China ,which is not joking.
•  » » 8 years ago, # ^ |   0 Thanks a lot for this comment... :) C is much easier to me now... :D
•  » » 8 years ago, # ^ |   0 Very friendly for understanding, thx a lot!
•  » » 7 years ago, # ^ |   0 Thanks! Your solution was very helpful.
•  » » 7 years ago, # ^ |   0 great explanation!!
 » 8 years ago, # |   0 can any explain problem E in detail :) ???
•  » » 8 years ago, # ^ | ← Rev. 4 →   +10 I'll post my solution for E and try to do a "mini-editorial" for it. You can easily notice that the value for any node is maximum 2*10^6. We can keep a binary search tree (Set in c++) for every number from 1 to 2*10^6. In each set we will keep a pair (depth[node], node) in order to find in O(1) the deepest node which has the divisor according to the set.Example: node = 1; value[node] = 6; ( 6 = 2*3 ) depth[node] = 2; At one point we will have: (2,1) in Set[2] and (2,1) in Set[3] We modify these sets in the DFS as follows: void DFS (int node) { ans[node] = pair(-1,-1) /// we might not have an answer for this node for ( every prime divisor of value[node] ) if ( Set[ prime divisor] not empty ) /// we have found a node x that has the same divisor and our node ans[node] = max( ans[node], last_element_in_set ); for ( every prime divisor of value[node] ) Set[ prime divisor ].insert( pair( depth[node], node ) ); for ( every every child of node ) DFS(child) for ( every prime divisor of value[node] ) Set[ prime divisor ].erase( pair( depth[node], node ) ); } !!!Node: these sets are gives the nodes sorted by their depthWhen we find an update query we just run DFS(1) and done! If something is not clear just ask!
•  » » » 8 years ago, # ^ |   0 The DFS may be 'segmentation fault' if the tree is a long link. If the length is 80000, and it break.
•  » » » 8 years ago, # ^ |   0 what is the work of this line ans[node] = max( ans[node], last_element_in_set ); ?
•  » » » » 8 years ago, # ^ |   0 ans[node] is a pair (depth, node number).The bigger pair means that's a node with greater depth.
•  » » » 8 years ago, # ^ |   0 thanx AlexandruValeanu
 » 8 years ago, # | ← Rev. 2 →   0 Can someone explain in detail how to built the graph in problem D?
•  » » 8 years ago, # ^ | ← Rev. 3 →   +3 for ( i = 1, N ) for ( j = 1, N ) if ( j is after i in all permutations ) addEdge( i, j ) /// i->j 
•  » » 8 years ago, # ^ | ← Rev. 3 →   0 Acc to what I hav understood take every pair of i and j and see if i comes after j in all the given permutations.If yes,add edge i-j in the new graph.This makes the graph to find the longest path.Pl tell if I am wrong somewhere.EDIT:Sorry didn't read Alexandru's reply which is the same as what I said.
 » 8 years ago, # |   +5 Some idea of understanding Problem D(graph theory solution):If i is in front of j in all k sequences then we add in graph a directed edge (i,j).--what does the edge mean?what happends if we go through the edges?Well ,think carefully:If i is in front of j in all k sequences,then subsequence [i,j] is a common subsequence of those k sequences.and if we walk through the edges, and line up nodes on the path we walk through, it would be a common subsequence of those k senquence.=====================================================and obviously,the graph is a DAG(directed acyclic graph),to make it simple,I'll use in_front_of(x,y) to replace the statement x is in front of y in all k sequencesif in_front_of(i,j) is true ,it's obvious that in_front_of(j,i) is false. Also if in_front_of(i,j) is T,in_front_of(j,k) is T,it's obvious that in_front_of(k,i) is false=====================================================with those in mind ,the longest path on this DAG will be the solution we need in this problem.There are several ways to find a longest path on DAG, I'd like to use Topological sorting.My solution:7647678
 » 8 years ago, # |   0 OMG,it's intresting to find that tutorial of every problem in this round is rewritten by other users, seems everyone's unsatisfied with this brief official tutorial.I think it's just so so,all right,I don't like it,well , I hate it!
 » 8 years ago, # |   0 My solution for E always get TLE on test 7. The approach is the same as the tutorial, so I think there must be something wrong with my code, but I couldn't find it out. Does anyone know why? Here is my solution: 7650731
•  » » 8 years ago, # ^ |   0 Find my mistake after lunch... Line 43: if (prime[i] > val) break; should be: if (prime[i] * prime[i] > val) break; And in fact, the prime factors of a node can be saved, we just need to change one node after each update.
•  » » » 4 years ago, # ^ |   0 Weak test cases in Problem E , Even brute force is passing all TCs
 » 8 years ago, # |   +39 Is this going to be the 1st editorial with contribution <=0?
•  » » 8 years ago, # ^ |   0 you bet Good editorials need to have clear in-depth explanations guided with proofs and well explained methods. fchirica has these kind of editorials and he is rewarded with +200. I personally like these editorials the best
 » 8 years ago, # | ← Rev. 2 →   +13 In statement of problem E the sentence "there are no more than 50 queries that changes the value of a vertex" is ambiguous. It can be understood as "there are no more than 50 queries that changes the value of --each-- vertex", that is equivalent to say "for each vertex, there are no more than 50 queries that change the value of such vertex". With this interpretation, this condition is useless. In fact, I understood the statement in such a way, and have spend one day to solve the problem without taking advantage of the restriction.
•  » » 8 years ago, # ^ |   0 AFAIK "value of a vertex" should mean that we don't care which vertex it is; the word "each" is used precisely to differentiate your understanding from what was meant here.
•  » » » 8 years ago, # ^ |   0 Well, it is ambiguous. The normal way to say that would be "there are no more than 50 queries of type 2". Anyway, now I am happy to have such a missunderstanding, since I have been able to solve the problem even without such a restriction.
•  » » » » 8 years ago, # ^ | ← Rev. 2 →   0 Yeah, it does sound strange — just pointing out that it is a gramatically correct wording (unlike other cases where the statement is unclear because nobody can make sense of it).
•  » » » » » 8 years ago, # ^ |   0 Ok, since my english is very far from perfect, I believe you, and will try to improve my understanding.
 » 8 years ago, # |   0 In problem D, lets consider if k is 5, then can we find LCS of of first two sequences, store and and then find LCS of this result and the next sequence. Are there any issues with such an approach?
•  » » 8 years ago, # ^ |   0 1 2 3 4 5 6 7 8 9 7 8 9 1 2 3 4 5 6 6 5 4 3 2 1 7 8 9 correct answer: 7 8 9your answer: 1
•  » » » 8 years ago, # ^ |   0 Oh okay thanks
 » 8 years ago, # | ← Rev. 3 →   0 sry, didn't look at dates...
 » 6 years ago, # |   0 why O(n^2) solution is getting tle in Problem c? can anybody tell me. i am doing precompution along with taking input in n^2 and then updating the solution for even and odd sum.
 » 5 years ago, # |   0 Solution to C: First let me put the question in this way... Consider a chessboard with back and white checks alternatively.You have a white and a black bishop(by this we assure both of them will never attack the same position). So now you have to put them in such a way that they both can earn maximum points together. Solution: It is pretty simple to see that the sum can be maximum only when the individual bishops fetch maximum money(as they both do not intersect each others path). So first precalculate the diagonal sum for all individual cells(which is equal to the money the bishop would have fetched if put at that location). Then you just find the maximum for white bishop and that for black bishop separately and add them up to get the answer. Solution
 » 4 years ago, # |   0 why this code is wrong ? http://codeforces.com/contest/463/submission/41503320
•  » » 4 years ago, # ^ |   0 Print the length of the longest ""common"" subsequence.
•  » » » 4 years ago, # ^ |   0 i do that ! did you see my code ?
•  » » » » 4 years ago, # ^ |   0 Of course I read your code. What you are calculating is the longest "Longest Increasing Subsequnce", not the length of the Longest "" Common "" Subsequence.I can hack your solution even k=1.hack : 3 1 3 2 1
•  » » » » » 4 years ago, # ^ |   +8 thank you for that and i hope to be like you in the future
 » 4 years ago, # |   0 In Problem C there is a problem with the testcases. for the case: 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0The answer 1 1 1 2 is not accepted.
 » 4 years ago, # |   0 What is wrong for my submission of B? http://codeforces.com/contest/463/submission/49780076
 » 3 years ago, # | ← Rev. 2 →   0 In B: Case 2 I dont need to pay dollar if have to pay it would be 1 dollar 3 4 4 4. Here starting energy is 0 So increased 1 4-4=0 Energy still 1 Again 4-4=0 Energy still 1 There is no loss of energy So i should pay 1 dollar only!Either question is wrong or test case!
 » 22 months ago, # |   0 Can anyone tell me Why this code is wrong. https://codeforces.com/contest/463/submission/98275804 Thanks in advance. Plz do reply
•  » » 22 months ago, # ^ |   0 IT is for Div2C_
•  » » 22 months ago, # ^ |   0 Edit: This code is passing test 9 https://codeforces.com/contest/463/submission/98395832 But it is giving TLE on test 10 Plz any one can help Any help is appreciated Thanks in advance
 » 9 months ago, # |   0 Can someone explain [problem:A. Caisa and Sugar] i can't understand the problem!