### 1e9's blog

By 1e9, 9 years ago, Topcoder SRM 642 will take place on 17th dec at 02:00 AM GMT. I was hoping for chrome to announce it.

I hope that most of us do multiple successful challenge and submission and after contest we do nice discussion on problems.

Good Luck to all. srm, Comments (24)
| Write comment?
 » 9 years ago, # | ← Rev. 2 →   It's at 7:30 AM IST, I think tomorrow my day starts with this contest.And ofcourse ends with CodeForces Round #283(10:00 PM — 12:00 PM IST)
 » TC ContestApplet is not working from about 12 hours. It just stucks at opening screen. Anyone else facing similar problem?
•  » » Resolved: It was using proxy settings from Firefox and not the system settings!
 » 9 years ago, # | ← Rev. 2 →   Is it true that in div1-hard is sufficient to take only one of two cells: opposite of the known one and the one just close to it? My solution failed and I'm not sure if the bug is in the idea or in the implementation.
•  » » No, that doesn't work. There are cases where you may want to choose some other cell.
•  » » » Oh, my bad. Thanks. It seemed quite feasible :(
•  » » » Can you provide a small example?
•  » » » » 9 years ago, # ^ | ← Rev. 3 →   N=10, s={6,3,3} In this particular case, if we see a score of 1 at position 0, it is optimal to open the cell at position 3.
 » How solve div1 B?
•  » » For each tree, only the last cut affects the final tree height. So we will assign to each tree the last cut (when, which device to cut that tree). We can solve it by max matching min cost (We have N trees and (number of devices)*time suggesions for last cut). Construct this graph is not difficult, but it will too slow as the number of edges is about 150^3. So the key idea to optimize is: For each tree, you know which last cut is good, which is bad (which makes the final tree height smaller is better). And you only need consider ~200 best last cut. The number of edges is now about 150^2.
•  » » 9 years ago, # ^ | ← Rev. 5 →   I'll try to explain solution without flows.If tree doesn't need to be cut it adds to answer value h[i] + T * a[i]If it cuts in turn t from the end on device j, the value is dev[j] + t * a[i].(Here you can see, if set of trees and devices used on some turn is fixed, order of matching doesn't affect the result).Consider subset of trees that are going to be cut. Parameter h[i] significant no more. Now we can sort trees using parameter a[i] and say that we can cut trees only in that order.On the other hand, if we consider one turn, and look on set of devices that are used on this turn, its obvious that optimal way to use subset with the smallest values of dev[j]. So we can sort all the devices and say that we are using some its prefix on each turn. So the last what is needed is to find how much devices should be used on each turn.Now you can see the following dp can be used to solve this problem. dp[t][i][j] — minimal value for cutting i trees in t turns, where j is the number of devices used on current turn.from the state (t, i, j) we can go to:(t, i + 1, j) //do not cut tree i, costs h[i] + T * a[i](t, i + 1, j + 1) // cut tree i with device j with value dev[j] + t * a[i](t + 1, i, 0) // step in the next turnThe answer is the cheapest path from state (0, 0, 0) to (T, n, 0).
 » Do you know, why solutions with 10^7 cout << int << ' ' << double << endl; doesn't fail on TL?
•  » » 9 years ago, # ^ | ← Rev. 3 →   Maybe, you use cin.tie(0) and ios::sync_with_stdio(false)?
•  » » » 9 years ago, # ^ | ← Rev. 2 →   endl flushes regardless and flush is slow regardless, so no.I'd assume the servers are just fast or optimize/something this stuff. Or something is broken.
•  » » » » Have you seen that guy? As I remember you was in my room. He failed systests, but I don't know it was due TL or he had another bug.
•  » » » It wasn't me. I tried challenge one guy and I don't understand why it was unsuccessful.
 » WTF I did in 500 div 2 problem. I managed to implement this BFS in the contest and I spent 1 hour to do it and then I saw that it has a simple O(n^2) solution with 2 nested loops. It seems like I need to sleep more, lol!
 » What is the solution of Div.1C?
•  » » 9 years ago, # ^ | ← Rev. 3 →   All of Alice's picks are equivalent, say she picks 0. For every number of points P the host says section 0 has, you need to find best section B for Bob to choose.Expected value if you choose B is: For every turn: thisprob = probability that 0 is picked on this turn expected += thisprob * expected increase of B for every subsegment that includes 0 expected += (1 - thisprob) * expected increase of B for every subsegment that does not include 0 Then calculate this for all Bs and have Bob pick the best one. Calculating the actual probabilities is just a simple DP exercise, but if you can't figure out how to do it you can check my code on the practice room (I failed during the contest because of MLE :'( )
 » 9 years ago, # | ← Rev. 3 →   What is the solution for Div2 1000? I felt it could be solved using flow, but that seemed complicated.Can someone please help? SRM 642 — Div2 1000
•  » » You had to do a binary search on the answer. Description of the check function: First construct a new graph, where a edge has 0 cost if road's height is more than king's shoe, else it is equal to (diff)^2 where diff=(height of king's shoe)-(road height) --> that is the minimum you would have to pay in case you want to traverse that road. Then as the number of nodes were small (50 at max.), you can apply floyd-warshall, to find the minimum cost to go from node '0' to node 'n-1'. If this cost <=king's budget, then the size of shoe (which is the argument of this bool function) is valid so return true, else false.
•  » » » 9 years ago, # ^ | ← Rev. 2 →   is it right about using min cost flow for check? As I understood, we must find a path from 0 to n — 1 which costs <= Budget. Why we can not use simple Dijkstra? Sorry, if I am wrong. UPD: sorry, I read wrong.
 » Div1-BCan anybody provide me with optimal strategy for the following case: height = {100, 50} add = {75, 30} device = {200, 100, 50} time = 2I cannot end with total height = 130 at the end and I cannot understand what I am missing.
•  » » You only use the device with height 50. At time=2 cut the first tree, so in the end it will have height=50. At time=1, cut the second tree, so in the end it will have height=50+30.