### SirirNicheBirirDokan's blog

By SirirNicheBirirDokan, 6 years ago,

Let's discuss problems.

How to solve the geography problem?

| Write comment?
 » 6 years ago, # | ← Rev. 2 →   +19 How to solve problem 2, 11?
•  » » 6 years ago, # ^ | ← Rev. 3 →   +14 The last problem: if after 6 hours the rocket is higher than the eclyptic, send it then; else the rocket crosses eclyptics, and that moment can be found with binary search; to find the position after t seconds, rotate point (0,-cos(phi),sin(phi)) by t/day_length*2pi around z-axis, then rotate it by -alpha around y-axis, and z-coordinate will be oriented distance to the eclyptic
•  » » 6 years ago, # ^ | ← Rev. 5 →   +5 Problem 11. Trigonometry. Find ratio between A1-L and A2-L (tangets). Then calculate arcsine.
 » 6 years ago, # |   +25 How to solve 2, 6 and 7?
•  » » 6 years ago, # ^ | ← Rev. 2 →   +5 2) Just determine time when item starts decoding and time when it's leaving the buffer than you get segments [enters_buffer, exits_buffer]. After just found point in time where maximum segments intersects. How to find this "enters_buffer": iterate from the end to begin and keep time when current item enters buffer, when iterating just update this smth like enters_buffer = min(enters_buffer, i * d); enters_buffer -= time_of_decoding[i]. There is a case when we have "IBBI" we know that 3 must be decoded before 1 so in our loop we skip 3 and update "enters_buffer" after iterating 1. So how to find "exits_buffer": for every item u iterate for each item v where v depends of u and choose maximum of enters_buffer[v] + time_of_decoding[v]
•  » » 6 years ago, # ^ |   +5 6) First of all, parse all input and calculate number of fields which take 1, 2, 4 and 8 bytes.For minimal size we can order fields in non-increasing order and then add padding so that the total size is divided by max-size field.Maximal and average sizes can be found using dynamic programming. Let's consider dp[r][c1][c2][c4][c8] be avg/max size of current structure where r is current size mod 8 and cX -- number of remaining fields with size X. When calculating average we also maintaining probability to get to each state. Transitions are done by inserting fields of all possible sizes. Then, for maximum we need to find max for all r among dp[r][0][0][0][0] and average equals sum of all dp[r][0][0][0][0] + probability[r] * padding(r) where padding(r) -- is padding we need to add to the resulting structure having remainder r.The dynamics can be optimized by using only two layers
•  » » » 6 years ago, # ^ |   +10 But i thought that numbers can be very big when we calculating avg so we can have loss of precision. Why they are remaining small?
•  » » » » 6 years ago, # ^ |   0 As long as we have only 100 fields, maximal total size is 800 and average is less or equals to it
•  » » » » » 6 years ago, # ^ |   0 Yes, but probability equals to x over y, I thought that y can be very large, and x very small
 » 6 years ago, # |   +61 I don't have ever seen single interesting problem, which is related to computer architecture with long description of buffer or memory, and I think this time is no exception...
•  » » 6 years ago, # ^ |   +8 I don't have ever seen single interesting problem with long description, and I think this time is no exception...
 » 6 years ago, # |   0 How to solve 3?
•  » » 6 years ago, # ^ | ← Rev. 2 →   +2 Kuhn or flows. With one of them it’s an easy task
•  » » 6 years ago, # ^ | ← Rev. 2 →   +8 Discard all packages that has at least one version that doesn't make conflict with any other package.Now you are left with some packages where all versions make conflict with some other package. You want to choose exactly one version from each package, such that you also choose no more that 1 version from a conflict set. That is exactly like finding a matching, where all left nodes are included.So, for this part, make a bipartite graph, with left nodes representing packages, and right nodes representing conflict sets. Add and edge between X and Y, if package X is in conflict set Y. Then answer is Yes, iff max bipartite matching = number of packages.Solution can be constructed by looking at matched edges, and taking a version that is in both package and conflict set.
•  » » 6 years ago, # ^ |   0 1.At first, check if there are any versions, which are not included in any conflict. Update answer for those programms.2.Then, make a bipartite graph with conflicts in the left part and programms(which you don't have answers yet) in the right(and write a version on the every edge for output). Find maximum matching in that graph. That's it.
•  » » 6 years ago, # ^ |   -8 Greedy algorithm with random.
 » 6 years ago, # |   0 How to solve 9?
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 for each i = 0, 1, ..., n / s memorize the segments that are near point i * s, to answer the query with point x look at these ssegments at x / s - 1, x / s and x / s + 1; i took s as 4
•  » » 6 years ago, # ^ |   +23 Actually I only make all the coordinate 1E6 times larger and use a Segment Tree and Pass the problem. So I am wondering what's the official solution idea, Since my solution has nothing to do with the randomability.
•  » » » 6 years ago, # ^ |   0 Hmm, interesting. What kind of Segment Tree did you use? Don't you need to squeeze coordinates before?
•  » » » » 6 years ago, # ^ |   +15 My Segment Tree's range is [-1E11,2E11]. You don't have to squeeze coordinates if you maintain the Segment Tree by the way that only generates necessary nodes.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 Well... The canonical solution is to build a segment tree with standard segment-nodes [k;k + 2s) for 2s|k. For each input interval, first find the best matching level s, then save its index into one or two segment-nodes which it intersects in this level. For a point query, go through all the nodes containing the point, and check all the intervals in it. This gives O(N) space in worst case and average O(NlogN) time with the provided distribution.The much simpler solution is the one described by polingy below, which needs O(NlogN) time and space on average.Of course, all sorts of other segment trees work as well.
•  » » 6 years ago, # ^ |   +29 We solved it with "naive" algorithm.For every interval, [L, R] add it to vector for indices , to answer point query x, look at the vector corresp. to and just check how many intervals x lies inside.It's not hard to show that expected runtime is ; I don't know how to show that it's quick with high probability.
•  » » » 6 years ago, # ^ |   -27 it is quick because the average length of any interval is 4
•  » » » 6 years ago, # ^ |   +2 It was said in the statement that radius of a segment R is generated with this — . So expected value of R is — . So, sum of lengths of segments is ~ .
•  » » 6 years ago, # ^ |   0 We solved it with "interval tree"
•  » » 6 years ago, # ^ |   0 Can also be solved with Binary Search Tree. Notice that number of segments that contains X = total number of segments — (number of segments that has right side  < X + number of segments that has left side  > X). So we can use two BSTs, one for storing left sides another for right, and keep sub-tree sum for the ids and size of sub-trees in each node. Since the data is random, so we don't need BBST like Splay-Tree / Treap, normal BST is enough.
 » 6 years ago, # |   +1 Does anyone WA on 8th testcase of problem 7? And I am also wondering is this Gp of Eurasia or Gp of Siberia? Quite comfusing.
•  » » 6 years ago, # ^ |   +13 I could pass the 8th test only by rewring computation from floating numbers to integers. But unfortunetaly, couldnt have time to squeze in TL.
 » 6 years ago, # | ← Rev. 2 →   +2 About testcases in 4:Store the sets for each component with indexes of bad irredeemable connection. When you need to merge it, first check from smaller set that there is no intersection. Then add small set to biggest. This solution should got TL, but during checking if we break inside the loop, when we found intersection got to AC. But it is easy constract test case where it should have O(n^2) comparison. Isnt it?I thought key idea would be dont compare two components more than once. But to get AC it is not needed. Is it bad testcases?
•  » » 6 years ago, # ^ |   +14 You meant Ω(n2), didn’t you?
 » 6 years ago, # |   +11 How to solve 4?
•  » » 6 years ago, # ^ |   0 use dsu, but while unioning sets, append one with lesser sets of conflict vertices to one with bigger; after unioning sets, if you appended B to A, then for each conflict vertex in B's set change B to A in that set
 » 6 years ago, # |   +5 I have two solutions of problem F that differ only in the following lines:Solution 1: scanf("%*[^;]"); scanf(";"); Solution 2: scanf("%*[^;];"); The first solution gets OK while the second fails on test 1. Can someone explain that?
 » 6 years ago, # |   0 How to solve 10?
•  » » 6 years ago, # ^ |   +5 Dijkstra on hex graph: build graph -> don't forget to add reverse edges for rivers -> run Dijkstra -> AC.
•  » » » 6 years ago, # ^ |   0 What is the state of vertex?
•  » » » » 6 years ago, # ^ |   0 dist[x][y] = (minimal number of steps, maximum energy left)
 » 6 years ago, # |   -8 Thanks problemsetters for beautiful combination of ML and TL in problem 6 !!!11!11 I can't use neither static array nor vector)
•  » » 6 years ago, # ^ |   +21 You can emulate many dimensional arrays on 1-dimensional. It is very easy.