This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Disjoint: | |
''' | |
Disjoinset class, support three main methods: | |
+ make_set(X): return a set for a vertexes v | |
+ find_set(X): find out which set X are in | |
+ union(a, b): union two set a,b and remove a,b | |
''' | |
def __init__(self): | |
self.sets = set() | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def merge_sort(arr): | |
if len(arr) <= 1: | |
return arr | |
# divide into two parts | |
mid = (len(arr)+1)//2 | |
left = arr[:mid] | |
right = arr[mid:] | |
# recursive call on both parts | |
left = merge_sort(left) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def breadth_first_search(start, n, graph, DISTANCE=6): | |
from collections import deque | |
parent_table = dict() | |
distance= dict() # store distance from start to other nodes | |
visited = set() | |
waiting_list = deque() # support remove front O(1) | |
# set up distance | |
for v in range(1, n+1): | |
distance[v] = 0 | |
waiting_list.append(start) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
''' | |
Given x, count how many a (0 < a < x) such that: | |
a xor x > x | |
- a < x means the first set bit (bit 1) in 'x' is '0' in a | |
example: | |
x = 110101 | |
=> a = 0xxxxx | |
with each bit in a, if it is 0, then if we turn it to 1, there will be 2 to ther power of (number of bits that are left). |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
''' | |
Use positional list to maintain O(1) on 'add' operation | |
Use one more attribute _prev in _Node to get the next last element | |
But first we have to maintain the last element by _last_node | |
As we removing, _last_node is assigned to _prev of it | |
PositionalList is a doubly linked list with structure: | |
head <=> node1 <=> node2 <=> ... <=> noden <=> tail | |
''' |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
''' | |
given n, find the number of x, such that | |
0 <= x <= n | |
n + x = n xor x | |
1. We can iterate from 0 to n: O(n) | |
2. Analyze: | |
n + i = n^i + n&i | |
since n + i = n^i => n&i == 0 | |
we count unset bit in n and calculatew 2 to the power of that value |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
''' | |
1. sort | |
2. set min as first pair | |
3. compair consecutive pair with min | |
''' | |
from sys import stdin, stdout | |
n = int(stdin.readline()) | |
a = [int(x) for x in stdin.readline().split()] | |
a.sort() |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Empty(Exception): | |
pass | |
class _DoublyLinkedBase: | |
''' | |
Abstract base class for double linked list | |
''' | |
class _Node: | |
__slots__ = '_element', '_next', '_prev' |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
''' | |
Priority Queue: | |
- Unsorted Double Linked List implementation | |
- Sorted Double Linked List implemenration | |
- Array-based Binary Tree implementation | |
- Positional List is a doubly linked list: | |
head <=> node1 <=> node2 <=> ... <=> noden <=> tail | |
''' | |
from DoublyLinkedList import PositionalList |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
''' | |
First you find 8 end points of 8 directions (if they exist) | |
Then go through k obstacle points, update if they are smaller than the end point | |
Smaller means near the queen position | |
Then if they are mark as updated means they are obstacles and | |
should be - 1 in the total squares | |
''' | |
from sys import stdin, stdout |