decoder123's blog

Topcoder Single Round Match 695
By decoder123, history, 8 years ago, In English

Hi!

Tomorrow at 14:00 MSK will be held Topcoder SRM 695.

Let's discuss problems after contest!

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

Comments Comments (30)
| Write comment?
»
8 years ago, # |
  Vote: I like it +41 Vote: I do not like it

is chrome ok? no posts of SRM by him since long time :/

I miss him :(

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

Can someone please explain the solution to Div1 Level 3?

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

    Solution to the 800: If S % K = 0, then write S/K on both sides of the coin and we are always done.

    If S % K is not 0, then first notice that we can only win if there is at least one head and one tail. WLOG the first flip is heads, and consider the position of the first tail.

    If there are A heads and K-A tails in the end, we must have AX + (N-A)Y = S for X on the heads side and Y on the tails side. Note that if gcd(A,N-A) does not divide S, we cannot win in this case.

    Otherwise, pick X so that for each A with gcd(A,N-A) dividng S, there exists integer Y with AX + (N-A)Y = S. (This can be done by the Chinese Remainder Theorem, as we need A | S-NX for each of these A)

    Write X on the head of the coin. Once the first tails appears, we need to decide what to write. If there are C coin flips left, pick the A closest to (C/2) such that gcd(A,N-A) divides S. Then write the Y with AX + (N-A)Y = S. The probability of this scenario is (C choose A) / 2^K.

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

      I have question about this solution.

      In Chinese Remainder Theorem, the dividers need to be co-prime to each other, which is not ensured in this problem. How could we ensure we can find such X?

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

        Ok, we need to find integer X so that lcm(all possible A) | S-NX. The greatest common divisor of this LCM and N must divide S since gcd(A,N-A) divides S, which means that you can find such an integer X by Bezout.

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

  • Reads a statement about bears/Limak

  • Immediately realises it's an Errichto's Round.

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

Can someone please explain some deterministic solution to div1 500? I didn't manage to use the fact about degree<=3 somehow so I just coded local optimization desperately.

Upd. I've just read in chat room, picking an edge decreases cost of at most 5 edges, so there is no need to try something except of 35 best edges in our brute force solution. Got it :(

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

That was my first time in a SRM! :D The experience was awesome. ^_^

I've a question though. Is there any editorial for today's contest?

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

    Don't expect the editorial to come out soon. They haven't published the editorial to SRM 694 yet. :(

    But you can ask the problems here. :)

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

How to solve div1 300 ??

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

    I will split the answer string into maximal constant substrings and store them in some container. (eg. abbaab has 4 components a, bb, aa, b). Once you have the sizes of all these components, you can assign 'a' and 'b' greedily. Keep assigning 'a' to the largest component, 'b' to the smallest, then 'a' to the largest and so on.

    Now to get these components. Iterate from n to 1 (assume x[] is 1-indexed). Store the components you have already found in some container. If you are at position i, decrease the value required by the number already contributed by all the components you've found already. If this value goes below zero, answer is not possible. Otherwise if remaining value is r, create r components of size i.

    Let's take a small example. Consider the vector {4, 2, 1}. At position 3, you create a component of size 3. At position 2, you get the new value as (2-(3-2+1)), which is 0. So you move on. Then at position 1, you get the new value as (4-(3-1+1)), which is 1. So you add 1 component of size 1. You have 2 components now, one of size 3 and one of size 1. Assign 'a' to the largest and 'b' to the smallest, to get the answer "aaab".

    Hope this helped. :)

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

      Yeah, it helped, thanx a lot :) ...

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

      Thanks for describing your solution satyaki3794. Unfortunately I feel like I'm missing something. What do you do if you have something like this {0, 0, 2, 0}. From my understanding you create 2 components of size 3, but this doesn't seem right since then your final string will have length of 6 chars while one with 4 chars is needed.

      Furthermore, how exactly do you decrease the value of all the components found already. E.g., what exactly are the numbers in your calculations: (2-(3-2+1)) and (4-(3-1+1))?

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

        Please refer to my code.

        Also, I have added a check for ans.length() == n at the end, to take care of the problem you mentioned.

        As regards to the value (2-(3-2+1)) at pos 2 (1-indexed array), 2 is the required number of constant substrings of length 2 and (3-2+1) is the number contributed by some constant substring already found (in my above example, there is only one of length 3).

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

    My solution was: the final string will be made of various segments of 'a's and 'b's. Let ai be the number of these segments of length i.

    Then ai satisfy a system of linear equations that involve xi. They also all need to be non negative and the sum of i * ai needs to sum to N.

    I solve that system, verify the solution and generate the output string.

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

My codes in Java. There are two approaches for div1-med. Mine was "choose some K of the initially-best 5*(K-1)+1 edges, in complexity C(5·(K - 1) + 1, K)". The other one was resursive "find the best edge and either take it or take some two neighbours".

div2-easy
div2-med
div2-hard
div1-easy
div1-med
div1-hard
→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    could you please elaborate a bit on div2-hard?

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

      Every valid subtree has a unique diameter. The main idea is to iterate over O(n2) possible diameters. For a fixed pair of vertices (a, b) we are interested in the number of subtrees with the following properties:

      1. Vertices a and b belong to a subtree. It means that everything on a path between them also must belong to a subtree.
      2. There should be no vertices v that dist(v, a) ≥ dist(a, b) or dist(v, b) ≥ dist(a, b) because then (a, b) wouldn't be a unique diameter.

      You should mark some vertices v as forbidden and on the remaining vertices run an O(n) dynamic programming solution. Check my code for details.

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

    Could you explain Div2-Med a bit please? Esp. this part: ~~~~~ for(int j = i — 1; j >= 0; --j) x[j] -= val * (i — j + 1); ~~~~~ Why do we reduce the values and then check if x[j] going < 0 will return an invalid password. Am not able to get the intuition behind this. Seems like something to do with combinations.

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

      Let's say the input says that there are no intervals of length bigger than 5. But it says that there are two intervals of length 5. Each of those two intervals generate some smaller intervals. In an interval of length 5 there are:

      • two intervals of length 4
      • three intervals of length 3
      • four intervals of length 4
      • five intervals of length 5

      The solution is to subtract those and then move on — check if the input says something about some smaller intervals that weren't simply generated by bigger intervals (here: intervals of length 5).

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

    Could please explain where number "5 * (K — 1) + 1" in your Div1-medium solution come from? I know picking 1 edge will affect cost of at most 5 other edges, but it doesn't seem obvious.

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

      Let's say that we already know k - 1 edges from some optimal solution. These edges affect at most 5(k - 1) edges in total. So, at the beginning you can sort edges by "the-sum-of-values-of-two-connected-vertices" and right now the best k-th edge to add is for sure one of 5(k - 1) + 1 best ones from the beginning. Because at least one of first 5(k - 1) + 1 edges isn't affected by already chosen k - 1 edges. And that "at least one" edge isn't worse that edges outside the set of first 5(k - 1) + 1 edges.

      Using the logic above, one can prove that there exists an optimal solution using edges only from the set of first 5(k - 1) + 1 edges.

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

    can you explain solution for div 1 easy

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

can someone explain div2 medium?

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

    You can think about the problem in this way:

    Let S be the answer we returned, and it can always be split into a consecutive sequence of 'a', then 'b', alternatively, etc. Let L[1], L[2], ..., L[t] be the length of each consecutive sequence of same character.

    For x[i], if L[j] >= i, then it will contribute L[j]-i+1 to x[i]. So x[i + 1] can be computed from x[i] in the following way: x[i+1] = x[i]-(# of L[j] >= i + 1)-(# of L[j] == i), this is equivalent to x[i+1]-x[i] = # of L[j] >= i

    Since we know how many L[j] has length at least i, we can thus construct an answer.

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

div2 medium not able to get solution?

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

    Here is my source: http://pastebin.com/N2TNgWD8

    The logic I follow is from biggests to smallests because biggests contains smallests. So lets say if x = {4, 2, 1, 0}. We check x[3] it is zero so we have nothing to do. We check x[2] = 1. Also we calculate how many 3-length substrs there are already. There are zero, so we need to construct one. The resulting string is res = "aaa" Next time we will start with the letter 'b'. x[1] = 2, we have already two substrs of length 2, so we dont add anything. Finally x[0] = 4, so because we have already three we just need to add one new, so resulting res = "aaab". I hope it helps.

    → Reply