Code Jam 2015 is close, so I wanna practice resolving Hacker cup 2015’s problems. Let’s begin.

Homework

The problem introduces the term primacity as:

Let an integer positive and a prime number, the primacity of is the amount of which divides it.

For example: Let , its primacity is becuase divide it.

The problem ask us: Given 3 numbers , how many integers in the inclusive range have a primacity of exactly

Constraints:

, Let the number of test cases

Clearly, we need to have a list of primes numbers for used later, we can use a modified of the Sieve of Eratosthenes. Let an array with length with initialized values of 0, the principle idea here is that each time that we found a in the sieve we increment by to thought , where is a number lesser than . Then, when we ask if in the interval has primacity , just we need to check out if . After that only we increment an by 1 each time that last statement is true for get the final answer. The complexity of this task is the same than the Sieve: for the integers .

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
typedef long long ll
#define MAXN 10000001

ll L[MAXN];

void sieve(){
  memset(L, 0, sizeof(L));
  for(ll i = 2; i <= MAXN; i++){
    if(L[i] == 0){
      for(ll j = i; j <= MAXN; j+=i)
        L[j]++;
    }
  }
}

int main(){
  int T;
  ll a, b, k, r;
  cin >> T;
  for(int i = 1; i <= T; i++){
    r = 0;
    cin >> a >> b >> k;
    for(ll j = a; j <= b; j++){
      if(L[j] == k) r++;
    }
    cout << "Case #" << i << ": " << r << "\n";
  }
  return 0;
}

Autocomplete

In layman’s terms the problem asks us:

If you have distinct words in a dictionary, What’s the sum up for each smallest non-empty prefix of the word for autocomplete it. Where

As the problem said, we need get the smallest non-empty prefix, so we are talking about a Trie. The time insertion is of course , where is the length of the word. Apart of the trie, we initialize two arrrays and both in 0’s. So when we are inserting the word in the trie, we take a initialized in 0, then we equal in the trie and we increment by one. What happen if ? It does mean that the answer is because already we found the smallest non-empty prefix, in otherwise, the answer will be the length complete of the word.

The worst case is when we need to type all the word, so the total complexity of the problem is , where .

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
#define MAXN 1000004

int trie[MAXN][27], step[MAXN], deep_word[MAXN];
int top;

int add(string s){
  int x = 0, deep = 1, ans = -1;
  for(int i = 0; i < s.size(); i++){
    int nxt = trie[x][s[i]-'a'];
    if(nxt == -1)
      trie[x][s[i]-'a'] = top++;
    x = trie[x][s[i]-'a'];
    step[x]++;
    deep_word[x] = deep++;
    if(ans == -1 && step[x] == 1)
      ans = deep_word[x];
  }
  if(ans == -1) ans = s.size();
  return ans;
}

int main(){
  int t, n, ans;
  string s;
  cin >> t;
  for(int i = 1; i < t; i++){
    top = 1;
    memset(trie, -1, sizeof(trie)); 
    memset(step, 0, sizeof(step)); 
    ans = 0;
    cin >> n; while(n--){
      cin >> s;
      ans += add(s);
    }
    cout << "Case #" << i << ": " << ans << "\n";
  }
  return 0;
}

Winning at Sports

We have scores are denoted by two hyphen-separated integers where is you and you always win. Then, the problem introduces two terms:

Stress-free victory: You score the first point and from then on you always have more points than your opponent.

Stressful victory: You never have more points than your opponent until after their score is equal to their final score.

Then the problem asks us: Given the final score of a game of Sports, how many ways could you arrange the order in which the points are scored such that you secure a stress-free or stressful win?

We can resolve this problem using dynamic programming technique. The solution is both case are similar, but the conditions change.

Let the final score, then for stress-free victory we have:

stress_free(, ) if () return 0, because it’s not a stress-free victory
stress_free(, ) if () return 0, becuase it’s not a stress-free victory
stress_free(, ) if () rerturn 1, because it’s a stress-free victory
dp[][] = stress_free(, ) + stress_free(, )

For stressful:

stress_free(, ) if () return 0, because it’s not a stressful victory
stress_free(, ) if () return 0, becuase it’s not a stressful victory
stress_free(, ) if () rerturn 1, because it’s a stressful victory
dp[][] = stressful(, ) + stressful(, )

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
#define MAXN 2004
#define MOD 1000000007

int dp1[MAXN][MAXN], dp2[MAXN][MAXN];
int A, B;

int stress_free(int a, int b){
  if(a <= b) return 0;
  if(a > A || b > B) return 0;
  if(a == A && b == B) return 1;

  int &r = dp1[a][b];

  if(r == -1){
    r = stress_free(a+1, b) + stress_free(a, b+1);
    r %= MOD;
  }

  return r;
}

int stressful(int a, int b){
  if(a > b) return 0;
  if(a > A || b > B) return 0;
  if(b == B) return 1;

  int &r = dp2[a][b];

  if(r == -1){
    r = stressful(a+1, b) + stressful(a, b+1);
    r %= MOD;
  }

  return r;
}

int main(){
  ios_base::sync_with_stdio(false);
  int t;
  char c;
  for(int i = 1; i <= t; i++){
    cin >> A >> c >> B;
    memset(dp1, -1, sizeof(dp1));
    memset(dp2, -1, sizeof(dp2));
    cout << "Case #"  << i << ": " << stress_free(1, 0) << " ";
    cout << stressful(0, 0) << "\n";
  }
  return 0;
}

Corporate Gifting

This is a kind Graph coloring problem. The employees are the nodes, so we build a vector with adjacency list to save the relation. We use dynamic programming technique to dertemine the sum of all the colors , what it is MAXK? It is the maximum numbers of colors for each node, so we’ll assume that max color is 32, in otherwise, we will not able to compute it.

For each node we go through all its parents, and after we go throught [1, 32> possible chromatic number, actually we do something like Dijkstra’s algorithm. We have a variable , so . After that just we add up

The complexity of the problem is , thanks to the DP.

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
#define MAXN 270000
#define MAXK 32
#define INF 0x3f3f3f3f

vector<int> adj[MAXN];
int DP[MAXN][MAXK], J=0;

int solving(int a, int b){
  if(DP[a][b] == -1){
    DP[a][b] = 0;
    for(int i = 0; i < (int)adj[a].size(); i++){
      int next = DP[a][i];
      int tmp = INF;
      for(int j = 1; j < MAXK; j++){
        if(b == j) continue;
        if(tmp > j + solving(next, j)) J = max(J, j);
        tmp = min(tmp, j + solving(next, j));
      }
      DP[a][b] += tmp;
    }
  }
  return DP[a][b];
}

int main(){
  int t, n, tmp;
  cin >> t;
  for(int i = 1; i <= t; i++){
    cin >> n;
    for(int e = 0; e <= n; e++) adj[e].clear();
    for(int j = 1; j <= n; j++){
      cin >> tmp;
      adj[tmp].push_back(j);
    }
    memset(DP, -1, sizeof(DP));
    cout << "Case #" << i << ": " << solving(0, 0) << "\n";
  }
  return 0;
}

You can find the codes here: Codes solutions

The full problems: Facebook Hacker Cup 2015 Round 1