Killever's blog

Topcoder SRM 676
By Killever, history, 9 years ago, In English

HI Folks,we Have SRM tomorrow at Time
Good luck to everyone.
Let us discuss problems here after the end of the contest

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

Comments Comments (24)
| Write comment?
»
9 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Why the downvotes?

→ Reply
»
9 years ago, # |
  Vote: I like it +33 Vote: I do not like it

Where is chrome?

→ Reply
»
9 years ago, # |
  Vote: I like it +84 Vote: I do not like it

I was the author for this round. Here are some hints and code:

code here:

all of div2: http://pastebin.com/YtdPjtHm

all of div1: http://pastebin.com/xSEVNXmW

Some vague hints

  • div2 easy: Suppose you just wanted to reduce time by 1 second. What's the best strategy in this case?

  • div2 med: The first step is to clearly define the state of the game. Then, you need to determine how to classify states as either winning or losing.

  • div2 hard: For each node in the tree, you can find some intervals of time where you definitely need to do one switch in that interval. How can you generate these intervals? Afterwards, does this modified problem look familiar?

  • div1 easy: Given an output rate, can you determine if the tank will overflow?

  • div1 med: The first step will be to compute some sprague grundy numbers. Can you see any patterns?

  • div1 hard: 2 different approaches

1) Given a time, can you compute the minimum budget needed to achieve this time?

2) Suppose you just wanted to reduce the time by 1. What's the best strategy in this case? (I'm not sure how to prove it, but it seems to pass all tests).

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    >(I'm not sure how to prove it, but it seems to pass all tests).

    Isn't that risky? Especially in competitions with challenges.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      I implemented the first approach as reference, which I know how to prove. I thought the second was interesting to mention, but I'm not sure why it works.

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

        Oh, I misread that part.

        It seems I could've solved 450 much more easily — I tried to find a pattern on paper, but it failed, so I just wrote a bruteforce for Grundy numbers, tried finding a period of Grundy numbers for some random tests (because they should be periodic if it's just 450 :D) and found out that it's 2 for large enough k...

        → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      Well, if the first approach can be proven then it's ok.

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

    The second solution uses critical path, looks like a well researched method so it's probably proven somewhere already.

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

    Strange solution for div1 hard that passes all systests: http://ideone.com/knlGNZ

    Basically, generate all paths from vertex with indegree 0 to a vertex with outdegree 0, then solve a linear program inside a binary search to find the answer.

    Seems to pass all system tests in at most 14ms (!), but I didn't have much confidence in this during the contest so I missed submitting by a few minutes :p.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    For div2 Med : It is possible to determine the winner of the game in O(1).Some case analysis needed . My solution : Link

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +19 Vote: I do not like it

    In div1 med of referenced implementation I found this code:

    if (k >= 4) {
    k = (k % 2) + 4;
}

    How this can be proven/inferred without generating any sprague grundy values? Is mentioned hint about it?

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Failed System Test Div1/250 :'(

How can you determine a good number of iterations for a floating-point binary search? I always make the same mistake of using an epsilon as a stop condition :(

It was a very silly mistake :'(

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

    A better approach in such situations is to manually set the no. of iterations ( >= 300 is fine)

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

    Suppose [L; R] is the search range and P is the number of digits after floating point you should calculate.
    log2(R - L + 1)  +  log2(10P)  + C will be enough for C <= 5.
    In today's 250p you could just set the number of iterations to 1024 and fit into the TL comfortably.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    I also used epsilon and passed. You just have to make sure that it's not too small; since the required precision is 10 - 6, I set it at 10 - 7. And the initial max. R at 106.

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I don't trust in the epsilon as the stop condition anymore :(

    It cost my team a problem in the ACM ICPC Latin America Regional contest of this year (a ternary search with dijkstra), and now this xD

    Thanks guys!

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    What is at least one reason not to use epsilon as stop condition, what caused a problem here? I was used to perform constant number of iterations, however recently I got 2 TLEs in 2 different problems within few days, because I set that constant a bit too high and after changing this to epsilon condition it passed, so now I think that eps condition is a safer way. However we should be aware that epsilon condition is applicable if value we are searching for is exactly what we want to output, I mean such thing will be bad:

    "Print result with error not larger than 10 - 6."

    double l = 0, r = 1e6;
while (r - l > 1e-7) {
  (...)
}
cout<<f(l)<<endl;

    because maybe it doesn't hold that

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I was able to cruze for first two problems div2 with comfort, but had no idea how to solve div2 hard, can anybody explain how to solve ? I did not get lewin solution

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

    I haven't coded it yet, so not 100% sure if it will work, but this is the best I could come up with.

    We can easily figure out the path (sequence of nodes) required for each train.

    Then we can figure out at what time, which nodes need to be in what state, eg(node 2, R).

    If we figure out all possible changes required to all possible nodes, and sort it by time, and then make the change at the top of the sorted list, followed by all possible changes, such that the same node is not changed twice (i.e stop changing node k, if it's ith iteration is different from it's first iteration in the list, and don't change it in this action) , in the same action, deleting the changed items from the list.

    Repeat till empty list, the number of times we had to iterate is the answer.

    I couldn't code this during the contest (ran out of time). Will try coding this after classes today.

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    Look at some specific node. For each train that passes through this node you will get an information "at time t[i]+epsilon the switch needs to point in the direction dir[i]".

    For example, you can obtain the information (3,left), (5,left), (12,right), (15,right), (33,left).

    Then, this particular node needs to be flipped twice: once in the interval (5,12] from left to right and once in (15,33] from right back to left. This is possible if and only if there is an action during each of these intervals.

    So, now you have a collection of intervals and you want to cover all of them using as few actions as possible. To do this, just notice that it never hurts to perform the actions as late as possible. For example, if your intervals are ( l[i], r[i] ], it makes no sense to perform the first action sooner than at min(r[i]). This allows us to solve it greedily: always find min(r[i]) among intervals that don't contain any actions yet.

    → Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Finally uploaded my screencast

→ Reply