### Medo.'s blog

By Medo., history, 3 years ago,  Comments (30)
 » Reminder: Contest starts in 2h. Let’s enjoy!
 » Can you please announce the round a bit earlier next time?I really like the TC problems but one literally needs to ruin his plans to be able to participate. I guess this is one of the main reasons for the low participation.
 » How to solve div2 800?
•  » » Calculate the probability of picking each item and then apply bitmask dp on states.http://blog.quantitations.com/stochastic%20processes/2013/02/07/expected-number-of-steps-of-a-markov-process/Answer will be dp
 » In div1 450, is there any simple solution or do we greedily do a bfs using only vertices on edges(is this right)??
•  » » Bfs on edges definitely works (just passed in practice room). I doubt there's a simpler way to do it since this is already pretty straightforward.
 » How to solve div2 2nd and 3rd problem?
•  » » 3 years ago, # ^ | ← Rev. 2 →   For div2 medium, you can use dynamic programming (there are non DP ways to solve it as well). The state consists of the following: the index of the rectangle you are currently processing the "intersection rectangle" of all the rectangles you've included so far For example, if I have rectangles 0,4,6,8 (the 0 is x1, the 4 is y1, the 6 is x2, the 8 is y2) and 5,2,9,5, then the intersection rectangle would be 5,4,6,5.So for each state, we either try to include the current rectangle, or we skip it. We take the best of those two results. When we include the current rectangle, we have to calculate a new intersection rectangle based on the current state's intersection rectangle and the rectangle at the current index. If there's no intersection rectangle for these two, then we can't use this rectangle. Otherwise, we pass this new intersecting rectangle to the next state.
•  » » » Can we solve this problem using Coordinate Compression in 2D ?
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   Yes, this is what I did.
•  » » » » The division winner (who was also in my room) wrote the code below (retyped by me without macros). I too solved it in O(n^3) by sorting coordinates but I used midpoints of each adjacent pair of coordinates to ensure I avoided corner/edge overlaps. I don't understand why the code below works despite staring at it for a while. Can anyone help explain? Why does he take "-1" of the x2 but then check x+1 <= x2 in the inner loop? (I can see the 'x' in the inner loop includes both x1/x2). int X, Y, XS, YS, n, s, x, y; int maxOverlap(vector x1, vector y1, vector x2, vector y2) { n = x1.size(); XS = YS = 0; for (int i = 0; i <= n-1; i++) { X[++XS] = x1[i]; X[++XS] = x2[i]-1; Y[++YS] = y1[i]; Y[++YS] = y2[i]-1; } ans = 0; for (int i = 1; i <= XS; i++) { for (int j = 1; j <= YS; j++) { int x = X[i], y = Y[j]; int s = 0; for (int j = 0; j <= n-1; j++) { if (x >= x1[j] && x+1 <= x2[j] && y >= y1[j] && y+1 <= y2[j]) ++s; } ans = max(ans, s); } } return ans; } 
•  » » » » » This is my code,I was the winner of SRM729 div2:) x,y means a square of size 1*1 at (x,y,x+1,y+1). I check every "useful" pair of x,y and updata the ans. Sorry for poor English.
•  » » » » » » Fantastic, what a great method. I thought it was "point within rectangle" but now I see, it is actually checking "1x1 square within rectangle".I can see this "Useful 1x1 square" idea being applicable in many such problems.Thanks for explaining! And congrats on your win :-)
•  » » Video solution to Div2 Problem 2 here: https://www.youtube.com/watch?v=WG7RguNSNC8
 » What is the corner case for div2 500? I see many people (including me) failed system tests.
 » 4 indian members get sponsorship for hello india programming camp (2 Div1, 2 Div2 (Logic TC??))This fag probably 2nd div2 top, registered account like 15 mins before start Well played!
•  » » We wanted to give a chance to the newbies too as the camp has three divisions of difficulty. Moreover, it is easy to verify 2 genuine coders out of the Div II list easily, their identity and information will be required for booking their bootcamp tickets. Also as per the rules, individuals are only allowed to have one account. If they create a new account, all of accounts may be suspended. Rest assured we will make sure deserving and genuine competitors get the chance
•  » » » 3 years ago, # ^ | ← Rev. 2 →   What makes you think that all people who are in div2 are newbies? The Indian guys who did well in div2 aren't. It's just that they don't take part in SRMs. I know in the end it's your wish, but it doesn't sound fair at all.
 » 3 years ago, # | ← Rev. 2 →   How to solve div1-800?If I understand correctly, the problem can be reduced to the following (which, I believe, should be easier):Given up to 100 positive integers (each up to 1018), you can replace value at position i with XOR of some values from its prefix (we have to include a[i] into XOR, and can decide separately for each of a..a[i - 1] whether to include it or not), find LIS.However, I haven't found a way to solve this [hopefully correctly] reduced version.
•  » » 3 years ago, # ^ | ← Rev. 2 →   The key subtask is: given numbers x, b, and a set of numbers yi, what is the smallest number of form x xor (xor of some subset of {yi}) that is  ≥ b?If we solve that one, we can apply it inside the standard DP to find the LIS.And to solve the subtask, we iterate over which bit will be the first difference with b, and then we have a subtask: a set of numbers yi, find a xor of its subset with certain higher-order bits and the remaining bits as low as possible. This is essentially solving a system of equations in Z/2Z, so we use Gaussian elimination in the right order (from higher bits to lower bits).
 » My screencast with commentary: https://youtu.be/Ugf5kbxmV_8
 » 3 years ago, # | ← Rev. 2 →   In div 2 — 800 points. I don't understand why the result of {2, 2} is 3.0. Can anyone tell me about the way to caculate the result.
 » For Div1 Medium, is there a proof that it is sufficient to use only cells on edges?
•  » » 3 years ago, # ^ | ← Rev. 3 →   Yes, actually the proof is not so hard. Suppose that there is a valid path, . vi is the coordinate of where the frog is on i-th step. Note that the place v2, v3, ..., vk - 1 is not necessarily on edge of the square. Let's think about "modifying" the path with following way, that it remains still valid, and the length of path is same or improved. Look at the following picture: This represents two cases (left one is case #1, and right is #2). The first case is that "x and y is both increasing or decreasing". In this case, you can compress the path, from , to . If you do this, the number of vertices decrease by one, and also the distance remains greater than or equal to d. The second case is the other pattern. Without loss of generality (because you can rotate arbitrarily), suppose that the y-coordinate of vx + 1 is greater than vx one and vx + 2 one. In this case, if you change the y-coordinate of vx + 1 into n - 1, obviously the distance will increase or stay equal so distance remains greater than or equal to d, and obviously the number of vertices doesn't change. If you repeat the process until no change occurs for any x, v2, v3, ..., vk - 1 will be on the edge of the square. Proved.
•  » » » Thank you for your clear explanation! I noticed that I tried to prove the following statement instead:If x → y → z is a valid path, there exists a cell y' on edges such that x → y' → z is a valid path.Thus I could't think of a shortcut in the left case.By the way, the statement above is correct. It seems important here that the given board is square-shaped.
 » Is there any editorial of problem div 2 — 800 points?
 » Can somebody please help me in Div 2 800 point problem. The problem is based on Expected Value and there is no editorial for this problem. Thank You.
•  » » 19 months ago, # ^ | ← Rev. 2 →   Simple trick for expected value can be used here — Dp[mask] = turns to complete game from mask. Go in backward direction with base case Dp[S] = 0. Acyclic recurrence code dp
•  » » » Thanks, Can you please explain "Acyclic recurrence code dp". I don't know this.