fushar's blog

Topcoder Open 2017 — Round 2B
By fushar, history, 7 years ago, In English

TCO17 Algorithm Round 2B will start at 12 noon EDT, Saturday, July 8, 2017.

Let's discuss the problems after contest here.

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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Approach for 300?

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

    Choose the smallest string with "largest prefix of length k".

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

Well my linear hard fell with TL at some test with small double numbers. It works 3s at this particular maxtest (at others < 100ms). And changing long double to double speeds up the solution in 7 times. That's how I lost the first place.)

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

Approach for 500 pts?

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

    For each connected component of equal letters find minimal and maximal height [l, r]. now you have the set of segments. And answer is number of ways to choose some segments so that their union covers the entire array of heights, this can be calculated with dp.

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

Solution for 1000?

→ Reply