1e9's blog

By 1e9, 10 years ago, In English

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.

  • Vote: I like it
  • +32
  • Vote: I do not like it

| Write comment?
»
10 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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)

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

TC ContestApplet is not working from about 12 hours. It just stucks at opening screen. Anyone else facing similar problem?

  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Resolved: It was using proxy settings from Firefox and not the system settings!

»
10 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    10 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    No, that doesn't work. There are cases where you may want to choose some other cell.

    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh, my bad. Thanks. It seemed quite feasible :(

    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you provide a small example?

      • »
        »
        »
        »
        10 years ago, # ^ |
        Rev. 3   Vote: I like it +21 Vote: I do not like it

        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.

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How solve div1 B?

  • »
    »
    10 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

  • »
    »
    10 years ago, # ^ |
    Rev. 5   Vote: I like it +81 Vote: I do not like it

    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 turn

    The answer is the cheapest path from state (0, 0, 0) to (T, n, 0).

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Do you know, why solutions with 10^7 cout << int << ' ' << double << endl; doesn't fail on TL?

  • »
    »
    10 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Maybe, you use cin.tie(0) and ios::sync_with_stdio(false)?

    • »
      »
      »
      10 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It wasn't me. I tried challenge one guy and I don't understand why it was unsuccessful.

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the solution of Div.1C?

  • »
    »
    10 years ago, # ^ |
    Rev. 3   Vote: I like it +18 Vote: I do not like it

    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 :'( )

»
10 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    • »
      »
      »
      10 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Div1-B

Can anybody provide me with optimal strategy for the following case: height = {100, 50} add = {75, 30} device = {200, 100, 50} time = 2

I cannot end with total height = 130 at the end and I cannot understand what I am missing.

  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.