Xellos's blog

TC SRM 638
By Xellos, 10 years ago, In English

The last blog got downvote bombed into oblivion, but I have enough contribution to spare.

TC SRM 638 takes place soon (ಠ_ಠ).

Feel free to discuss the problems here after the round ends (because TC apparently doesn't have placeholders for new matches in its forum anymore...).

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

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

I bet you are the problem setter today.

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

    Actually, there's almost enough information to deduce this: https://apps.topcoder.com/forums/?module=Thread&threadID=826777 and related threads.

    Some additional information: problems from that incentive were for SRM and TCO.

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

      I have never used/read topcoder forums. Are they alive?

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

        Holding on to bits of life, rather. There's something to be found occasionally (discussion of ACM WF problems, or this writers' incentive), but not much.

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

    I must admit, the AC rates on 300 and 600 are similar to my 250. Only much, MUCH worse.

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

Start with the hard problem, they said... It's only 800, they said...

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

    Still better than 250.

    Everyone gets challenged (at least in my room...).

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

      But everyone who opened the 600 beat me >.>

      For the 300, what's the testcase that kills the solution which checks if the number of connected components is <=1 (instead of checking whether at least one of the components is "good enough")?

      Edit: The check lots of people forgot is {"Y"},{"N"},{"N"}, but my question still stands.

      Edit2: The testcase is {"YNY","YYY","YYY"},{"YNY","YYY","YYY"},{"YNY","YYY","YYY"}. Topcoder chat scrolled away so I can't see who to give credit to, sorry :(

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

        is answer for this test: {"Y"}, {"N"}, {"N"} Impossible? Sorry for stupid question, but i just can't understand trick of this test.

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

          Yes. The trick is that you would see the whole cube should be empty, therefore connected, and you'd think it's all ok if you don't check that it actually covers everything it needs to cover.

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

        And what should be answer for the second? I suppose "Impossible" too?

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

          The second should be possible. Even though the maximal shape is not connected, one of its connected components is good enough.

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

        Thanks for the hint!

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

    Some stupid stuff should pass, they said... It's only 300, they said...

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

TC apparently doesn't have placeholders for new matches in its forum anymore...

From Chat Room 1:

vexorian> t-mac: also create for 637 it has been missing
...
t-mac> vexorian: I'll get that fixed soon, sorry about that
→ Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

It seems that the nubmer of people solved 300 is nearly same as the number of who solved 600 :(

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

    600 has around 80 successful solutions, 300 has around 55 (much less).

    My sides.

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

How to solve 600?

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

    Considered the largest wolf wolfi, if wolfj + wolfi ≤ limit,then this wolfj is free, it can be anywhere in the sequence. But somehow there are some wolves can only be in the left of the largest one, some should only be in the right. Now we get two small subproblems. You can use divide-and-conquer to solve it.:D

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

    Consider f(start, end) = number of possible permutations on the subsequence [start — end]:

    • If end < start just return 1;

    Otherwise: - Find the smallest wolf and remember its position min;

    • Find the largest range [minStart, min] such that minStart <= start and the sum of wolf[i] + wolf[min] <= maxSizeSum for every i in this range;

    • Likewise find the largest range [min, maxEnd] such that maxEnd <= end and the sum of wolf[min] + wolf[i] <= maxSizeSum for every i in this range;

    • Swap positions min and minStart;

    • The answer will be: f(start, minStart — 1) * (maxEnd — minStart + 1) * f(minStart + 1, maxEnd) * f(maxEnd + 1, end).

    This is because in the range [minStart — maxEnd] for every i in this range wolf[min] + wolf[i] <= maxSizeSum so wolf[min] can occupy any position within this range but can't go outside this range. So you are left with calculating the number of possible permutations in this range such that wolf[min] isn't there and multiply by the length of the range because wolf[min] can occupy any position. Of course you still have to multiply by the number of permutation on the left and right side of this range which is f(start, minStart -1) and f(maxEnd + 1, end) respectively.

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

    There is a simple solution. Find a smallest element. Find the number of places (it can go right and left as long as swapping rule is not violated) it can be in.Let it be k. Now, remove that element from the array.Let the new array be v' Answer is ans(v)=k*(ans(v') .
    This is O(n^2) (using recursion,n steps at each level)
    Credits : [user:msaikrishna17394]

    → Reply