486 problems solved
Rank by points: #65
Total points: 459
10 contests written
Rank by rating: #109
From Erindale S.S.
Name: Andrew Qi Tang
Main Language: Java
Organization: Triway Education and Erindale Secondary School
Codeforces Username: AQT
Andrew Qi Tang's Hierarchy
Slaves:, , , , , , , ,
Triway Level 4 Sept - Dec:, , ,
If I miss your name, just message me on slack.
Important Milestone For Me
Date Joined: July 7th, 2017
Top 100: October 15th, 2017
69th place and 420 problems done: December 18th, 2017
451 problems and 451 points: December 31st, 2017
This is where I talk about my exprience about Competitve Programming that I would like to share. If you have any interest in my blogs, feel free to check it out anytime. Any suggestions would be appreciated. (if you can somehow contact me) I will try to update it, but it will not be a daily thing.
Dec 10th, 2017
Although, Game Theory problems don't come up that often in CCC or any DMOJ contests, it is still a good idea to study the topic to just be prepared. Game Theory problems that I have encountered so far is a Two Player Game where if two players are trying to win a game and play perfectly, determine the winner (Nim games).
The way how I tackle these types of problem is to follow a general idea.
When you think about it, it does make sense. I want to win the game, so I go to the path where I will win for sure.
I made the connection that this is like a DP problem. The states are just like DP states. I have my base cases such that, I can solve easily. And I build on previous states to determine the winner.
Sometimes, so solution have a pattern in them. Rather than going through all the states a simple inspection can pass all the cases.
(Time limit: 1 sec / Memory Limit: 256 MB)
Alice and Bob are playing a game with matches. Each turn a player may take either one or two matches. The loser is the one where they can not take another match. Alice moves first. Find the winner of this game.
One solution is using a DP like solution. We can store the information in a fixed array of size where each element represents if Alice is going to win or not with that many matches. The base cases are and . If there are one or two matches, then Alice will win because she can just take all of them leaving Bob with none left. Now we can recursively solve it by going up one by one using the general idea. If and are winning states, then is a losing state; otherwise, it is a winning state.
However, the solution above yields the correct solution, it will TLE or MLE. To solve this problem we can find a pattern. If you do a little inspection we can see that every 3rd state is a losing position whereas, everything else is a winning position.
The one above is a simple Game Theory Problem. The ones that DMOJ provides are slightly more challenging.
Dec 13th, 2017
Under the request of, I will be talking about Minimum Spanning Trees (MST) or more specifically Prim's Algorithm.
A Minimum Spanning Tree is a subset of edges that forms a tree with the minimum total edge weights. This is not to be confused with a Shortest Path Tree where a Minimum Spanning Tree will not always give the shortest path between any two nodes.
There are two popular ways of implementing a MST (Prim's Algorithm and Kruskal's Algorithm). The idea of a Prim's is to have two subset of nodes, already part of a Minimum Spanning Tree or not. I'll be naming the two subsets, "visited" and "notvisited" respectively. Also we will have a "minwt" array that will store the for each node the edge that connects it to the tree.
At first, all the nodes will be in subset notvisited as we haven't touched them yet. Now set all the minwt array to an arbritary large number. Make sure you will never reach that point. Now that the set up is done, we can go to the meat of the algorithm.
Find the smallest value in minwt that is in the notvisited section. Now mark visited. Next, for each edge update the minwt of the destination node if the edge going towards it is the smaller than the current minwt. This is also known as the "relaxation of an edge", used in other algorithms such as Dijkstra's Algorithm. Repeat this for until all N nodes are now in the visited section. That's it.
You can also extract even more information from the Prim's such as the parent of the node if using Prim's and the maximum weight that is needed to get to any node. Another very similar problem is the Maximum Spanning Tree.
If you want an example graph that goes through the proccess I highly recommand following the steps from GeeksForGeeks.
Code for Prim's Algorithm on a Adjacency Matrix in Java
Dec 25th, 2017
Merry Christmas Everyone!!! Convinced by the Christmas trees I'll be talking about the basics about trees in graph theory. Trees are an undirected acyclic (no cycles) graph where between any two vertices, there is only one unique path. Compared to a standard graph, trees have many properties that makes certain classical problems a lot easier to solve.
Common Tree Properties
The following are some of the most basic properties in a tree.
To find the longest path in a regular graph takes exponential time. However, to find the longest path in a tree it takes only two DFS/BFS. Start at any node and apply the first DFS/BFS storing all of the distances. Then, find the largest value and store the node. For your second DFS/BFS, store all of the distances again from the node that you just stored. This will always hold true because the longest path from any node is always to one of the diameter's ends. To practice your diameter finding skills: The question.
Jan 14th, 2018 - on hold
Requested by both time. It uses a divide and conquer method to organize the values into segments from the array, represented using a balanced binary tree.and , today's topic will be on segment trees. A segment tree is normally used to solve certain questions that supports both range updates and/or range queries; solving them both in
Above is an example of a segment tree with the intervals labelled in black and the node number labelled in green.
If you notice a segment tree is that every node except for the leaf nodes can be further broken down into two halves. It will break down into halves until it can not be further broken down. So for interval , the segment tree will split into two nodes and where can be calculated by .
In order to access ones children, it can be seen that the left child will be and the right child will be where is the index of the current node tree.
The leaf nodes are single elements. Thus, they can not be further divided any further.
For example: A node stores the interval with an index of 3. Its left child will store the value of range indexed 6 and its right child will store the value of the segment indexed 7. Notice that to calculate , we used integer division.
The node of the segment tree can be what you want to represent, so you can create your own class or struct. If I want to find the minimum, I'll store the minimum of the node. Same with LCM, sum, etc.
A segment tree can be represented as an array, where each index will point towards a node.
After the structure of a segment tree, the next step is processing.