### dalex's blog

By dalex, 4 years ago, translation, ,

540A - Combination Lock

For every symbol we should determine how to rotate the disk. This can be done either by formula: min(abs(a[i] - b[i]), 10 - abs(a[i] - b[i])) or even by the two for cycles: in both directions.

540B - School Marks

First count the number of marks that are less than y. If there are more than such marks, we can't satisfy the second condition (about the median), and the answer is -1. Otherwise we can get exactly such number of y marks so that the total number of marks greater than or equal to y is at least (maybe it's already satisfied). This is the required action for satisfying the second condition.

Now, in order not to break the first condition, get the remaining marks as lower as possible — all ones — and check the sum of the marks. If it is greater than x, the answer is -1, otherwise the correct answer is found.

540C - Ice Cave

There are three cases here, though some of them can be merged.

1. If the start and finish cells are equal, let's count the intact neighbours of this cell. If there is one, move there and instantly move back — the answer is YES. Otherwise it's NO.
2. If the start and finish cells are neighbours, the solution depends on the type of the destination cell. If it's cracked, the answer is YES — we can just move there and fall down. Otherwise it must have at least one intact neighbour to get the positive answer — we can move to the finish cell, then to this intact neighbour, and then return to the finish cell.
3. In the general case, check if the path from the start cell to the finish cell exists. If it doesn't, the answer is NO. Otherwise check the type of the destination cell. If it's cracked, it must have at least one intact neighbour, and if it's intact, it must have two intact neighbours.

Let's count the values dp[r][s][p] — the probability of the situation when r rocks, s scissors and p papers are alive. The initial probability is 1, and in order to calculate the others we should perform the transitions.

Imagine we have r rocks, s scissors and p papers. Let's find the probability of the rock killing scissors (the other probabilities are calculated in the same way). The total number of the possible pairs where one species kills the other one is rs + rp + sp, and the number of possible pairs (rock, scissors) is rs. As all meetings are equiprobable, the probability we want to find is . This is the probability with which we go the the state dp[r][s — 1][p], with the number of scissors less by one.

In the end, for example, to get the probability of the event that the rocks are alive, we should sum all values dp[i][0][0] for i from 1 to r (the same goes to the other species).

At first find the position of each element which is used in swap (using map). Now let's find the answer. It consists of the two parts. First part is the number of inversions formed by only whose elements which took part in the swaps. They can be counted by one of the standard ways: mergesort or Fenwick tree. The second part is the number of inversions formed by pairs of elements where one element has been swapped even once, and the other element stayed at his position. Let's consider the following test:

2
2 6
4 8


The global sequence will look as follows: [1 6 3 8 5 2 7 4 9 ...], and here is the array of swapped elements: [6 8 2 4].

Let's understand with which numbers the number 8 forms the inversions. The only elements that could do that are the elements between the initial position of the number 8 (where the number 4 is now) and its current position: [5 2 7]. There are two numbers on this segment which didn't take part in swaps: 5 and 7. The number 2 should not be counted as it took part in the swaps and we have already counted it in the first part of the solution.

So we should take the count of numbers between 8's indices in the global sequence (8 - 4 - 1 = 3) and subtract the count of numbers between its indices in the swaps array (4 - 2 - 1 = 1). We'll get the number of inversions formed by the element 8 and the elements which haven't moved at all, it's 2. Counting this value for all elements which have been swapped at least once, we get the second part of the answer. All operations in the second part of the solution can be performed using sorts and binary searches.

• +103

 » 4 years ago, # |   +5 Well, I think, it would be great if the meanings of 'global sequence' and 'swaps array' is made clear in E's explanation (in paragraph 4 if the test case isn't counted). Do they mean 'the permutation' and 'the swapped elements' in the second paragraph...?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +10 Yeah, "global sequence" == "permutation" and "swaps array" == "the swapped elements" (fixed)
•  » » » 4 years ago, # ^ | ← Rev. 3 →   0 Thanks for fixing, and thanks for the short & clear explanation!
 » 4 years ago, # |   0 Thanks for the editorial! If I may ask quickly about question B, I'm still a bit confused as to how the (n-1)/2 check works for the median. For example if given original grades 3, 5, 6 and minimum median of 6, with value k=50 and x=999, wouldn't it be easy to add 50 values to {3, 5, 6} such that the median exceeds 6 and sum<999? Yet with the editorial it says if at least (n-1)/2 marks are less than the median ie: (3-1)/2 = 1, marks are <= median (which there are since 3, 5, and 6 are <=6}, how does it mean we can return -1?Thanks, sorry if this is a dumb question, I'm just really confused.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Seems like you mistook n and k.In the example where Vova needs 49 (the problem says it's an odd number) tests and finished 3, n = 49, and k = 3. Therefore, (n — 1) / 2 is 24 instead of 1. Then, of course, the answer is -1 if there are 24 marks that are less than y, instead of 1 :)
•  » » 4 years ago, # ^ |   +3 Oh... I see now, the variable "n" was referring to ALL the course marks and not just the ones that were currently given... I didn't read the question very well; but hoping to do better next time, thanks for the problems!
•  » » 4 years ago, # ^ |   0 The number 3 in your formula (3-1)/2 is k, but it must be n, I think that's where you are wrong.
 » 4 years ago, # | ← Rev. 2 →   0 Edit: No need to read this. I have caught my mistake. A reading error :) One more Question for Problem B. If suppose the input is n=5 and k=3 and the minimum median is 4 and the given input is 444. So this fails the (n-1)/2 condition, but still 44444 for example is a solution (assuming sum is large enough). Sorry if it is dumb question(hopefully it is not) :) Did not read the solution carefully. My mistake. No need to reply to this.
•  » » 4 years ago, # ^ |   0 This mistake was fixed about 30 minutes ago, maybe you haven't updated the page since that time? Now that statement says about elements less than y.
•  » » » 4 years ago, # ^ |   0 Yes, I just refreshed and saw that. Then I updated my post, thinking I read wrong. But thanks, I did not read wrong and now it has been corrected. :)
 » 4 years ago, # | ← Rev. 2 →   0 In problem D, if all the meetings are equiprobable the probability that we have minus one scissor would not be instead of . Why we don't count the meetings between the same kind?
•  » » 4 years ago, # ^ |   +8 It's a conditional probability: the probability of the fact that rock kills scissors, given that somebody dies.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +5 But the question D says any two random individuals meet so why isn't 2 people from whole set included as said above by Empty.I mean why is that wrong if we consider the whole people left as our sample space for choosing two people.
•  » » » » 4 years ago, # ^ |   0 If two of the same types are chosen, we are back with the same state as before: nothing changes. We just go again, and we keep going until different types are chosen. Until that happens, nothing changes so the same state is preserved.As dalex said, we only calculate probabilities of the different events given that something changes.
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 But, it will not affect the result of the probabilities?, it would be interesting to see a math proof to show how it works.
•  » » » » » » 4 years ago, # ^ |   0 What's confusing is that we are conditioning this on the fact that a single type wins, and also we are not at all interested in the number of trials this takes. Meaning, we aren't checking the probability of the case that all three types remain (ie: they keep meeting each other). So now, given that after some number of trials, a single type remains, we can effectively ignore all the trials where the same type meets. Again, we could not do this if we were calculating things like:1) number of trials until a specific type wins 2) probability that a single type will win given the possibility of an eternal tie
•  » » » » » » » 4 years ago, # ^ |   +1 I get the same meaning like Empty said.I can't get the correctly example answer in my way.I think in most cases, you should read the problem without ambiguity or less.
•  » » » » » » 4 years ago, # ^ |   +5 math proof can be following:first, lets say thatCrsp — all possible permutations of r s and p pairs. Crr, Css, Cpp — all possible permutations between (r and r), (s and s), (p and p) pairs respectively. Crs, Csp, Crp — all possible permutations between (r and s), (s and p), (r and p) (note that Crs = r *s, Csp = s * p, Crp = r * p)it's evident thatCrsp = Crr + Css + Cpp + Crs + Csp + Crpnow lets say thatPrsp — is a probability for [r, s, p]Pr1sp — is a probability [r — 1, s, p]Prs1p — is a probability [r, s — 1, p]Prsp1 — is a probability [r, s, p — 1]note that meetings between r and r, s and s, p and p doesn't remove anything, so:Prsp = (Prsp * (Crr + Css + Cpp) + Pr1sp * Crp + Prs1p * Crs + Prsp1 * Csp) / Crspmultiply the equation by Crsp and move Prsp * (Crr + Css + Cpp) to the left part:Prsp * (Crsp — Crr — Css — Cpp) = Pr1sp * Crp + Prs1p * Crs + Prsp1 * Cspbut Crsp = Crr + Css + Cpp + Crs + Csp + Crp, so:Prsp * (Crs + Csp + Crp) = Pr1sp * Crp + Prs1p * Crs + Prsp1 * Cspor:Prsp = (Pr1sp * Crp + Prs1p * Crs + Prsp1 * Csp) / (Crs + Csp + Crp)finally we know that Crs = r *s, Csp = s * p, Crp = r * p, so:Prsp = (Pr1sp * (r * p) + Prs1p * (r * s) + Prsp1 * (s * p)) / (r * s + s * p + r * p)
•  » » » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 Nice. We obtain a recursive relation for Prsp. I mean Prsp = A * Prsp + something, a seemingly infinite recursion.
•  » » » » 4 years ago, # ^ | ← Rev. 3 →   +3 I didn't use the conditional probability at all. See my code:10949419. I'm considering all possible pairs of meeting (the sample space is n*(n-1) / 2). However, I still got the same result. When 2 people of the same species meet, no one will die. This will lead to an infinite geometrics series when you calculate the probability that someone dies. So, both methods are fine. If you do it without the conditional probability, but get a different result, you're calculating the probability wrong.
•  » » » » » 4 years ago, # ^ |   0 p[i — 1][j][k] += ppp / (1 — ppp2); can you please explain what i am doing by this ppp / (1 — ppp2); ?
•  » » » » » » 4 years ago, # ^ |   0 Let's say we're interested in P[a rock dies].Case 1: a rock dies in the first meeting. P(1) = i * k / space(i + j + k)Case 2: no one dies in the first meeting, then a rock dies in the second meeting. P(2) = P[no one dies] * P(1).Case 3: no one dies in the first 2 meetings, then a rock dies in the third meeting. P(3) = P[no one dies]^2 * P(1)....P[no one dies] = (space(i) + space(j) + space(k)) / space(i + j + k) = ppp2.So, P[a rock dies] = P(1) + P(2) + ... = P(1) + ppp2 * P(1) + ppp2^2 * P(1) + ppp2^3 * P(1) + ... = P(1) / (1 — ppp2).
•  » » » » » » » 4 years ago, # ^ |   0 clear as water . thanks a lot
•  » » » » » » » 4 years ago, # ^ |   0 Sorry for my bad question, but why P(1) + ppp2 * P(1) + ppp2^2 * P(1) + ppp2^3 * P(1) + ... = P(1) / (1 — ppp2) ?
•  » » » » » » » » 4 years ago, # ^ |   +1
•  » » » » » » » » » 4 years ago, # ^ |   0 I will see it. Thanks a lot !
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Hey, why can't we use this recurrence relation instead: Considering dp[i][j][k] to be a struct with member functions r,s,pdp[i][j][k].r= 1/3.0 *( dp[i][j][k-1].r + dp[i][j-1][k].r + dp[i-1][j][k].r);Why is this logically incorrect? EDIT: Got it. All are taken different. I was taking all the rocks as same.
 » 4 years ago, # |   0 Why my solution for D print wrong answer? I don't see anything different compared to the author's code.10958659
•  » » 4 years ago, # ^ |   +3 10961000It should be i,j,k in bound checking and counting chances
•  » » » 4 years ago, # ^ |   0 Thanks a lot!
 » 4 years ago, # |   0 can someone help me to correct my algorithms for Problem-B(School Marks)My SoutionSolution
•  » » 4 years ago, # ^ |   0 I just want to give you an advice (because I'm not familiar with Java). Your code is a bit complicated, to make it simpler, put the answer(s) to the problem into an array (or a vector). It is much easier to read, and of course, to write the code. Here is my C++ solution (with comments) for reference: pastebinGood luck!:)
 » 4 years ago, # |   0 Thanks for the fast tutorial :)
 » 4 years ago, # |   0 can anyone please explain how to calculate the probability in problem D?
 » 4 years ago, # | ← Rev. 2 →   0 In problems C this case 7 1 X . . . X . . 5 1 3 1 Will fall at the beginning, and will not come up So the answer should be NO, but why the answer is YES Can you explain it ?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +1 From the statement: "the ice on the starting cell is initially cracked".
•  » » » 4 years ago, # ^ |   0 yes thinks. but i think starting will down , I read wrong .
 » 4 years ago, # | ← Rev. 11 →   0 Umm i may have grossly misunderstood problem C here. Probably the word 'side adjacent' or 'fall down'. Help me out here. I used the BFS in a grid technique to get my answer. However, my code gives me 'YES' for example testcase 2. According to my logic, that should right. Here is the case:5 4 .X.. ...X X.X. .... .XX. 5 3 1 1We can go to 1,1 from 5,3 as follows:(5,3)->(4,3)->(4,2)->(3,2)->(2,2)->(2,1)->(1,1)Here is my code: http://ideone.com/JS4OAUWhat's the flaw?
•  » » 4 years ago, # ^ |   0 When you reach (1, 1) for the 1st time, the ice from 'intact' become 'cracked', so you can't fall down yet. You must step on (1, 1) another time to fall down, but there's no room to do this, so the answer is 'NO'.
•  » » » 4 years ago, # ^ |   0 Aaaah I get it. Once I encounter destination, i check if it's 'X'. If it is then possible. If not, then I need to move in an uncracked adjacent direction if possible and come back. Only then will it be possible. Thanks!
 » 4 years ago, # | ← Rev. 2 →   0 ALright so i've applied the concept of a BFS in a grid but my code keeps failing at Test case 21:2 2 .. .X 2 2 1 1Any ideas as to why it fails?
•  » » 4 years ago, # ^ |   0 Ok, I've had a lot of submissions and i'm thinking this cannot be done by BF Ssince there is not way of determinig whether the adjacent edges have been stepped on or not. They may have been discovered but no way to determine that they have been stepped on i believe. Not unless i find the actual shortest path using BFS and backtrack. I'm completely lost. Could someone help me? Is this solvable with BFS?. Here's a C++ code: http://codeforces.com/contest/540/submission/10968998
•  » » » 4 years ago, # ^ |   0 The insight is that you just need to find if the destination is reachable or not. It doesn't matter which path you take. Then at the destination, if you need an extra step on that, you just look around the 4 neighbors to see if at least two of them are dots. So you can move to one dot and move back again (assuming that you might step on another dot, while getting to the destination). There is also an edge case where you start from one of the 4 neighbors. In this case, you only need one dot.
•  » » » » 4 years ago, # ^ |   0 And at least a neighbor dot have visited to ensure it reachable from start point
•  » » » » » 4 years ago, # ^ |   0 No need. We already check if the destination is reachable or not. If it's reachable, it already guarantees at least a neighbor dot has been visited or the starting point is a neighbor.
•  » » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 Can you please tell me what will be the answer for this case? 3 1 X . X 1 1 2 1I think answer will be YES. Path: (1,1)->(2,1)->(1,1)->(2,1)Accepted codes give NO.
•  » » » » » » » 4 years ago, # ^ |   0 you cannot go back to (1,1) because it's already cracked and you'll fall down.
•  » » » » 4 years ago, # ^ | ← Rev. 3 →   0 AC!!!Thank you so much! This particular line 'that you just need to find if the destination is reachable or not. It doesn't matter which path you take. Then at the destination->corner cases' made all the difference :DI have 12 WA submissions in this question. I don't know if you can club the 'neighbours case' given in the editorial using DFS or something. That was really a tought corner case to think of during the contest. Just a vague idea. I had to specially set a case for thatHere is my AC solution: http://codeforces.com/contest/540/submission/10996038
 » 4 years ago, # | ← Rev. 2 →   0 Can anyone tell me why am I getting WA on test 55 problem C? flag=0 if destination cell is intact, else it is 1. Solution
 » 4 years ago, # |   0 Can anyone please explain problem E in detail? I m not able to understand anything
•  » » 4 years ago, # ^ |   0 Which part are you unable to understand. Do you understand the question clearly?
•  » » » 4 years ago, # ^ |   0 I tried to understand his code. CODECan you please tell me what he is doing in the last for loop of the main function and what is the function bs doing.
•  » » » » 4 years ago, # ^ | ← Rev. 4 →   +6 let me explain you the general approach. suppose you have the input as: 2 1 1000000000(10^9) 100 200000000(2*10^8)you obviously cannot create an array of size 10^9. so you create an array with only the elements which were swaped. So the array : arr[] = {1 , 100 ,200000000,1000000000 } we then compress this array as arr[] = {1,2,3,4} (100 is replaced with 2,200000000 with 3,1000000000 with 4) now apply the swaps then we get arr[] = {4,3,2,1} now we need to do 2 things 1) Count the inversions in the compressed array 2) Count the inversions in the original sequence which contains all the elements. Add the results of 1 & 2 you get the answer. How to solve 1 ? We can use merge sort : http://www.geeksforgeeks.org/counting-inversions/ or using a fenwick tree : http://pavelsimo.blogspot.in/2012/09/counting-inversions-in-array-using-BIT.html. ans = 0 number of elements less that 4 and to its right = 3. ans = 3 number of elements less that 3 and to its right = 2. ans = 5 number of elements less that 2 and to its right = 1. ans = 6. so the answer for the first part is 6.Now, How to solve the 2nd part ? (this is the last loop in the editorial solution) Getting back to our original sequence after swaping. seq = 1000000000,2,3,4,...98,99,200000000,101,102.........999999998,999999999,100,1 now how many inversions for 10^9 ? it's original position — current position so 999999999 but we have already counted the inversion made by 200000000,100,1 in the first part where they were compressed, so subtract 3.now inversions for 2*10^8 is also calculated in the same way.Now add the results of the 2 parts. Please go thorough the editorial code. the above is an explanation of that code. It is easy to understand.also have a look at http://codeforces.com/blog/entry/17643#comment-225956 that is what the last loop is for
•  » » » » » 4 years ago, # ^ |   0 Got it. Thanks for such a detailed reply and the links.
•  » » » » » » 4 years ago, # ^ |   0 np
 » 4 years ago, # | ← Rev. 2 →   0 Can some one explain why we need to do the second part in question E. Why cant we simply count the no. Of inversions using merge sort or a fenwick tree?
•  » » 4 years ago, # ^ |   0 I understood it after understanding the question and solution clearly.
•  » » 4 years ago, # ^ |   0 Because you will miss cases where first number is a moved one and the other one did not move.look at first input:after swaps it looks like:2,4,3,1,5....if you just consider pairs in which both elements have moved from original you will get:2,4,1this will give you 2 pairs (2,1) and (4,1) but what about (4,3) ? you will only get this, by the second method that has been explained.You cannot construct the complete tree and expect to iterate through it in timelimit that is set.
•  » » » 4 years ago, # ^ |   0 got it.Thanks :)
 » 4 years ago, # | ← Rev. 2 →   0 I think that for problem E one of our contestants wrote better code. complete perfectness, with many fascinating variables in it.http://codeforces.com/contest/540/submission/10962472
 » 4 years ago, # |   0 is it just me or anyone else?I wanted to practice on this round but find the image in Problem C is a dead image... http://codeforces.com/predownloaded/5b/ff/5bff99f4731b22c9ea00f830072ddfe7040ed80d.png
 » 2 years ago, # |   0 I am trying to understand the following solution 10945934 for 2 days already.I don't get the key part of the solution: for (int i = 0; i < m; i++) { int x = a[i]; int pos = mapchik[x]; ans += abs(b[i] - x) - abs(pos - i); } Could, someone please explain in as much detail as possible, how does this part of the code work?
•  » » 2 years ago, # ^ |   0 I can provide an alternative to this one if you'd like me to :)
•  » » » 2 years ago, # ^ |   0 Sure!I'd be glad to see a different perspective.
 » 3 weeks ago, # |   0 can anyone help with div2c my code failing on 64, can't even see the complete testcase.