chrome's blog

Topcoder Single Round Match 688
By chrome, history, 9 years ago, In English

Hi there!

Tomorrow at 18:00 MSK will be held Topcoder SRM 688.

Let's discuss problems here after contest!

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

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

Is topcoder working currently? I can't connect either through application or web. Connection timed out

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

    For me, the Java arena managed to start, just very slowly (after a few minutes).

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

      My arena is not working at all. And "ping topcoder.com" doesn't respond.

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

    I am having the same result. Hope the coding time will be extended.

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

      I'm still waiting for arena to start too.

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

How to access problems in the web arena? I can't seem to find them.

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

Will that be unrated? I turned on my arena at 16:58 at it loaded at 17:18 :P. Nevertheless I decided to take part, because I'm not solving contests mainly for rating, but for fun.

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

    Yes, I spend 10 minutes to open arena too, and i can't submit second problem;(

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

My short story of today's SRM:
1. I tried to open Arena at 16:58 (SRM was starting at 17:00 in my timezone), but it was loading forever. At 17:10 I lost my hope and stopped waiting and watching CF if that is not only mine issue (from comments here I concluded that others also experience this). No wonder it influenced my mood in a very negative way.
2. Very surprisingly at ~17:20 it finally loaded. I thought that everyone had the same issue as me, but there were already many submissions on the leaderboard, so I felt that it was really unfair. But as I was already in a bad mood I thought "OK, ^&*# the rating I will compete either way. I will try to perform well, but that will ont be easy"
3. After ~10 minutes I wasn't able to figure out 250 problem, so I thought "OK, now I don't care even about place, so let's check if hard problem is fun"
4. I got some not very clever observations in hard problem and my intuition told me that a stupid approach which is on my mind may be ok. It seemed to be waaay too easy to be a good solution to hard, but as I already said I wasn't in a mood for solving problems, so I was too lazy to think about any proof/counterexample/different approach, so I started coding.
5. After some debugging it passed samples. Lol. Submitted it expecting miserable fail on systests.
6. It passed systests and I'm 9th XDDDDD. In the beginning of the contest I already accepted fact that I will got like -150 to my rating and didn't try hard to change that, but in the end I got +84 xD.

In my opinion problems should be cyclically shifted one place to right preserving their original point values :P.

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

    How to solve Hard? :D

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

      cgy4ever told me the intended solution for Hard and it was a very nice solution with flow. (This is a very big hint, but I still couldn't solve it with this hint — can you solve?)

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

      I greedily constructed those strings keeping their 'heights' difference as small as possible. After considering some prefix of s, first constructed string always have exactly the same number of nonclosed brackets as second one or exactly one more. In the end compute their summed cost :P. As I looked, Petr's submission follows exactly the same idea.

      My code is here: http://ideone.com/JgVmI7

      Observations which I made during the contest were:
      1. Those strings can be constructed iff s is a correct bracket sequence
      2. If I'm not mistaken (I may be) consider two strings A and B so that their "heights" (number of nonclosed brackets) are the same. Then (cost(AC) — cost(BC)) is fixed for all valid Cs. That implies that if we are in the middle of constructing process, only thing that matter for future decisions is the height. That statement is either very easy to prove or obviously false, but as I have already said few times I was too lazy to check and still I am
      3. Since x^2 is an increasing function, it is better to make those strings relatively flat, so better keep their heights as close as possible to each other.

      EDIT: Statement 2. is in fact obviously false. A="(()", B="(", C1=")", C2="())". However I don't know now how does that affect dubious correctness of my solution.

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

        Well I tried the same solution with one little difference. I also always put +1 to the smallest and -1 to the biggest, but I don't fix which one of two strings will be the largest (case of equal heights). And without it the solution doesn't pass systests (in my code it's a change of "<" to "<=" in closing bracket case).

        It's interesting whether this solution actually works at stress.

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

          I remember Petr on his blog wrote that it works to all strings up to some length (something like 16 or 18). I believe it is a correct algorithm, but I expect proof to be noninteresting ifology (but still requiring some nontrivial idea), so I didn't think hard about it.

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

      My solution is DP which will work for any cost function. The idea is following: notice that there exists a solution where every pair of matching open and close brackets belongs to the same subsequence. So we can build a tree of pairs of brackets (we'll add a dummy node and make it a parent of all bracket pairs without parents) and the goal is to distribute its nodes into two trees so that overall cost is minimized. Let f(v, d1, d2) be the optimal cost of splitting a subtree of node v into two trees so that depth of the first tree is d1 and depth of the second one is d2, node v is considered unassigned (i.e. we'll assign it to one of the to trees later). Then, we can iterate over child nodes and make a DP transition for each of them (when we assign a child node to one of the two subtrees, the depth will change by 1, overall depth will be max(current_depth, this_child_depth)). Overall complexity is O(N^4).

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

        I had a similar idea, but got stuck, because initial sequence not necessary a correct bracket sequence. Did you add some artificial brackets to deal with that?

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

          If it's not a correct bracket sequence, the answer is -1.

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

        Have you proved that "there exists a solution where every pair of matching open and close brackets belongs to the same subsequence"? Is there some simple proof?

        I have passed in practice room with the following greedy solution (which seems to work only for cost functions growing faster than linear):

        • Answer is not -1 iff initial sequence is a valid parentheses sequence

        • If the sequence is valid there is corresponding forest (And depth of the sequence is exactly the height of the forest).

        • "there exists a solution where every pair of matching open and close brackets belongs to the same subsequence" => there exists solution where the relation of being nested over parentheses is preserved => there exists solution where the relation of being successor over vertices in the forest is preserved

        • Since function grow is faster than linear it is optimal to just colour every tree into 2 colours. (The parentheses corresponding to each colour form the sequence)

        Complexity is linear. But I have to admit there are some gaps in the proof.

        Code http://ideone.com/uCzy9E

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

    Up until point 4. my situation was exactly the same. The difference was that I didn't finish debugging Hard in time and I'm at 0 points and (I don't want to see the rating change).

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

    Was that experience with web or java applet arena?

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

how to solve Div1 250 ??

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

    Preprocess the string, for any index i, try to delete as much as possible valid parenthesis starting from i. The preprocess will take O(n^2), after that the string can be 3 formats: "))..))", "(((...(((" and ")))..(((". In each case it is easy to find a way to make it valid.

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

    The operation given is equivalent to take the mirror image of the segment.

    Use a stack insert everything that is unbalanced into stack , even ')' brackets.

    At the end, the state of the stack will be something like :

    )))))(((((((

    If the stack size if odd return -1.

    Note : The ')' sequence or '(' can be empty too . Also the balanced parenthesis keep balanced even after the operation.

    Now to balance try taking mirror image of at most STACK_SIZE/2 using one operation and another operation to turn other half to make the state of stack as STACK_SIZE/2 '(' and STACK_SIZE/2 ')'.

    (Sometimes you do not need to take mirror image of some elements)

    Complexity : O(N)

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

    Replace '(' with +1, and ')' with -1. Compute prefix sums. Observe that correct bracket sequence is equivalent to sum[i] ≥ 0 for all i and sum[n - 1] = 0.

    Find the smallest prefix sum — say sum[k]. If sum[k] < 0 then apply our move on that prefix. Observe that the first property (sum[i] ≥ 0 for all i) is now satisfied (why?)

    Now if sum[n - 1] = 0 then we are done. Otherwise sum[n - 1] = 2·h > 0 (because n is even), now just find last index l with sum[l] = h and apply our move on suffix [l, n - 1].

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

      Wow, cool. I thought it's gonna be something like O(logN) moves.

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

        Technically you're right, 2 is definitely O(logN) :P

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

      Actually this is very similar to my approach but somehow I managed to not to keep balance sum (I do not need crossing Operation too). Solution

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

      Don't you think, it should be [l + 1, n — 1]?

      Any corner cases can you think of? I had same approach but I got hacked :(

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

        No stk[i] is the position of the unbalanced parenthesis in the original string We have to balance. You will reverse from this position to the last.

        Though I don't have your code but I think your mistake is quite trivial you will eventually have a facepalm moment.

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

Where can one view problem submission challenge data ?

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

Any hints for Div 2 Hard?

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

Could someone tell me How the algorithm in Div-2 500 ptr will always output less than or equal to (lenth_of_string/2 + 1) flips ? A formal proof of some sort. My idea was to keep a variable balance which stores difference b/w '(' and ')' seen up till a certain point. Balance is incremented when '(' and decremented when ')'.

if bal<0 ---> index is pushed and , bal += 2

if bal>1 ----> index is pushed and bal -= 2

This failed the system tests since it outputted more than (length/2 + 1) flips. Could someone tell me why my idea wouldn't work. Thanks.

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

    When i found my self stuck and can not get a proof fast, i assumed there will always be a way to do so ( the statement said that ) so i coded a dynamic programming solution which gets the min number of flips needed, then 1 more function which trace my DP table and gets the path that the DP follows ( the indices that should be flipped ). and passed the system test.

    this is my solution.

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

      Thanks.

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

      I wrote a greedy algorithm with time complexity O(n) where n is length of input string. It passed system tests.

      Here is my solution.

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

how to solve div2 500?

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

    What you need to flip are ')' that don't match to their left, and '(' that don't match to their right. But remember if you have 2 ')' that don't match, and you flip the one that appears first, you'll have these 2 symbols matched: )) -> () The same with '('s. So you just perform a check:

    let cnt be the number of opening '('
and you have a stack st
for i in [0, s.size())
  if s[i] is ')' and cnt = 0
    flip i
    push(i)
    cnt++
  else if s[i] is ')'
    cnt--;
  else if s[i] is '('
    push(i) 
    cnt++

    finally you'll get a stack with '('s, flip half of them you'll get a valid sequence.

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

for div1 hard, i got an idea like this: Let dp[i][cnt1][cnt2] be the minimum cost starting at position i, and to its left there were cnt1 opening '(' in sequence 1 and cnt2 opening '(' in sequence 2, what's the minimum cost. The transition:

if(s[i] == '(')
  dp[i][cnt1][cnt2] = min(dp[i + 1][cnt1 + 1][cnt2], dp[i + 1][cnt1][cnt2 + 1]);
else if(s[i] == ')')
  dp[i][cnt1][cnt2] = min(dp[i + 1][cnt1 - 1][cnt2] + cnt1 * cnt1, dp[i + 1][cnt1][cnt2 - 1] + cnt2 * cnt2); // of course, don't caculate those with cnt1 = 0 or cnt2 = 0

and when "i" becomes s.size(), and cnt1 = cnt2 = 0, return 0, or else it is an invalid solution. I think this works because I just put each symbol into sequence1 or sequence2, but actually it won't even pass the samples. And I just can't figure out why, could someone kindly help me with the problem of this idea ?

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

    Another idea I also tried is that, I maintain 2 stacks, and opening '('s are put into them, and I'll try to make the length of these 2 stacks as close as possible, that is, whenever a '(' comes, I push it into the stacks with less '(', and whenever a ')' comes, I match it with the sequence with less length. However, this idea is also wrong and has the answer as the previous one.

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

      I know where my problem lies... depth(AB) = max(depth(A), depth(B)) cost(AB) = cost(A) + cost(B)

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

I wrote a simple O(n) greedy in Div.1 Hard and to my surprise it passed system test.

I just build the forest using the parentheses sequence, and I divided the tree into two parts: the nodes with a odd depth and the nodes with a even depth. Then I calculate the cost of the two parts.

It seems that it's correct but I can't come up with a strict proof...

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

    Thanks! This is an interesting idea. I think it's quite similar with the idea that maintains 2 stacks. It seems somewhat obvious to do so but I can't neither show that's mathematically correct :-(

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

Any ideas on Div 2 Hard

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

How to solve DIV 2 1000 ??? I need an explanation

→ Reply