This is a problem from PAT - The Largest Generation.
A family hierarchy is usually presented by a pedigree tree where all the nodes on the same level belong to the same generation. Your task is to find the generation with the largest population.
Each input file contains one test case. Each case starts with two positive integers N (<100) which is the total number of family members in the tree (and hence assume that all the members are numbered from 01 to N), and M (<N) which is the number of family members who have children. Then M lines follow, each contains the information of a family member in the following format:
ID K ID ID … ID[K]
where ID is a two-digit number representing a family member, K (>0) is the number of his/her children, followed by a sequence of two-digit ID’s of his/her children. For the sake of simplicity, let us fix the root ID to be 01. All the numbers in a line are separated by a space.
For each test case, print in one line the largest population number and the level of the corresponding generation. It is assumed that such a generation is unique, and the root level is defined to be 1.
21 1 23
01 4 03 02 04 05
03 3 06 07 08
06 2 12 13
13 1 21
08 2 15 16
02 2 09 10
11 2 19 20
17 1 22
05 1 11
07 1 14
09 1 17
10 1 18
1 9 4
- Mar 16, 2018...more
- Mar 15, 2018...more
Let S be a set of n integral points on the x-axis. For each given interval [a, b], you are asked to count the points lying inside.
The first line contains two integers: n (size of S) and m (the number of queries).
The second line enumerates all the n points in S.
Each of the following m lines consists of two integers a and b and defines an query interval [a, b].
The number of points in S lying inside each of the m query intervals.
1 3 7 9 11
- 0 <= n, m <= 5 * 10^5
- For each query interval [a, b], it is guaranteed that a <= b.
- Points in S are distinct from each other.
- Coordinates of each point as well as the query interval boundaries a and b are non-negative integers not greater than 10^7.
- Time: 2 sec
- Memory: 256 MB
- Mar 12, 2018...more
This is a problem from Leetcode - Champagne Tower.
We stack glasses in a pyramid, where the first row has 1 glass, the second row has 2 glasses, and so on until the 100th row. Each glass holds one cup (250ml) of champagne.
Then, some champagne is poured in the first glass at the top. When the top most glass is full, any excess liquid poured will fall equally to the glass immediately to the left and right of it. When those glasses become full, any excess champagne will fall equally to the left and right of those glasses, and so on. (A glass at the bottom row has it’s excess champagne fall on the floor.)
For example, after one cup of champagne is poured, the top most glass is full. After two cups of champagne are poured, the two glasses on the second row are half full. After three cups of champagne are poured, those two cups become full - there are 3 full glasses total now. After four cups of champagne are poured, the third row has the middle glass half full, and the two outside glasses are a quarter full, as pictured below.
Now after pouring some non-negative integer cups of champagne, return how full the j-th glass in the i-th row is (both i and j are 0 indexed.)
Input: poured = 1, query_glass = 1, query_row = 1
Explanation: We poured 1 cup of champange to the top glass of the tower (which is indexed as (0, 0)). There will be no excess liquid so all the glasses under the top glass will remain empty.
Input: poured = 2, query_glass = 1, query_row = 1
Explanation: We poured 2 cups of champange to the top glass of the tower (which is indexed as (0, 0)). There is one cup of excess liquid. The glass indexed as (1, 0) and the glass indexed as (1, 1) will share the excess liquid equally, and each will get half cup of champange.
- poured will be in the range of [0, 10 ^ 9].
- query_glass and query_row will be in the range of [0, 99].
- Mar 11, 2018...more
This is a problem from Leetcode - All Paths From Source to Target.
Given a directed, acyclic graph of N nodes. Find all possible paths from node 0 to node N-1, and return them in any order.
The graph is given as follows: the nodes are 0, 1, …, graph.length - 1. graph[i] is a list of all nodes j for which the edge (i, j) exists.
Input: [[1,2], , , ]
The graph looks like this:
There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.
- The number of nodes in the graph will be in the range [2, 15].
- You can print different paths in any order, but you should keep the order of nodes inside one path.
- Mar 10, 2018...more
This is a problem from Codeforces - A Leapfrog in the Array.