### dalex's blog

By dalex, 5 years ago, translation, Hello everyone,

Some days ago we had an annual programming contest in Samara, and yet again we copy it into Codeforces Gyms. The gym contest takes place on Sunday, 17 April, at 11:00 MSK. Site clist.by says that there are no intersections with something important that day.

Previously, it was a team contest, but this year we decided to make it personal. So we ask everyone to participate solo. This is how the results will be the most adequate.

And as usual, Announcement of 2016, IX Samara Regional Intercollegiate Programming Contest  Comments (50)
 » Great :D I really like the previous Samara contests :)
 »
•  » » No, it's Codeforces not Facebook. Tagging your friends won't appear for them in notifications.
•  » » » But what if it did actually work?I mean instead of messaging five different people on CF about the same contest, wouldn't it be nice and convenient if we could just tag them and they receive notification or something?
•  » » » » I don't think that tourist will like it , as he's going to be fully spammed.
•  » » » » » Not if only the people in friend list of tourist are allowed to tag him ;)A person should get notified only if his/her friend tags him/her.PS — BTW I had no idea you replied to my comment till I revisited this page just now. :P May be a person should get notified if someone replies to his/her comment?
•  » » » » » » You will get notified through your email. I think it would be more convenient to get notified here rather than in email.
 » how to solve E?
•  » » 5 years ago, # ^ | ← Rev. 2 →   solutionThe one half of the figure can be translated into the other by some linear transformation. Let's iterate over all possible transformations. There are three important parameters of a transformation:1) translation by X axis from -50 to 50 and by Y axis from -50 to 502) rotation on 0/90/180/270 degrees3) mirroring — yes or noThis gives us a total of 101x101x4x2 transformations.For each transformation, let's consider an oriented graph, where vertices are cells of the figure and edge (u,v) means that cell u is transformed to cell v by this transformation.Our transformations are invertable, so there are at most one incoming and at most one outcoming edge for each vertex.Because of this, the graph is formed by cycles and chains. If all cycles and chains are of even length, we can color the graph vertices in red and blue so that no edge connects vertices of same color. The red and blue parts of graph would mean the two parts of the input figure.If for each transformation there is at least one cycle or chain of odd length, the answer is Impossible.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   Alternate ApproachI had a slightly different approach. I let the top-left point of the figure be a point in the A figure, and brute forced over the corresponding point in the B figure, as well as the rotation and flipping. Then, on the remaining points, I constructed a 2-SAT instance with a variable for each cell and where being part of A is equivalent to being set to true and being part of B is false. if a given cell was a part of A, its corresponding cell (the cell with the same, possibly rotated/flipped, offset relative to the top-left corner of figure B) must be a part of B, and vice versa.
 » Here is my game, on which the Bisection problem from this contest was based.
 » Can anyone show, how to solve "L"-Chess Match.
•  » » 5 years ago, # ^ | ← Rev. 3 →   We want to understand are there any permutations A of a and B of b such that the number of positions i with A[i] > B[i] is more than n / 2. Let's find the worst case(when the number k of such positions is the greatest possible) . It is easy to see in this case some of the k least numbers of b are less than some k numbers of a. So let's find k greedily step by step. Every step needs to find the least number x in b, and the least number y in a which satisfies a condition y > x. So k = the number of times when you can find such y For doing this you may use set or simple sortingJust do this algorithm with (a, b) and (b, a) and print the answerYour text to link here...
•  » » I compared the n/2 + 1 smallest elements of A with the same number of the largest elements of B, element-wise (0th with 0th, 1st with 1st, etc.).
 » Could anyone tell me how to solve pro H and pro J? Thanks in advance.
•  » » Solution JAnswer is YES if there is cycle in graph or cell with three or four free neighbours.
•  » » » 5 years ago, # ^ | ← Rev. 3 →   Is that an arbitrary cycle?
•  » » » » Yes. Code
•  » » » » » Oh, it's really amazing :D. Thank you so much :D.
•  » » » » » What should be the output of this test case?? and why4 5#####...#....#21..#.
•  » » » » » » It's incorrect test. From statement: "From every free cell it's possible to reach every other free cell by moving only through the cells sharing a side."
•  » » » » » » » oh.. Thanks :)
•  » » Solution H SpoilerFor size i we need to find i-th smallest index of friend among friends going to the party of that size. It can be done next way: iterate over party size from 1 to N. For size i: remove from data structure friends, whose maxSize[friend] == i — 1; add to data structure friends, whose minSize[friend] == i; ask data structure i-th smallest index in it. Segment tree can perform these operations with O(logN) complexity, it is enough in this problem.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   In addition to problem HC++ has a cheating data structure — a set with methods order_of_key() and find_by_order(). Link(if you didn't know the cheat above) In this problem such data structure can be emulated by 2 sets, one of which stores the lowest k values, and the other one stores the rest values. Since the find_by_order(k) calls are not arbitrary — parameter k is increasing — it's easy to maintain this data structure by moving the smallest elements from the second set to the first one.Of course, segment tree or (fenwick tree + binary search) also work.
•  » » H. Let's have a look at some K. Let's create array c[] with c[i] = 1 if a[i] <= k <= b[i]. Then the answer for a query with group's size = K is the K-th index i with c[i] = 1 or -1 if there is no K ones in array. For more fast processing the queries(finding k-th positions/updating the cell) we can build a segment tree over the array cNow let's iterate over K from 1 to n. Before answering for a query K we must change c[i] to 1 for every position with a[i] == K (in segment tree, of course). After answering for a query K we also must change c[i] to 0 for every position i with b[i] == K. As you can see, implementation these operations keeps real array c in some moment K in our segment tree.Maybe code is the best explanation
•  » » Another solution H. SpoilerLet's build data structure, that can perform next operations on array 'a': a[l..r] += value; index of max(a[1..n]); a[i] = value; // can be done as a[i] += (value — a[i]); Segment tree can perform all these operations with O(logN) or O(sqrtN) complexity, it is enough in this problem.Idea of solution:Initialize out data structure with values (-1, -2, -3, ..., -n) for indexes 1..n.Iterate over friends from 1 to N, for friend with index i do: a[minSize[friend]..maxSize[friend]] += 1; Let's j = index of max(a[1..n]). If (a[j] < 0) — continue. Else a[j] == 0 — phone calls about party with size j will be stopped at i-th friend — we can update answer[j] = i. Set a[j] = NEGATIVE_INFINITY (some value < -n) — each party size can be stopped only once (we 'remove' party size j from next answer updating).
•  » » Also another solution for His parallel binary search. For every k = 1... N, set initial lower and upper bound as 1 and N. Then iterate over the array times, and using an auxiliary data structure like a BIT narrow the range for each query down as you arrive at its mid-point. This is O(N × log2N), read more about the technique here
 » Can anyone tell me how to solve problem F ?
•  » » 5 years ago, # ^ | ← Rev. 2 →   Solutionp1 is moving with velocity vector v1 and p2 is moving with velocity vector v2. Relative to p1, p2 starts at p2 — p1, and is moving with velocity vector v2 — v1, Then, you want the closest point on this ray to the origin, which is almost the same as the point-line segment distance problem and can be solved using a very similar formula.
•  » » » Thank you :D
•  » » » Alternative solutionTernary search also works well, and is easier to understand, I think.
•  » » » » Function for square of distance between points at the time 't' is a*t^2 + b*t + c. I don't think, that it is harder to find minimum of that function: max(0, -b/2a) — than understand and implement your solution correctly and without problems with precision.
•  » » » » » He meant this one: 17360287But the solution by mkirsche (comment) is the most reliable. There are problems where numerical solutions don't work.
 » 5 years ago, # | ← Rev. 3 →   Can anyone give me some tests for problem F, please? Following operations I did.. Point p1 = new Point(x1, y1), q1 = new Point(x1+vX1, y1+vY1); Point p2 = new Point(x2, y2), q2 = new Point(x2+vX2, y2+vY2);  After that I got two segments... Then I found minimum distance between two segments like this: if(doIntersect(p1,q1,p2,q2)){ System.out.printf("%.15f",0.0); }else{ double d1=Double.MAX_VALUE,d2=Double.MAX_VALUE,d3=Double.MAX_VALUE,d4=Double.MAX_VALUE; if(isActue(p1,p2,q1) && isActue(q1, p2, p1)){ double a =p1.y-q1.y, b = q1.x-p1.x, c = p1.x*q1.y-q1.x*p1.y; d1=((double)abs(a*p2.x+b*p2.y+c))/(sqrt(a*a+b*b)); }else{ d1 = min(distance(p2,p1),distance(p2,q1)); } if(isActue(p1,q2,q1) && isActue(q1, q2, p1)){ double a =p1.y-q1.y, b = q1.x-p1.x, c = p1.x*q1.y-q1.x*p1.y; d2=((double)abs(a*q2.x+b*q2.y+c))/(sqrt(a*a+b*b)); }else{ d2 = min(distance(q2,p1),distance(q2,q1)); } if(isActue(p2,p1,q2) && isActue(q2, p1, p2)){ double a =p2.y-q2.y, b = q2.x-p2.x, c = p2.x*q2.y-q2.x*p2.y; d3=((double)abs(a*p1.x+b*p1.y+c))/(sqrt(a*a+b*b)); }else{ d3 = min(distance(p1,p2),distance(p1,q2)); } if(isActue(p2,q1,q2) && isActue(q2, q1, p2)){ double a =p2.y-q2.y, b = q2.x-p2.x, c = p2.x*q2.y-q2.x*p2.y; d4=((double)abs(a*q1.x+b*q1.y+c))/(sqrt(a*a+b*b)); }else{ d4 = min(distance(q1,p2),distance(q1,q2)); } System.out.printf("%.15f",min(d1, min(d2, min(d3, d4)))); }  Thanks..
 » how to solve I and M ?
•  » » 5 years ago, # ^ | ← Rev. 2 →   Solution for MWe need to make observation that function of different characters in suffix of any string is increasing with length of suffix increasing (in other words, it's monotonic).Then, let dp[i] be the optimal answer for i-th prefix of string, dp = 0. Let's imagine we're standing at the end of i-th prefix of string. Now, we need to find such positions l and r that l is the leftest position at which substring [l; i] has exactly k different characters and r is the rightest position at which substring [r; i] has exactly k different characters. Now, dp[i] = min(dp[l-1]..dp[r-1]), because all substrings from [l; i] to [r; i] are good (due to function mentioned earlier being monotonic), and we can concatenate any of them with shorter prefix. You can get min(dp[l-1]..dp[r-1]) with segment tree. Now we only need to find such l and r. You can do it using two pointers or binary search with some data structure that can answer queries like "how many different characters there are on segment [l..r]". For example, it can be sparse table with bitmasks of length 26 to get O(1) time for query.Total complexity is O(N log N).Sorry for bad English :)
•  » » » thank you :D
 » How to solve Problem A-Treasure Island??Got Wrong Answer in Case No-9. I use dp and dfs. My code is here-17709718
•  » » You can replace '?' with '.' or '#'. But you replace '?' only with '.'
•  » » » My idea is- If all land land position is connected and can be reached from any land position then others '?' mark can be replaced with either '.' or '#'. If all land position is not connected then we can replace '?' mark to '.' so that all land mark become connected. If we need every '?' mark to change in '.' mark to connect all land mark then we have a valid solution and If there remain some extra '?' mark that can be replaced with either '#' or '.' so this situation is ambiguous.And if we can't make all land mark connected after using all '?' mark then this situation is impossible.I am not sure my idea is correct or not. Please Give me some hints/idea or source code.
•  » » » » You can run bfs\dfs from all '.' and mark all reachable '?'. If '.' are not connected then answer is "Impossible" else check for all marked '?': if you replace this '?' with '#' and all '.' are connected then answer is "Ambiguous" (you can replace this '?' with '.' or '#' so that '.' are connected).my source
 » Does anyone know how to solve Problem-A? Get wrong answer at test 14,I used DFS. My code is here-17886458
 » 17886458 Problem A Treasure Island I get wrong answer at test 14 I used dfs
 » how to solve D ?
•  » » It can be solved by processing cities, ordered by descending their populations. You can use map for storing already processed cities by their coordinates.On each step you simply look and compare two cities by their distances to city, processing on this step: nearest from left and nearest from right.
 » How to solve I?
 » How to solve problem I?
•  » » Solution of problem ISort tasks by deadline. Not by "deadline — time" or any other shit.Then process them in this order. If a task requires some dependencies, do them. If you can't do some task in time, output "NO".
•  » » » thank a lot, I was able to solve now.
 » can any one tell me how to solve problem b?