chrome's blog

Topcoder Open Algorithm Round 1A 2016
By chrome, history, 9 years ago, In English

Hi!

Tomorrow at 19:00 MSK will be held TCO16 Round 1A.

You can read about TCO16 here.

Also this round has limited number of competitors only 2500. And max number of advancers to the next stage is 750.

Let's discuss problems after contest.

GL && HF!!!

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

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

registration started , register soon since number of people allowed to participate are limited(2500)

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

Is it a rated contest?

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

What is the idea of 1000!!!

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

    Greedy approach is ok, try the least index to go now and check whether it is possible to finish process from current state.

    To check it one can prove that it is optimal to go to the deepest node from current one every time.

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

      Could not understand, what should be done in case of walking to the least index from current state doesn't brings to finish?
      Try the next unvisited least index or something else? If try the next — it's looks like bruteforce.

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

        We pick node with the least index and trying to find some answer(maybe not optimal one). If we can find it, we take this node to answer and trying to make next move, or try to pick node with greater index and so on.

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

          find some answer (maybe not optimal one)

          Still could not understand.. How to do it? Dirac's theorem about hamiltonian path or something else?

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

            To check if answer exists, every time we should go to the deepest node which is reachable from current one.

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

Is there any way to solve 1000 in O(N3)?

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

    Yep.

    Let's do the following process: suppose we have a function that is able to, given a sequence of already visited vertices (we are staying at the last vertex of that sequence), tell if this sequence can be extended to a correct permutation. Having such function, we can determine the answer in O(n2) calls of it by restoring the elements of the desired permutation one by one.

    Now we need to implement such function. This can be done via pretty easy DP, smth like D[v] =  minimum number of vertices above v we should visit in order to visit all vertices in the subtree of v. It can be calculated in O(n).

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

    If you can check if there exists a sequence starting with a1, a2, ... in O(N) then you can solve the question in O(N^3).

    To do this: we remove all the vertices in the sequence that we already decided to use from the tree: so if we decide to go to 2, then all of 2's children are now children of 2's parents, etc. Now we can perform a tree dp[], taking special consideration of which is the last a_i we decided to use.

    dp is number of times you need to leave the subtree.

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

      Could you please provide a link to your source code here?

      It would be helpful for me to understand the solution.

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

    Interestingly enough there is even an O(N^2) solution. The main idea is that you can find nodes that are "good to go to" without breaking the traversal of the tree in O(N). If you are interested you can see my code in the practice rooms. As a problem setter I decided to not give it with N <= 1000 xD

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

Not related to problem.

I am getting the above error. I tried reinstalling java, using javaws to run it from command line, downloading the applet again.

There is one solution where I have to add the site as exception list in java. But I don't know the exact site address of topcoder. If someone knows please help.

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

    I had the same problem and resolved it using your solution: added "http://www.topcoder.com" to the list of exceptions.

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

    i had the same problem. and i solved it finding the "java control panel".

    There you choose the sequrity tab and set it to medium .

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

      I think allowing medium would be riskier for other application. We actually trust topcoder that's why added it as exception :)

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

    I had the same issue and decided to try web applet, in my opinion it worked fine but it was difficult to find things like how enter to the contest, open a problem, test a code, and finally I couldn't find how to see the global ranking.

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

    Thank you! Now I can write 1001 reasons to hate the Arena! I only had 1000 till date!

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

can anybody please explain div-2 500 by binary search and DP ??

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

    Suppose you have another problem, you have an array A and an integer D, what is the maximum number of disjoint pairs you can form where a pair(x, y) can be formed if abs(A[x] — A[y]) <= D, this can be solved by dynamic programming in O(N^2).

    In the original problem we can binary search D.

    → Reply