### lucyanna2018's blog

By lucyanna2018, history, 7 years ago,

SRM 721 will be held today.(in less than 18 hours)

Time: 11:00 UTC-4, September 26, 2017

• +62

 » 7 years ago, # |   +26 Remainder: Contest starts in 4 hours, registration is open now.
•  » » 7 years ago, # ^ |   +3 Reminder: Contest starts in 1 hours. Now # of registerants is 351.
•  » » 7 years ago, # ^ |   +23 Were you the writer?
•  » » » 7 years ago, # ^ |   0 I'm not the writer.
 » 7 years ago, # |   0 How to solve Div 1 250?
•  » » 7 years ago, # ^ |   +5 I used binary search to find element on day d1.If both left and right sum will turn out larger than needed, decrease high, and vice versa for smaller. If one is larger, the other smaller no solution is possible.Left and right sum with one given element can be checked by computing min and max possible sum with n*(n+1)/2
 » 7 years ago, # |   +31 Wow, that was probably the easiest SRM I have participated in.
 » 7 years ago, # |   +6 Could someone explain how the Div1 800 could be converted to Max-Flows?
•  » » 7 years ago, # ^ |   +38 Instead of moving tokens one by one at each time, you can imagine you move all tokens simultaneously, since if two tokens cross while moving, you can just uncross them.Here's the max flow graph.Create two nodes for every (node, time) pair (let's denote this a(n, t), b(n, t), meaning node n at time t). Create a source and sink. All edge capacities in the following will be 1. For every node x with a token, connect source to a(x, 0). For every node x without a token, connect b(x, t) to the sink. For every edge in the graph (x, y) and every time j, 0 ≤ j < t, connect b(x, j) to a(y, j + 1) (and similarly b(y, j) to a(x, j + 1). For every node x and every time j, 0 ≤ j < t, connect a(x, j) to b(x, j), and b(x, j) to a(x, j + 1). The max flow in this graph is the answer.You need two classes of nodes a, b because you need to encode the constraint "every node only has 1 token at each time".
•  » » » 7 years ago, # ^ |   +13 How does having two classes of nodes resolve the constraint issue while one class itself couldn't?
•  » » » » 7 years ago, # ^ |   +5 This is encoded in the edge a(x, j) to b(x, j).
•  » » » » 7 years ago, # ^ |   +33 This separation into two classes is a trick that essentially assigns capacities to vertices. See https://en.wikipedia.org/wiki/Maximum_flow_problem#Maximum_flow_problem_with_vertex_capacities
 » 7 years ago, # |   +3 how to solve div2 500?
•  » » 7 years ago, # ^ |   -23 I will try to give a hint. Probably, that will be enough. Every time you see a large problem space, you don't want to go through all of that space, but you want to consider only special points.In the case of this problem the space is the days: [1, 2, 3, ..., d1 + d2].We don't want to go through all of that space, but we want to consider only one special place.
 » 7 years ago, # |   0 Is there a reason to require that the graph in Div1 Hard is specifically a tree other than making the contestants explore the possibility of the solution being some kind of dynamic programming?
•  » » 7 years ago, # ^ |   0 Good question! One (admittedly weak) reason is that it is a natural way to reduce the number of edges in your flow graph, which helps in doing worst-case analysis for the maxflow algorithm (Dinic runs in time E^(3/2) for unit-capacity networks, for example).
 » 7 years ago, # |   -31 I've won the match!Aijuuuuuuuuuuuuuna would say some gauchos criollos in my area :) !!!! Poder gaucho FTW!
 » 7 years ago, # |   0 I misread div1 B and started thinking about this problem:Given n and d, what is the maximum number of pairs that can have a distance d between them?Does it have a nice solution?
 » 7 years ago, # |   0 Any idea about div2 500 problem ( RememberWordsEasy ) ?
•  » » 7 years ago, # ^ | ← Rev. 4 →   +2 Vary the number of words (say d1) learnt on the last day of the sem1 from 0 to w1. Let the number of words learnt in the first day of the sem2 be d2. Given d1 words learnt on the last day, let the maximum number of words learnt in sem1 be hi, and minimum be lo. For w1 words to be learnt in the first sem, the sufficient condition is hi >= w1 >= lo. For each d1 vary d2 from d1-1 to d1+1. Find a similar hi and lo here as well for sem2 and check conditions.To find hi and lo for a given w [words read on first day(or last)] and d [the number of days], hi = w + w+1 + .. (w+d-1)/2. And lo is w + w-1 + .. max(w-i+1, 0) ..d terms. So you get hi and lo in O(1). So the only thing that takes time is varying d1 from 0 to w1.
 » 7 years ago, # |   0 Hello, this comment can be off topic to this blog, sorry for that.When I enter TopCoder Arena I can't read problems, it keeps loading, is there any way to fix it? Is problem in my internet/pc?Thanks in advance.
 » 7 years ago, # |   +25 Why did cgy4ever stop posting about SRM announcements?