### ItsNear's blog

By ItsNear, history, 19 months ago, ,  Tutorial of Codeforces Round #488 by NEAR (Div. 1) Tutorial of Codeforces Round #488 by NEAR (Div. 2) Comments (79)
 » Fastest editorial ever! Kudos!
 » 3 8 8 9 8 5 9 2 8 4 8 3 2 6 4 2 4 3 3 7 3 6 1 6 how is this in problem D give a "0",can someone explain?
•  » » If person A has 8 9 as pair, then he knows that the hidden number is 8, since 9 doesn't appear in person B's communication. If he has the pair 8 5 the same thing hold, because 5 doesn't appear in B's communication. And if he has the pair 9 2, then the hidden number is 2, since 9 doesn't appear. So in any case person A will know the hidden number.You can do a similar reasoning for person B.
 » 19 months ago, # | ← Rev. 2 →   ItsNear Can you please upload the solutions(code) also. Thanks in advance :)
 » In F you are only considering gates that always return 0 in one of the configurations. Why is it impossible that all gates sometimes return 0 and sometimes 1 in both configurations but still all gates return 0 in one configuration for each input?
•  » » 19 months ago, # ^ | ← Rev. 4 →   Edit: LHiC below challenged the author solution and the proof below. I will keep my incorrect proof here for history. You can only use the 6 second-layer gate kinds described in the editorial (all other setups return 1 in both original and inverted configuration at least for one input). If you have at least one of the first four kinds, such gate would return 1 for all inputs in one of the configurations, so you must have all gates return 0 in the other configuration for all inputs. You must include at least one gate of the first four kinds, because if you only include the gates of the last two kinds, then for the input of all ones all the gates in the second layer will return 0 in both original and inverted configuration, and the output of the circuit will be different in two configurations. Does it make sense?
 » 19 months ago, # | ← Rev. 2 →   Another Div2C/Div1A solution: If there exists a point in squares intersection, it's also exists a point in squares intersection with integer coordinates. Then we can just bruteforce all points, because absolute values of their coordinates are small (<=100).
•  » » how can you check if a point lies in the rotated square ?
•  » » » point lies in the rotated square if manhattan distance from it to square's center is equal or less to the half of square's diagonal
•  » » » » Does this apply to a rectangle or a square with rotations other than 45 degrees? Can you also provide a proof of why does manhattan distance works? I've seen this method in Errichto solution here but couldn't prove it.
•  » » » » » It applies only to square rotated by 45.Proof, why it works:If you look to its sides, you can see that the manhattan distance from any point on the side to the center of square is constant and equal to half of the diagonal. So if a point is farther than that distance, it is obviously not in the square.
•  » » » » » » 19 months ago, # ^ | ← Rev. 9 →   The Manhattan distance property should apply to any square if that square is rotated around its center using geometric transformation such that its two diagonals are aligned with the coordinates of the 2D plane. The proof is a simple geometry exercise.
•  » » » I've checked only all points of rotated square, their coordinates are follows some uncomplicated regularities. For example, you can calculate length of diagonal and then start to bruteforce points one by one (first the higher one, then line of three points below, line of five etc.).
 » In Careful Maneuvering, my solution tries all possible meaningful positions for two spaceships, and then for each such combinations does simulation, so it is O(N5).In Compute Power, I'm using the fact that values of b[i] are small to implement a solution that sorts tasks by power and then does knapsack dp[pref][i][j][sum_of_b] — where parameters are length of prefix, number of used computers with one task of higher power, number of used computers with one task of power equal to power of current task, sum of b[i] for first tasks on used computers so far, and the value of dp is total power used, so it is something like 50*50*50*5000. Was any of these solutions considered during round preparation? What was the intended verdict for them? I'm confused because constraints look weird in both problems: it's like they aren't high enough to make it challenging to get AC with such solutions, but at the same time they are high enough to make it clear that intended solution is most likely different. Both of the solutions which I mentioned are not so hard to transform into right ones — but, at the same time, they are not so hard to cut off as well :)Or is it about JavaBlitz thing, and they indeed don't pass in Java? :)
•  » » 19 months ago, # ^ | ← Rev. 2 →   How did you simulate in O(n)? I had to write a binary search resulting in O(n^5log(n)) which gave tle. for each spaceship I found if the resulting spaceship it hits is present or not and its range of indices so that I mark them hit. (I guess it is more than n^5logn, maybe n^6)
•  » » » Coordinates are small, so we can keep an array of flags to answer query "do we have a ship at position P?" in O(1) instead of doing binary search.
 » O(1) solution to Div2C without having to check for any intersections or handling many cases: Fix the center square, and see what locations the center of the diagonal square can be at. An octagon with 45 degree sides emerges. See below picture. The square in the middle is what is given to us, it has side length 2s. The diagonal square has a diagonal of length 2d. I drew 2 diagonal squares so you can see, if it is inside the octagon, then it intersects, otherwise it does not. We can represent this octagon as the union of two squares centered at the center of the first square, one parallel to the coordinate axes with side length s+d, and one at 45 degrees with side length 2s+d. Resulting code is short and clean: http://codeforces.com/contest/994/submission/39320205
 » can someone explain how this solution works: http://codeforces.com/contest/994/submission/39313692thank you!
 » 19 months ago, # | ← Rev. 4 →   im not sure why div 2 B complexity is O(nk), isn't time for storing set of maximum coins is O(n)? then it should be O(n²) overall complexity. pls help i still cant understand the solution.edit: now i understand the solution (keep updating the set and store the answer for each knight)
•  » » if it it O(n^2) then it surely gives TLE as n=1e5 O(n^2) > 1 sec
•  » » » yeah, its ok i got the idea for the O(nk) solution
 » 19 months ago, # | ← Rev. 5 →   My approach for solving problem 994C - Два квадрата was: Intersect the bounding box of the diagonal square [the smallest square whose sides are parallel to the X and Y axes and contains the diagonal square] with the first square whose sides are already parallel to the X and Y axes. Search inside the resulting intersection rectangle if it is non-empty for a point that the diagonal square contains. If such point exists, then the answer is "YES". Otherwise, the answer is "NO". Since all the given integer numbers are between -100 and 100, the intersection rectangle can contain at most 40,000 points. 39333649
 » Don't last two kinds return 1 on all ones? nand(nand(1, 1), or(1, 1)) = 1. That makes author's solution incorrect on test: 3 6 6 nor xx. nor x.x nor .xx and xx. and x.x and .xx and x...x. and x....x and .x.x.. and .x...x and ..xx.. and ..x.x. All gates are of kind 5 (both participants' solutions return 0).
•  » » Yep, this is a major mess up. I both misinterpreted the output of my script that was searching for the gate configurations, and evidently when I was stressing the solution against the naive, didn't get all the way up to 6 gates in both layers...Would be interesting then to hear how Um_nik and Errichto solved it.
•  » » » And damn, should have listened to those guys and thanked MikeMirzayanov in the announcement...
•  » » » » So what happens afterwards? Is it rated at all?
•  » » » » » Yes, because there is a solution and the tests are not affected.
•  » » » My solution:There are two types of bad situations: on some input first circuit returns 1, but second returns 0 and vice versa.First type means that there is an input on which some gate in second layer of first circuit returns 1 and some (maybe other) gate in second layer of first circuit returns 1. Let's iterate over all ordered pairs of gates and check if there is such input. A pair of gates depends only on 8 variables, so we can check all possible values. If there is such input, we will draw an edge between these two gates. To satisfy first condition the set of remaining gates in our circuit must be an independent set in this graph.Second type means that there is an input on which all gates in second layer of both circuits return 0. Let's suppose (for now) that we only want to check if this condition is satisfied for the whole circuit. Let's say that outputs of two gates in the first layer which are inputs for some gate in second layer are X1, X2. So we want OP(X1, X2) = NOT(OP(NOT(X1), NOT(X2))) = 0. It is easy to see that if OP is OR/AND then we want X1 = X2 = 0, and if OP is NOR/NAND then we want X1 = X2 = 1. So, our condition is "some gates in first layer should be equal to given values". Since gates are only OR/AND/NOR/NAND it is some instance of 2-SAT problem.Now let's notice that that for second type some subset of a set is always worse than the whole set (we have less restrictions). So if we have some set on which there are no bad situations of first type than there is no need to check its subsets.So, the whole solution is: find all maximal independent sets (using Bron-Kerbosch algorithm), then for each of them check if 2-SAT has a solution.Yeah, it probably should be TL :)Initially I thought that we only need 2-SAT once in the beginning, wrote the solution, it doesn't work on second sample. I have like 20 minutes left, so have to come up with some tweaks.
•  » » » » What if all maximal independent sets do not satisfy the 2-SAT? Do you need to check smaller independent sets?
•  » » » » » Maybe I used incorrect word. By 'maximal' I mean maximal by inclusion (I know that there are 'maximal' and 'maximum' but I don't know which is which :) ). If all of them do not satisfy then the answer is -1.
•  » » » » » 19 months ago, # ^ | ← Rev. 2 →   If I understand Um_nik's solution right, 2-sat is used to find an input that would result in all the gates in some maximal set return zero in both configurations. If 2-sat finds such input, then such maximal set doesn't satisfy the condition from the problem statement, and naturally all its subsets do not satisfy it either (so no need to check them).Otherwise such a maximal subset is an answer candidate.
•  » » » » I think that the number of maximum sets will be at most two. My reasoning:Let's split all the setups of gates in the second layer into four categories: ['nand(nand(a, b), and(a, b))', 'nand(or(a, b), nor(a, b))', 'or(nand(a, b), and(a, b))', 'or(or(a, b), nor(a, b))'] All these setups return 1 for all inputs in the original configuration, and 0 for all inputs in the inverted. ['and(nand(a, b), and(a, b))', 'and(or(a, b), nor(a, b))', 'nor(nand(a, b), and(a, b))', 'nor(or(a, b), nor(a, b))'] All these setups return 0 for all inputs in the original configuration, and 1 for all inputs in the inverted. ['and(and(a, b), nor(a, b))', 'nor(nand(a, b), or(a, b))', 'and(and(a, b), nor(a, c))', 'nor(nand(a, b), or(a, c))'] All these setups return 0 for all inputs in the inverted configuration, and something that depends on the input in the original ['and(and(a, b), nor(a, b))', 'nor(nand(a, b), or(a, b))', 'and(and(a, b), nor(a, c))', 'nor(nand(a, b), or(a, c))'] All these setups return 0 for all inputs in the original configuration, and something that depends on the input in the invertedAll other setups return 1 in both original and inverted configuration for at least one input, and as such can't be in the resulting set.Now the maximal set might be one of the two forms: All the gates from the first category and all the gates from the third category. If there's at least one gate from the first category, such set satisfies the condition from the problem statement (since such gate return 1 for all the inputs in the original config). If there's no gate from the first category, then we need to run 2-sat to see if for every input there's at least one gate from the third configuration that returns 1 (this step was missing in my original incorrect solution) All the gates from the second category and all the gates from the fourth. Similar reasoning -- if at least one gate of second category exists, it's a good set, otherwise run 2-sat to check it. Now we need to show that no other maximal set exists.Gates from the first category can't possibly be with gates from the fourth, because gates from the first category always return 1 in the original configuration, and gates from the fourth return 1 for some inputs in the inverted, thus there's at least one input for which one of them returns 1 in one configuration, and one in another.Similarly gates from the second category can't be with gates from third.Finally, to show that the gates from the third can't be with the gates from the fourth, it is enough to show that if the input is all ones, the gates from the third category return 1 in the original configuration and the gates from the fourth category return 1 in the inverted configuration.If I haven't messed up anything above, your solution fits into TL since it will consider at most two maximal sets.
•  » » » Is it possible to add that test to the main tests for upsolving? if I hadn't read this comment I would have probably thought that my wrong solution is correct and never went back to it.
 » Please take this constructively — all the problem statements other than C could have been written in a much clearer way.
 » can someone please explain me the last sample test of Div2 D.what i have understand : second person is sharing (1, 2) and (1, 3) so, it must have either (x,1) or (2, 3) and third time he is sharing (2, 3) and as this pair doesn't contain the both the numbers of second player. so, he must have (x, 1) but for (2, 3) to contain a number from his own pair (i.e(1,x)) he must have either (1, 2) or (1, 3) which will contradicts the first two pairs. so, how the given pairs are valid?PS: sorry if someone finds this silly. but i'm really confused.
•  » » I can't understand you explanation . In this test , first player showed(1,2),(4,5) , which means one of them is real and the other one is a "made-up" pair . The same for the second player . if (1,2) in first and (1,3) in second is true , the common one is 1 . If (1,2) in first is true and (2,3) in second is true , the common number is 2 . So the observer could not determine the common number . For players , the second player could determine the number because he know which of the (2,3) and (1,3) is true . But for first player , he only knows his (1,2) is true , but he could not determine the second player's pair . So the answer is "-1" . Note pair(4,5) couldn't be the true one because there's no common number in the second player's pairs . The same for the second player's (1,2) because there's either two common numbers(if the first player's pair is (1,2) ) or no common numbers(the first player's pair is (4,5) ).
•  » » » thanks a lot for this explanation.
 » 19 months ago, # | ← Rev. 2 →   I solved E by using divide and conquer and FFT that is O(nlog^2). FFT solution : http://codeforces.com/contest/993/submission/39324259 And I get TLE by using NTT instead of FFT. NTT solution(TLE) : http://codeforces.com/contest/993/submission/39317762 Can only body explain why there are so much difference between these two solutions?
•  » » 19 months ago, # ^ | ← Rev. 2 →   NTT uses a lot of / and % operations, so it is slower than FFT.
•  » » » thanks Next time I'll try to avoid using NTT
 » div1B can be solved in O(n*m) Why n,m<=12? During the contest,I thought I misunderstood the problem at first because n,m was so small.
•  » » Maybe it's just for confusing you. :)
 » RTE CODE my code shows RTE for some reason. can someone please tell why. When I replaced b[i] with variable t. It passed all test cases. this is so weird AC CODE
•  » » You accessed from b to b[m — 1], but the size of b is set to n, and m can be larger than n.
•  » » » Yeah, I realized it a few minutes after. That costed me a lot XD
 » My approach for Div2B was using dynamic programming.First, sort the knights by the power in ascending order. Then, let themdp[n][k] : the maximum number of coins the n-th knight has after he kills k other knights.coin[n] : the number of coins the n-th knight initially has.Finally,dp[n] = coin[n]dp[n][k] = MAX(dp[n - 1][k] - coin[n - 1], dp[n - 1][k - 1]) + coin[n]
•  » » I think the correct version of last of your DP equation should be : dp[n][k] = MAX(dp[n - 1][k] , dp[n - 1][k - 1] + coin[n-1]) + coin[n]and also this is not any different from author's solution.
•  » » » OOPS! sorry, I looked at it again. Mine is wrong, yours is correct. I actually didn't account for the last term (coin[n]) in your equation.
 » In Div1 D , I saw the word"rounded up" . The google translation told me it means"1.4 -> 1 , 1.6->2" . Then I got wronganswer on test 8 and it turns out that we need to find the smallest integer which is bigger or equal than the answer .
•  » » I actually believe it's a translation mistakes, cause author is (I guess) russian. "Round up" is a literall translation from russian, which in russian means "to round UP", so there is no ambiguity. Author just didn't notice it's a phrasal verb in English.
•  » » » May be this problem. The first time I saw this word , I thought it means "to Round UP" . Then I checked on google and discovered that it's a phrase . Anyway I'm not able to solve this problem during the contest and it doesn't matter too much for me . :)
 » Thanks for this fast editorial, ItsNear Senpai!!
 » There is solution for div1D without binary search and it have no mess with precision at all.First of all lets gather vectors of bi for each unique ai and sort it from bigger to smaller.dpi, j, k = minsuma where i step (we are iterating for unique ai) ;j is how many computers can take second task(with this sorting it is valid) ;k is how many processors is used;minsuma is how minimum sum of A;so shortly we calculate minimum sum of A for each valid possible sum of B. To do this on each step we try to update go from every state and we try to use some tasks as second and as first on computer. How to choose what tasks with equal ai will be second or first we need to conseder that tasks with bigger bi must go to first. Thus we only iterate size of tasks that will go as first.Complecity see submission for deatils : 39313087
 » Another solution for problem B div 2 using just pair and array is to save the power and idx in array of pairs and save the coins in another array then sort the pairs (power and idx) increasingly according to power. then go from smallest power to largest every iteration check only if the current coin is larger than the smallest coin in another array called coin its dimension is only 10 then sort this array and sum to get the max coins
 » My solution for div1C: compute bitmasks of destroyed spaceships (1 bitmask for each side) for each position of a small spaceship. Precompute popcounts of numbers up to 220. Then try all pairs of these positions, compute ANDs of corresponding bitmask pairs, get the number of destroyed spaceships as the sum of 6 popcounts and take the maximum. Complexity O(N2M2(N + M) / 60).
•  » » 19 months ago, # ^ | ← Rev. 2 →   I solved with bitmask too, basicly generate all possible intersections points while updating its leftmask and rightmask with OR operation. iterate over all the possible pair of points, the answer is the maximum of popcount(leftmask[p1] | leftmask[p2]) + popcount(rightmask[p1] | rightmask[p2]).
 » how test case 37 results -1 for div 2 D problem??
 » elegant Python solution for Div2/B, sub: 39338337 R = lambda: map(int, input().split()) n, k = R() v = [] t = *n for p, c, i in sorted(zip(R(), R(), range(n))): t[i] = sum(v)+c v += [c] v = sorted(v)[::-1] if len(v) > k: v.pop() print(' '.join(map(str, t))) 
 » please someone provide DIV2 (b) solution.
 » 19 months ago, # | ← Rev. 3 →   994C — Two Squares can be accepted with randomized algorithm with some special judge. My Code (If you are a lucky dog, you may pass with very short code. But for me, I think it's impossible xD
 » Giving testcase 8 WA in Div2 C and following the editorial only... Can anyone help?http://codeforces.com/contest/994/submission/39349217
•  » » Draw the two squares, then it should be obvious why your code doesn't work.
•  » » I think you forget to check centers that mentioned in the editorial in first sentence.Input seems like this.
 » Why in the "Two squares" test: 3 6 3 7 4 7 4 6 5 0 0 5 5 10 10 5 breaks many people, and the testing system produces a "Full Solution"?
 » In the editorial of Div 2 D, there is actually no need to check for the point 2. Its because candidateship is commutative. If we found "a" as a candidate while iterating over the first array, we must be having some pair (a, b) in the first array and a pair (a, c) in the other one (where b != c) . But while iterating over the 2nd array, when we would have come across the pair (a, c) , we would have found the corresponding pair (a, b) in the other array. This means that a candidate found for the first array while iterating over it will also be found as a candidate for the second array while iterating over it, and vice versa. Therefore, the first and the second array have the same candidates.
 » In Div2 B, I keep getting WA on test 10, can someone tell me what am I doing wrong? Here's my code. http://codeforces.com/contest/994/submission/39424745
•  » » Overflow. "#define vi vector ". You save the result which has got the type "long long" into the "vector res(n)".
•  » » » Oh... FML ;-; Thank you.
 » What's the complexity of Problem F?
 » Oh my god,n^2*m^2*(m+n) can pass div.1 C. See my code 39886117
 » Can someone help why the following solution for Div 2 B gets a Runtime Error on test 62 — http://codeforces.com/contest/994/submission/41742929
•  » » 17 months ago, # ^ | ← Rev. 2 →   There was wrong answer. It was late in night so I wrote a very stupid thing.
 » 17 months ago, # | ← Rev. 2 →   Hi guys, I am trying to solve 994B and getting 'Time limit exceeded' on test 52. Can someone look into my code and help me?http://codeforces.com/contest/994/submission/41903805
 » I solved div1E for practice, and got WA in test 43 for float-precision. I changed it to long double and got AC. Then I read the editorial and found that simple doubles should not pass. However, after looking at the top 3 contestants from the round, Um_nik, Errichto, and scott_wu, the three of them used simple doubles and got AC! Here are the submissions, respectively: 39303954, 39298654, 39301524. I know the contest was ages ago, but I'm really curious to how they handled precision, since long doubles are unbearably slow! Can someone help me understand this please?
•  » » 15 months ago, # ^ | ← Rev. 2 →   The reason you have bad precision is the way you compute the roots of one:for(int i = 2; i < (1 << LG); i++) ur[i] = ur[i - 1] * ur;The precision errors stacks up when you compute every next uri. Instead, compute them independently:for(int i = 2; i < (1 << LG); i++) ur[i] = polar(1.0, i * M_PI * 2 / (1 << LG));You get AC with this change: http://codeforces.com/contest/993/submission/44679848. The disadvantage is that this preprocessing is much slower, but it's only done once so it's ok. Also, you can even start from i = 0 in this loop and not initialize ur0 and ur1 in a special way. I will soon create a tutorial about precision errors, maybe with some examples about FFT.
•  » » » That's very helpful, thank you very much. I will anxiously await you post, it sounds interesting. You could also consider writing a post on efficient FFT's, your solution is intriguingly fast.
•  » » » Also looking forward to your post about precision errors :)
 » For C coordinates when we rotate the origin by 45 degrees can be found using the formula. » i solved div2E for practise. seems like there exists another solution using bitmasks and stuff. can anyone explain what the other solution is? what do i need to read for that?