scott_wu's blog

By scott_wu, history, 4 years ago, In English

Hey all,

I've posted my screencast and commentary of yesterday's Kickstart 2020 round B. Check it out at https://www.youtube.com/watch?v=AP74zQ0ZmRM

BTW, stay tuned for the return of Lockout streams in the coming weeks! :)

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

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Auto comment: topic has been updated by scott_wu (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Only scott_wu can choose overcomplicated solutions and still finish first :P

Here's some simpler alternative solutions (which you alluded to in the analysis):

problem B: - chosen solution: binary searching - simpler solution: going backwards & rounding D down to the nearest multiple of x[i]

  ll n, d;
  cin >> n >> d;
  vector<ll> v(n);
  for (ll &i: v) cin >> i;
  for (int i = n - 1; i >= 0; --i) {
    d -= d % v[i];
  }
  cout << d << "\n";

problem C: - chosen solution: something with a 2D array of pairs, unclear exactly how many of those values are used - simpler solution: iterate through string while maintaining a stack, latest value should be product of all loops that contain the current position

typedef modnum<int(1E9)> mint; // https://github.com/ecnerwala/cp-book/blob/82a039f71e105737a1591caf609f4d1e0b9532ba/src/modnum.hpp
  string s;
  cin >> s;
  vector<mint> mult({1});
  mint x = 0, y = 0;
  for (auto c: s) {
    if (c >= '0' && c <= '9') {
      mult.push_back(mult.back() * (c - '0'));
    } else if (c == '(') {
    } else if (c == ')') {
      mult.pop_back();
    } else {
      mint dx = 0, dy = 0;
      if (c == 'E') ++dy;
      else if (c == 'W') --dy;
      else if (c == 'N') --dx;
      else ++dx;
      x += dx * mult.back();
      y += dy * mult.back();
    }
  }
  cout << int(y) + 1 << " " << int(x) + 1 << "\n";