MONASH COMPETITIVE PROGRAMMING

«Back
MCPC-2016 Results

Problem A: Returning Home

The rain is in a checkboard pattern. Thus, if you are standing on a square that is not raining, then all of your neighbours are raining, which means that in the next second, your square will be raining and all of your neighbours will not be raining. So as soon you get to a square that is not raining, you can always stay out of the rain.

If you start in a square that is not in the rain, then you can just walk home normally–walk only to (i-1,j) or (i,j-1). If you start in a square that is in the rain, just simply wait 1 second then you will be in a square that is not raining. There are two corner cases: (1,0) and (0,1). If you are getting Wrong Answer, think about these two cases.

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
  #include <bits/stdc++.h>
  using namespace std;

  int main(){
    int x, y; cin >> x >> y;
    int d = x + y;
    int p = (x + y) & 1;
    if (p == 0){
      cout << 0 << ' ' << x + y << endl;
    } else {
      if (d == 1) cout << 1 << ' ' << d << endl;
      else cout << 1 << ' ' << x + y + 1 << endl;
    }

    return 0;
  }
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
  import java.util.*;

  public class Backtohome {
      public static void main(String[] args) throws Exception {
          Scanner in = new Scanner(System.in);
          int i = in.nextInt(), j = in.nextInt();
          in.close();
          int x = 0, y = i + j;
          if ((i + j) % 2 == 1) {
              x++;
              if (y > 1)
                  y++;
          }
          System.out.printf("%d %d\n", x, y);
      }
  }

Problem B: Badminton Bunny Buddies

Just a simulation problem. Carefully read the problem and simulate it.

Note: I do not endorse using the coding style used in the C++ solution presented here! (…even though I wrote it)

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
  #include <bits/stdc++.h>
  using namespace std;

  const string LR[2] = {"Left","Right"};

  int main(){
    string names[2][2];
    for(int i=0;i<2;i++)
      for(int j=0;j<2;j++)
        cin >> names[i][j];
    
    int W,score[2] = {0},serves[2] = {0};
    char c;
    cin >> c >> W;
    int t = (c == 'B');
    while(score[t] < W){
      cout << names[t]["011100"[serves[t]%6]-'0'] << " ";
      cout << LR["0110"[serves[t]%4]-'0'] << " ";
      cout << score[t] << "-" << score[1-t] << endl;
      serves[t]++;
      
      cin >> c;
      if(c == 'R') t = 1-t;
      score[t]++;
    }
    
    cout << "Team " << "AB"[t] << " wins!" << endl;
    
    return 0;
  }
java
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
  import java.util.*;

  public class Badminton {
      public static void main(String[] args) throws Exception {
          Scanner in = new Scanner(System.in);
          String[][] name = new String[][] { { in.next(), in.next() },
                  { in.next(), in.next() } };
          int AB = in.next().charAt(0) - 'A', W = in.nextInt();
          String res = in.next();
          in.close();
          
          int[] cnt = new int[2], win = new int[2];
          for (int i = 0; i < res.length(); i++) {
              cnt[AB]++;
              System.out.print(name[AB][(cnt[AB] + 1) / 3 % 2]);
              System.out.print(cnt[AB] / 2 % 2 == 0 ? " Left" : " Right");
              System.out.printf(" %d-%d\n", win[AB], win[1 - AB]);
              if (res.charAt(i) == 'R')
                  AB = 1 - AB;
              win[AB]++;
              if (win[AB] == W) {
                  System.out.printf("Team %c wins!\n", AB == 0 ? 'A' : 'B');
                  break;
              }
          }
      }
  }

Problem C: Candy

The bounds on the problem are very large, so you may not simulate the answer. The key here is to note you can do each pass of the teacher in O(1).

Case 1: If your location is 1 (mod k), then you will get candy on this pass. If you are at location p, then you will the ceil(p/k)’th person to receive candy. Note that you should use integer ceiling, not the builtin ceiling function.

Case 2: If your location is not 1 (mod k), then you will not get candy, so you need to remove those kids from the line. There will be ceil(n/k) kids that receive candy, so subtract that many from n and and add that to your answer.

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
  #include <bits/stdc++.h>
  using namespace std;

  int main(){
    int n,k,p;
    cin >> n >> k >> p;
    
    int ans = 0;
    while(p % k != 1 % k){ // Need 1 % k in case k == 1.
      ans += (n + k - 1) / k;
      n -= (n + k - 1) / k;
      p -= (p + k - 1) / k;
    }
    cout << ans + (p + k - 1) / k << endl;
    return 0;
  }
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
  import java.util.*;

  public class Candy {
      public static void main(String[] args) throws Exception {
          Scanner in = new Scanner(System.in);
          int n = in.nextInt(), k = in.nextInt(), p = in.nextInt();
          in.close();
          
          int id = 0;
          while (true) {
              if ((p - 1) % k == 0) {
                  id += 1 + (p - 1) / k;
                  break;
              }
              else {
                  id += 1 + (n - 1) / k;
                  n -= (1 + (n - 1) / k);
                  p -= (1 + (p - 1) / k);
              }
          }
          System.out.println(id);
      }
  }

Problem D: Happy Journey

The numbers are much too big to do anything like Floyd-Warshall. You can compute the distance from u, v and c to each of the other vertices (run Dijkstra times with u, v and c as the source). Then try all vertices as potential p using the distances computed in the Dijkstra computations.

Note: There is a quicker way to solve this problem. The values 1, 2 and 5 were selected specially–the answer is always to set p == v (prove it!).


Problem E: Eratosthenes Error

We are simply checking if k is the multiple of a perfect-square. It is too slow to check all of the squares up to sqrt(8 * 1018).

If k is the multiple of a square, then we can write it in the form x * y2 (x ≥ 1 and y ≥ 2). Note that either x or y must be no more than 2,000,000 (otherwise x * y2 > 8*1018). Simply try all x and y in their range up to 2,000,000 and check if the other variable is an integer.

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
  #include <bits/stdc++.h>
  using namespace std;

  bool is_perf_sqr(long long x){
    long long guess = sqrt(x)-1;
    while(guess*guess < x) guess++;
    return guess*guess == x;
  }

  int isPrime(long long k){
    for( long long x=1 ; x*x*x <= k ; x++ )
      if(k % x == 0 && is_perf_sqr(k/x))
        return 0;
    
    for( long long y=2 ; y*y*y <= k ; y++ )
      if(k % (y*y) == 0)
        return 0;
    
    return 1;
  }

  int main(){
    long long k;
    cin >> k;
    
    cout << isPrime(k) << endl;
    
    return 0;
  }

Problem F: Vending Machine

This problem is a very traditional problem: coin change problem. If you don’t know this, make sure you look it up (roughly equivalent to Knapsack Problem/Subset Sum Problem). This problem asks you 2 different instances of this problem: the 0-1 case as well as the infinite supply case.

To be a highly competitve programmer, I would recommend you learn this algorithm and be able to code it easily.

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
  #include <bits/stdc++.h>
  using namespace std;

  const int MAX_V = 50030;
  const int MAX_N = 130;
  int A[MAX_V],B[MAX_V]; // The DP
  int X[MAX_V],Y[MAX_N][MAX_V]; // The next value

  int read_currency(){
    int d,c; char ch;
    cin >> d >> ch >> c;
    return d*100 + c;
  }

  int main(){
    int n,m;
    cin >> n >> m;
    
    vector<int> coins;
    for(int i=0;i<n;i++)
      coins.push_back(read_currency());
    
    vector<int> mine;
    for(int i=0;i<m;i++)
      mine.push_back(read_currency());
    sort(mine.begin(),mine.end());
    
    int price = read_currency();
    
    for(int i=0;i<MAX_V;i++){
      A[i] = i; // 1 cent pieces
      X[i] = 1;
    }
    for(int i=0;i<n;i++)
      for(int j=coins[i];j<MAX_V;j++)
        if(A[j] > 1+A[j-coins[i]]){
          A[j] = 1+A[j-coins[i]];
          X[j] = coins[i];
        }
    
    for(int i=0;i<MAX_V;i++) B[i] = -1;
    B[0] = 0;
    
    for(int i=0;i<m;i++)
      for(int j=price-1+mine[i];j-mine[i]>=0;j--)
        if(B[j-mine[i]] != -1)
          if(B[j] < 1+B[j-mine[i]]){
            B[j] = 1+B[j-mine[i]];
            Y[B[j]][j] = mine[i];
          }
    
    int best_diff, best_i = -1;
    
    for(int i=price;i<MAX_V;i++)
      if(B[i] != -1)
        if(best_i == -1 || best_diff > A[i-price]-B[i]){
          best_i = i;
          best_diff = A[i-price]-B[i];
        }
    
    vector<int> ans_line1,ans_line2;
    for(int v=best_i,i=B[best_i];v;v-=Y[i][v],i--){
      ans_line1.push_back(Y[i][v]);
      //cout << v << endl;
    }
    for(int v=best_i-price;v;v-=X[v])
      ans_line2.push_back(X[v]);
    
    reverse(ans_line1.begin(),ans_line1.end());
    reverse(ans_line2.begin(),ans_line2.end());
    
    cout << B[best_i];
    for(const auto& x : ans_line1)
      cout << " " << x/100 << "." << setw(2) << setfill('0') << x%100;
    cout << endl;
    
    cout << A[best_i-price];
    for(const auto& x : ans_line2)
      cout << " " << x/100 << "." << setw(2) << setfill('0') << x%100;
    cout << endl;
    
    return 0;
  }