YoungForest's blog

In this contest, because of carelessness, I forgot to consider the corner case in the first problem: the permutation count of 0 is 1. In the second problem, I simply reversed upper and lower. I got two penalties. Otherwise I probably could have entered the top 100. The problems were relatively simple, all standard problems, and previous original problems could be adapted with small changes.

1175. Prime Arrangements

This week I went to ByteDance to attend the summer camp, and still had classes on Sunday, so I skipped the weekly contest. Then how could I participate in Kick Start? After all, this month’s Round E was the so-called golden round, important for getting interview slots, so I chose to skip the summer camp.

After the summer camp ended, I made up the problems as promised. I have to say, LeetCode is still much less difficult than Kick Start. It feels like Kick Start’s warm-up problems are Medium, and the last two problems are Hard.

1169. Invalid Transactions

Cherries Mesh

Minimum spanning tree.
Pay special attention to the Union-Find implementation: find must use path compression to achieve O(1).
Otherwise it will time out.

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

#include <iostream>
#include <vector>

using namespace std;

struct UF {
	vector<int> parents;
	UF(int n) {
		parents.resize(n);
		for (int i = 0; i < n; ++i) {
			parents[i] = i;
		}
	}

	int find(int x) {
		return parents[x] == x ? x : (parents[x] = find(parents[x]));
	}

	void unio(int x, int y) {
		int px = find(x);
		int py = find(y);
		parents[px] = py;
	}
};

int main() {
	int T;
	cin >> T;
	for (int i = 0; i < T; ++i) {
		int N, M;
		cin >> N >> M;
		UF uf(N);
		int ans = 0;
		for (int j = 0; j < M; ++j) {
			int l, r;
			cin >> l >> r;
			--l;
			--r;
			if (uf.find(l) == uf.find(r)) {
				continue;
			}
			uf.unio(l, r);
			ans += 1;
		}
		ans += (N - 1 - ans) * 2;
		cout << "Case #" << i + 1 << ": " << ans << endl;
	}
	return 0;
}

This week I attended ByteDance’s summer camp. The opening ceremony was on Saturday, so I completed this biweekly contest from the bed in a five-star hotel. It was wonderfully comfortable, and the contest result was still decent.
Since I had to attend the summer camp classes the next morning, I skipped the weekly contest. But I still joined Kick Start Round E in the afternoon, skipping the summer camp class for it. What can I say? I really want to go to Google.

The biweekly contest problems were not hard. They felt like the kind of beginner-level problems you see on other OJs.

The result of this contest was poor again, with a rank in the 400s. The direct reason was that I spent too much time on search pruning for the third problem and did not get it right in one shot. The root cause was that I finally had a two-week holiday at home recently, relaxed my practice, and basically stopped grinding problems; naturally, my hands got rusty. It really matches the saying, “Excellence comes from diligence and is ruined by idleness.” Last week’s rank was also very bad.

1160. Find Words That Can Be Formed by Characters

Ashamedly, my ranking fell back to 400+. I had half an hour to solve the last problem and kept trying to use a segment tree. Just like Kick Start Round D, I got obsessed with segment trees and crashed. The lesson learned is: do not insist that interval problems must be solved with segment trees. There are often simpler approaches.

1154. Day of the Year

This contest was my first time entering the top 100 again after three months, and it was also my second consecutive top-200 finish, so I was a little happy. It swept away the gloom from last week’s Kick Start failure.
In fact, because of a judge issue, the rank I saw right after the contest ended was 56. Later, the official side rejudged the last problem, so some people’s submissions could pass, and there was no penalty time.
This was also a pretty high-quality contest. The problems were not very hard, but they covered knowledge points quite comprehensively, and the difficulty distribution was reasonable.

1144. Decrease Elements To Make Array Zigzag

Yesterday I did the Biweekly Contest, and today I did the regular contest plus Google Kick Start Round D in the afternoon.
Three contests in a row made for a very full weekend.

1137. N-th Tribonacci Number

Rank: 765 / 1866.

X or What

This problem is about finding patterns and tests one’s familiarity with xor. In fact, I had once been very close to the correct solution. But I was fixated on my past experience solving interval problems with segment trees, trying to figure out what information each node should record. As a result, I went further and further off track.

It had been two months since I last participated in a biweekly contest, and the number jumped directly from 1 to 5.
This contest was very simple. All the problems were classic algorithm problems and belonged to the must-know category. After finishing all four problems, I still had nearly an hour left.

1133. Largest Unique Number