Editorial.md

Contest Tutorial

Getting Gold :

• the problem is Simple : just do a simple recursive function that given the position of the player tries and get Gold from unvisited cells, and stops when a risk of a trap is found

int n, m, x, y;
const int MAX_SIZE = 51;
string grid[MAX_SIZE];
bool visited[MAX_SIZE][MAX_SIZE];

int solve(int x, int y){
    
    if(grid[x][y] ==  '#' || visited[x][y]){
        return 0;
    }
    
    int g = grid[x][y] == 'G' ? 1: 0;
    
    visited[x][y] = true;
    
    if (grid[x-1][y] == 'T' || grid[x][y-1] == 'T'
        || grid[x+1][y] == 'T' || grid[x][y+1] == 'T')
      return g;
    
    g += solve(x - 1, y)
          + solve(x, y - 1)
          + solve(x + 1, y)
          + solve(x, y + 1);
    return g;

}

int main(int argc , char* argv[]) {

    cin >> m >> n;
    for(int i= 0;i < n ; i++){
        cin >> grid[i];
        memset(visited[i], false, sizeof(visited[i]));
        for(int j = 0; j < m ; j++){
            if(grid[i][j] == 'P'){
                x = i;
                y = j;
                break;
            }
        }
    }
    cout << solve(x,y) << endl;

}

Treasure Hunt :

• Another Simple problem just do what the probelm is asking, follow the instruction after reading the map and display the result

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author MaxHeap
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TreasureHunt solver = new TreasureHunt();
        solver.solve(1, in, out);
        out.close();
    }

    static class TreasureHunt {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            int m = in.nextInt();
            char[][] grid = new char[n][m];
            int tx = -1, ty = -1;
            for (int i = 0; i < n; i++) {
                grid[i] = in.next().toCharArray();
                for (int j = 0; j < m; j++) {
                    if (grid[i][j] == 'T') {
                        tx = i;
                        ty = j;
                    }
                }
            }
            int sx = 0, sy = 0;
            int ans = 0;
            boolean[][] visited = new boolean[n][m];
            while (true) {
                if (sx == tx && sy == ty) {
                    out.println(ans);
                    return;
                }
                if (sx < 0 || sy < 0 || sx >= n || sy >= m) {
                    out.println("Out");
                    return;
                }
                if (visited[sx][sy]) {
                    out.println("Lost");
                    return;
                }
                visited[sx][sy] = true;
                char cur = grid[sx][sy];
                if (cur == 'N') {
                    sx--;
                } else if (cur == 'S') {
                    sx++;
                } else if (cur == 'W') {
                    sy--;
                } else if (cur == 'E') {
                    sy++;
                }
                ++ans;
            }
        }

    }

The backslash Problem

• another simple problem, but kind of tricky, multiple levels of interpretation will lead you directly to think about recursion, and after seeing the constraints n <= 8 the recursive solution does not look so bad after all .
• firstly you must define what is a special character this part is easy just create a boolean array and mark special characters (ones that must be escaped)

boolean[] special = new boolean[256];
for (int i = ‘[‘; i <= ‘]’; i++) {
    special[i] = true;
}
for (int i = ‘!’; i <= ‘*’; i++) {
    special[i] = true;
}

• after that you just create the recursive function that given a string tries and interpret it to n levels of interpretation

public static String rec(String s, int n) {
    if (n == 0) return s;
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        if (special[s.charAt(i)]) {
            if (s.charAt(i) == ‘\\’) {
                sb.append(« \\ »);
            } else {
                sb.append(« \\ »);
            }
        }
        sb.append(s.charAt(i));
    }
    return rec(sb.toString(), n - 1);
}

Judging Troubles

• this one needs some thinking, but as soon as you get the gist of it it’s the easiest to implement, first you read the verdicts of the first judge, and count the number of times a verdict occured (in a dictionnary)
• the second step is to read the second judge’s verdicts one by one and determine whether the verdicts exist in the first created dictionnary
• the observation is :
  • if the the verdict still exist in the dictionnary then we check it’s count, if the count is bigger than one we decrement the count otherwise we remove the key . (more compact solutions exist . in my eyes this is the simplest)

n, count = int(input()), dict()
ans = 0
for i in range(n):
  s = input()
  if s in count: count[s] += 1
  else: count[s] = 1

for i in range(n):
  s = input()
  if s in count:
    val = count[s]
    if val > 1: 
      ans += 1
      count[s] = val - 1
    else:
      ans += 1
      del count[s]

print(ans)