CF Lieges of Legendre

Solution sketch

When $k\ is\ odd$, $[0, 20]$ = {$0, 1, 0, 1, 2, 0, 2, 0, 1, 0, 1, 0, 1, 0, 1, 0, 2, 0, 1, 0, 2$}.
So for $number <= 4$, the $sg\ value$ needs to be handled differently. For all other numbers, if it is odd, $sg\ value = 0$, otherwise, $sg\ value = (sg\ value\ of (\frac{number}{2}) == 1 ? 2 : 1)$.

When $k\ is\ even$, $[0, 8]$ = {$0, 1, 2, 0, 1, 0, 1, 0, 1…$}. So for $number < 3$, the $sg\ value$ needs to be handled differently. For all other numbers, $number \% 2 == 1 ? 0 : 1$.

HDU 1848 Fibonacci again and again

AC Code

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

#include <bits/stdc++.h>
using namespace std;
vector<int> fib;
int sg[1111];
void gen()
{
    // generate fib
    fib.push_back(1);
    fib.push_back(2);
    for (int i = 2;; i++) {
        fib.push_back(fib[i - 1] + fib[i - 2]);
        if (fib[i] > 1000)
            break;
    }
    // generate sg
    sg[0] = 0;
    sg[1] = 1;
    set<int> has;
    for (int i = 2; i < 1001; i++) {
        has.clear();
        for (int j = 0; j < (int)fib.size() && i - fib[j] >= 0; j++) {
            has.insert(sg[i - fib[j]]);
        }
        for (int j = 0;; j++) {
            if (has.find(j) == has.end()) {
                sg[i] = j;
                break;
            }
        }
    }
}
int main()
{
    gen();
    int m, n, p;
    while (scanf("%d %d %d", &m, &n, &p) == 3 && (m || n || p)) {
        if ((sg[m] ^ sg[n] ^ sg[p]) == 0)
            printf("Nacci\n");
        else
            printf("Fibo\n");
    }
    return 0;
}

Exclusively Edible

AC Code

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

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int ncase;
	scanf("%d", &ncase);
	while(ncase--) {
		int r, c, x, y;
		scanf("%d %d %d %d", &r, &c, &x, &y);
		int val = (x + 1) ^ (r - x) ^ (y + 1) ^ (c - y);
		printf("%s\n", val == 0 ? "Hansel" : "Gretel");
	}
	return 0;
}

Allowance

Solution sketch

The sentence each denomination of coin evenly divides the next-larger denomination is a good lead for you to safely assume that using greedy strategy is fine.

If the coin value is greater than $C$, then there is no need to combine two coins into one. Just distribute them out.

For all other remaining coin values, use greedy strategy (just like coin change), and start with the largest coin value to try to get the total value as close to $C$ using minimal coins as possible. If the total value we can get is not exactly $C$, then we run the greedy algorithm from the smallest coin to the largest one. There is a little trick though, $min(\frac{remaining\ value + current\ coin\ value\ - 1}{current\ coin\ value}, all\ remaining\ coins\ for\ this\ coin\ value)$ can get you the minimal amount of coins by exceeding $C$ no more than the value of the minimal coin value that still have coins available.

This tutorial have a casual prove on this method.

CF733C Epidemic in Monstropolis

Solution Sketch

Key observations:

1. Use prefix table to group initial weights of the monsters to match weights of the monsters after the joke. (make sure to check if grouping is possible or not -> WA test case 119)
2. For each group, if the maximum number in that group has a smaller number on its left or right, then reduction is possible.

Installation

Use brew cask

The easiest way!

brew cask install mactex texstudio

Download packages:

The hard way!

1. MacTex
2. TexStudio

Install Mactex package simply by running the .pkg file and follow its instructions.

Add font

1. Download fonts from Google fonts.
2. Double click on the .ttf file, or use font book to install the font

Installation

Google search for Eclipse IDE for Java Developers.

Auto-completion

For some reason, this feature isn’t activated by default. Hmm….

Go to Eclipse -> preference -> Java -> Editor -> Content Assist, add .abcdefghijklmnopqrstuvwxyz to auto activation triggers for Java.

Doves and bombs

Solution Sketch

Observe the process of finding the articulation points. Keep count of how many times a node $u$ is being referred to as an articulation point. (Notice that the edge to parent won’t be counted!)

AC Code

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

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
#define N 11111
vector<int> g[N];
int dfsTime[N], dfsLow[N], timer, root;
int articulationPoint[N];
typedef pair<int, int> ii;
void dfs(int u, int p) {
	// printf("u %d p %d\n", u, p);
	dfsTime[u] = dfsLow[u] = timer++;
	int child = 0;
	for(auto v : g[u]) {
		if(v == p)
			continue;
		if(dfsTime[v] == 0) {
			child++;
			// printf("v %d\n", v);
			dfs(v, u);
			dfsLow[u] = min(dfsLow[u], dfsLow[v]);
			if(dfsTime[u] <= dfsLow[v] && u != root)
				articulationPoint[u]++;
			if(root == u && child >= 2)
				articulationPoint[root]++;
			// printf("pt %d %d\n", u, articulationPoint[u]);
		} else {
			dfsLow[u] = min(dfsLow[u], dfsTime[v]);
		}
	}
}
bool cmp(ii a, ii b)
{
	if(a.second == b.second)
		return a.first < b.first;
	return a.second > b.second;
}
int main()
{
	int n, m;
	while(scanf("%d %d", &n, &m) == 2 && (n || m)) {
		// init
		for(int i = 0; i < n; i++)
			g[i].clear();
		// build graph
		int u, v;
		while(scanf("%d %d", &u, &v) == 2 && (u != -1 && v != -1)) {
			g[u].push_back(v);
			g[v].push_back(u);
		}
		// find articulation point
		memset(dfsTime, 0, sizeof(dfsTime));
		memset(dfsLow, 0, sizeof(dfsLow));
		memset(articulationPoint, 0, sizeof(articulationPoint));
		for(int i = 0; i < n; i++) {
			if(dfsTime[i] == 0) {
				timer = 1;
				root = i;
				dfs(i, -1);
			}
		}
		vector<ii> res;
		for(int u = 0; u < n; u++) {
			res.push_back(ii(u, articulationPoint[u] + 1));
		}
		sort(res.begin(), res.end(), cmp);
		for(int i = 0; i < m; i++)
			printf("%d %d\n", res[i].first, res[i].second);
		printf("\n");
	}
	return 0;
}

CF712C Memory and De-Evolution

Solution Sketch

Key observation: It’s pretty hard to come up with the solution working from x to y. But, how about working your way back from y to x?

Hint: The next possible/best move is turn $(4, 4, 4)$ into $(4, 4, 7)$. Why 7? Because it’s in the range of $4 \leq x < 4 + 4 = 8$, which won’t form a degenerate triangle. Better yet, it’s the greatest among the range!

AC code

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

import java.io.*;
import java.util.*;
public class C
{
    public static void main(String[] args)
    {
        MyScanner sc = new MyScanner();
        out = new PrintWriter(new BufferedOutputStream(System.out));
        int a = sc.nextInt(), b = sc.nextInt();
        ArrayList<Integer> inp = new ArrayList<Integer>();
        inp.add(b);
        inp.add(b);
        inp.add(b);
        Collections.sort(inp);
        int ans = 0;
        while(true) {
        	if( inp.get(0).intValue() == inp.get(1).intValue()
                && inp.get(1).intValue() == inp.get(2).intValue()
                &&  inp.get(0).intValue() == a )
        		break;
        	ans++;
        	inp.remove(0);
        	inp.add(Math.min(inp.get(0) + inp.get(1) - 1, a));
        	Collections.sort(inp);
        }
        out.println(ans);
        out.close();
    }
    public static PrintWriter out;
    public static class MyScanner
    {
        BufferedReader br;
        StringTokenizer st;
        public MyScanner()
        {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        boolean hasNext()
        {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                    return false;
                }
            }
            return true;
        }
        String next()
        {
            if (hasNext())
                return st.nextToken();
            return null;
        }
        int nextInt()
        {
            return Integer.parseInt(next());
        }
    }
}

CF707C Pythagorean Triples

Solution Sketch

Using Euclid's formula