• simple arithmetics
  • optimal strategy was intuitively clear
  • 2D case just jumped to different row instead of enforced hit announcement

Typing monkeys

  • I knew principle how to get the result, however, had problems deriving correct probability of words within sequence
  • thus I solved only the simple version where I enumerated all possible word sequences
  • I had unsubstantiated troubles counting how many overlapping words fit into sequence of length S…
    • fortunately figured it how eventually, on the other hand I thought this get me to advanced group, I was 1082th though, so I went to the last task

Less money

  • I was a bit stressed (despite the fact, uniform 50 minutes remained till the end)
  • I had no idea how to solve it with repeated coins
  • I brute-forced single coin problem and did it as subset sum
  • and only after implementation of subset sum I realized I must always add the smallest coin of impossible prices
  • before submit I was below 1200, after it I got between 1100 and 1200

  • I wasn’t qualified and still about 30 minutes remained
  • I knew I won’t figure out the coins (FIXME would be nice to understand the efficient solution)
  • I attempted to derive probability of words within sequence, however, it seemed complicated (=conditioned) because of overlapping words
  • in the end, I was 1132nd and after deadline because of many people had wrong answers to big tasks (I expected that this would be 50–100 people), I moved to 947th place :-)

Lessons learned

  • I did it all in Python (I didn’t manage to prepare C++ templates).
  • Brush up on discrete mathematics (counting the words, probability).
  • Learn how the coins should have been solved.