MONASH COMPETITIVE PROGRAMMING

«Back
MCPC-2020 Results
Placement Name
1st Place Wennong Cai
2nd Place Jeremy Yip
3rd Place Tianyang Zhan
Best Newbie Rajaraman Sundararajan

Problem A/B: Hearty Frogger I/II

Firstly, notice that even $1\leq t1 \leq t2 \leq 10^8$, we can always map the spawn location to one or two ranges $[l, r]$ where $0 \leq l \leq r < b$.

When $b \leq 50$

To simplify problem, we can change the frame of reference so that we can assume only Alice moves and she can take all hearts in the top-left diagonal line.

When $b$ is small, we can simply brute force the start location and comput the total heart in top-left diagonal line.

When $b \leq 10^5$

For better visualization, we shift the $i$-th row to right in $b-i-1$ position.

For a given spawn location range $(row, l, r)$, the best answer can be computed by a range query,

\[max(vec(j) |\ j \in [l, r])\]

where $vec(j) = \sum_{i=0}^{i=row}{heart(i,j)}$.

We can maintain $vec(.)$ by processing from top to bottom (start with $row=0$), and adding trucks in the current processed row - which is a range update operation. Both range query and range update can be handled by segment tree.

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int maxn = 100001;

struct truck {
  int x, y, l, h;
  bool operator < (const truck& rhs) const {
    return y < rhs.y;
  }
};

struct spawn {
  int x, y, tl, tr;
  bool operator < (const spawn& rhs) const {
    return y < rhs.y;
  }
};

vector<truck> tk;
vector<spawn> sp;

int b, p, q;
int best[maxn << 2], lazy[maxn << 2];

void push_down(int rt) {
  assert((rt<<1) < (b<<2));
  assert((rt<<1|1) < (b<<2));
  if (lazy[rt]) {
    lazy[rt<<1] += lazy[rt];
    best[rt<<1] += lazy[rt];

    lazy[rt<<1|1] += lazy[rt];
    best[rt<<1|1] += lazy[rt];
    lazy[rt] = 0;
  }
}

void push_up(int rt) {
  assert((rt<<1) < (b << 2));
  assert((rt<<1|1) < (b << 2));
  best[rt] = max(best[rt<<1], best[rt<<1|1]);
}

void update(int l, int r, int L, int R, int rt, int v) {
  assert(r >= l);
  assert(l >= 0 && r <= b-1);
  int mid = (L + R) >> 1;

  if (l <= L && R <= r) {
    lazy[rt] += v;
    best[rt] += v;
    return;
  }

  push_down(rt);
  if (l <= mid && r >= L) update(l, r, L, mid, rt<<1, v);
  if (l <= R && r >= mid+1) update(l, r, mid+1, R, rt<<1|1, v);
  push_up(rt);
}

int query(int l, int r, int L, int R, int rt) {
  assert(r >= l);
  assert(l >= 0 && r <= b-1);
  int mid = (L + R) >> 1;
  if (l <= L && R <= r) {
    return best[rt];
  }
  push_down(rt);
  int lans = -1, rans = -1;
  if (l <= mid && r >= L) lans = query(l, r, L, mid, rt<<1);
  if (l <= R && r >= mid+1) rans = query(l, r, mid+1, R, rt<<1|1);
  push_up(rt);
  return max(lans, rans);
}

void init() {
  memset(best, 0, sizeof(best));
  memset(lazy, 0, sizeof(lazy));
}

void solve() {

  init();

  int pt = p-1, ps = q-1, ans = -1;
  for (int y=b-1; y>=0; y--) {
    while (pt >= 0 && tk[pt].y > y) pt--;
    while (ps >= 0 && sp[ps].y > y) ps--;

    int d = b-1-y;
    while (pt >= 0 && tk[pt].y == y) {
      const truck& c = tk[pt];
      int l = (c.x - d + b) % b, r = (l + c.l - 1) % b;

      if (l <= r) {
        //printf("update l: %d, r: %d, h: %d\n", l, r, c.h);
        update(l, r, 0, b-1, 1, c.h);
      }
      else {
        //printf("update l: %d, r: %d, h: %d\n", l, b-1, c.h);
        update(l, b-1, 0, b-1, 1, c.h);
        //printf("update l: %d, r: %d, h: %d\n", 0, r, c.h);
        update(0, r, 0, b-1, 1, c.h);
      }
      pt--;
    }

    while (ps >= 0 && sp[ps].y == y) {
      const spawn& c = sp[ps];
      int l, r;
      if (c.tr - c.tl + 1 >= b) {
        l = 0;
        r = b-1;
      } else {
        l = ((c.x - c.tr - d) % b + b) % b, 
        r = ((c.x - c.tl - d) % b + b) % b;
      }

      if (l <= r) {
        int tmp = query(l, r, 0, b-1, 1);
        //printf("query(%d, %d) = %d\n", l, r, tmp);
        ans = max(ans, tmp);
      }
      else {
        int tmp = query(l, b-1, 0, b-1, 1);
        //printf("query-1 (%d, %d) = %d\n", l, b-1, tmp);
        ans = max(ans, tmp);

        tmp = query(0, r, 0, b-1, 1);
        //printf("query-2 (%d, %d) = %d\n", 0, r, tmp);
        ans = max(ans, tmp);
      }
      ps--;
    }
  }

  cout << ans << endl;
}


int main() {
  cin >> b >> p >> q;

  tk.resize(p);
  sp.resize(q);

  for (size_t i=0; i<(size_t)p; i++) {
    cin >> tk[i].x >> tk[i].y >> tk[i].l >> tk[i].h;
  }

  for (size_t i=0; i<(size_t)q; i++) {
    cin >> sp[i].x >> sp[i].y >> sp[i].tl >> sp[i].tr;
  }

  sort(tk.begin(), tk.end());
  sort(sp.begin(), sp.end());
  solve();
  return 0;
}

Problem C: Fast and Furious I

Method 1: BFS

Define status as (x, y, direct), then the problem becomes running BFS on 3-dimension graph.

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int maxx = 110;
const int maxy = 110;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};

vector<pii> p;
int m, sx, sy, tx, ty;
int ts[maxx][maxy][4];

struct node {
  int x, y, d;
};

void solve() {
  queue<node> q;
  node best = node{-1, -1, -1};
  memset(ts, -1, sizeof(ts));
  q.push({sx, sy, 0});
  ts[sx][sy][0] = 0;

  while (!q.empty()) {
    node c = q.front(); q.pop();
    int cost = ts[c.x][c.y][c.d];

    if (c.x == tx && c.y == ty) {
      if (best.x == -1) best = c;
      else if (ts[best.x][best.y][best.d] > cost) best = c;
      continue;
    }
    for (int i=0; i<4; i++) {
      // change direction
      if (cost > 0 && cost % m == 0 && i == c.d) continue;
      node nxt;
      nxt.x = c.x + dx[i];
      nxt.y = c.y + dy[i];
      nxt.d = i;
      // if nxt in bound
      if (nxt.x >= 0 && nxt.x < maxx && nxt.y >= 0 && nxt.y < maxy) {
        if (ts[nxt.x][nxt.y][nxt.d] == -1 || ts[nxt.x][nxt.y][nxt.d] > cost + 1) {
          ts[nxt.x][nxt.y][nxt.d] = cost + 1;
          q.push(nxt);
        }
      }
    }
  }

  int best_cost = ts[best.x][best.y][best.d];
  while (!(best.x == sx && best.y == sy)) {
    p.push_back({best.x, best.y});
    int cost = ts[best.x][best.y][best.d];
    int prex = best.x - dx[best.d];
    int prey = best.y - dy[best.d];
    int pred = -1;
    for (int d=0; d<4; d++) if (ts[prex][prey][d] + 1 == cost) {
      if (ts[prex][prey][d] > 0 && ts[prex][prey][d] % m == 0 && d == best.d) continue;
      pred = d;
      break;
    }
    assert(pred != -1);
    best = {prex, prey, pred};
  }

  reverse(p.begin(), p.end());
  assert(p.size() == best_cost);

  cout << best_cost << endl;
  for (auto i: p) cout << i.first << " " << i.second << endl;
}

int main() {
  cin >> m >> sx >> sy >> tx >> ty;
  solve();
  return 0;
}

Method 2: Greedy

Let $dx=tx-sx$ and $dy=ty-sy$, when $dx=dy$ the problem is trivial - move in horizontal and vertical alternatively. Assume $dx \neq dx$, we should make $|dx - dy|$ as small as possible in each step, and we will back to the trival case when $dx =dy$.

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
vector<pii> p;
int m, sx, sy, tx, ty;

void make_move(int& cur, int& delta) {
  if (delta <= 0) {
    cur--;
    delta++;
  } else {
    cur ++;
    delta --;
  }
}

void solve() {
  int dx = tx - sx;
  int dy = ty - sy;

  int curx = sx, cury = sy, ts = 0;
  int pred = 0; // 0: dx, 1: dy
  while (!(curx == tx && cury == ty)) {
    //printf("ts: %d, cur: (%d, %d), dx: %d, dy: %d\n", ts, curx, cury, dx, dy);
    if (ts > 0 && ts % m == 0) {
      if (pred == 1) {
        make_move(curx, dx);
        pred = 0;
      }
      else {
        make_move(cury, dy);
        pred = 1;
      }
    } else {
      if (dx > dy) {
        make_move(curx, dx);
        pred = 0;
      } else {
        make_move(cury, dy);
        pred = 1;
      }
    }
    p.push_back({curx, cury});
    ts++;
  }

  cout << ts << endl;
  for (auto i: p) cout << i.first << " " << i.second << endl;
}

int main() {
  cin >> m >> sx >> sy >> tx >> ty;
  solve();
  return 0;
}

Problem D: Fast and Furious II

Let $dp(x, y, s, d)$ be the number of ways to reach the $(x, y)$ in $s$ steps while the last direction is $d$. Then $dp(x, y, s, d)$ has subproblem(s) $dp(x’, y’, s-1, d’)$. Notice that $s < 3 * (dx + dy)$, thus the memory cost is up to $50 * 50 * 300 * 4 = 3 * 10^6$, which is efficient enough.

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int D = 25;
const int maxx = 52 + 2*D;
const int maxy = 52 + 2*D;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
const long long mod = 1000000007;

int m, sx, sy, tx, ty;
int mem[maxx][maxy][maxx*3][4];

int calc(int x, int y, int t, int d) {

  if (mem[x][y][t][d] != -1) return mem[x][y][t][d];

  if (t == 0) {
    if (x == sx && y == sy && d == 0) mem[x][y][t][d] = 1;
    else mem[x][y][t][d] = 0;
    return mem[x][y][t][d];
  }

  if (x == sx && y == sy) {
    mem[x][y][t][d] = 0;
    return 0;
  }

  int prex = x - dx[d];
  int prey = y - dy[d];
  int res = 0;
  if (prex >= 0 && prex <= tx + D && prey >= 0 && prey <= ty + D)
  {
    for (int i=0; i<4; i++) {
      if (t>1 && (t-1) % m == 0 && i == d) continue;
      res += calc(prex, prey, t-1, i);
      if (res >= mod) res %= mod;
    }
  }
  mem[x][y][t][d] = res;
  return res;
}

void solve() {
  memset(mem, -1, sizeof(mem));
  int ans = -1;
  int opt = max(tx - sx, ty - sy);
  for (int t=1; t<=3*opt; t++) {
    for (int d=0; d<4; d++) {
      int res = calc(tx, ty, t, d);
      if (res == 0) continue;
      if (ans == -1) ans = 0;
      ans = (ans + res) % mod;
    }
    if (ans >= 0) {
      cout << t << " " << ans << endl;
      break;
    }
  }
}

int main() {
  cin >> m >> sx >> sy >> tx >> ty;
  sx += D, sy += D, tx += D, ty += D;
  solve();
  return 0;
}

Problem E/F: Storage Room I/II

When $V \leq 10^3$

When $V \leq 10^{12}$

python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import math

v = int(input())
divs = []
sqr = int(math.sqrt(v)) + 1
for i in range(1, sqr + 1):
    if v % i == 0:
        divs.append(i)

best = math.inf

for first_one in divs:
    for second_one in divs:
        if v % (first_one * second_one) == 0:
            third_one = v / (first_one * second_one)
            best = int(min(best, 2 * (first_one * (second_one + third_one) + second_one * third_one)))

print(int(best))