In the "large" variety of this problem the B parameter which is the upper bound on the range of integers that are to be examined is 1012. This makes for a huge number of elements to check if you go through each one, find all the factors for that number, then figure out which of those factors are prime, then check every pair of integers in the range for common prime factors. How big is huge? Well given that the range of integers to check is 1012, in the worst case, the number of integer pairs is approx. 1024/2 [= 1012.(1012-1)/2], since nCr = n! / (n-r)! r! . Thus it isn't computationally feasible to try this approach.
A better approach is to attack the problem the other way round. That is, find the prime numbers in the range, then for each prime number find every multiple of it and group them into a common set using the aforementioned disjoint set data structure. Furthermore, we know that for a given interval of consecutive integers [a,b] = {x ∈ ℜ, a ≤ x ≤ b} the "spread" of the interval is (b-a+1). Any prime number greater than or equal to the spread can only have, at most, 1 integer which is a multiple of the prime that falls within the range [a,b]. Why? Because after you have found a multiple of the prime that falls within the range, and then added that prime to this number, it must fall outside the range since the prime is greater than the spread of the interval. The fact that we can have, at most, one factor means no set union will ever take place in this case. Hence we need to only find the prime numbers less than the size of the spread of the interval. For a given upper interval bound, the bigger the interval spread, the fewer the number of prime numbers we need to evaluate.
There are several well published, efficient methods to produce a series of prime numbers, including Sieve of Eratosthenes and the Sieve of Atkin. The running time of Eratosthenes is O((nlogn)(loglogn)), although it has a memory requirement of O(n) in order to store the work-in-progress results. In other words, it's sublinear. I chose the slightly less efficient sieve of Eratosthenes over the Atkin sieve since it is simple to code.
1: using System;
2: using System.Collections.Generic;
3: using System.IO;
4:
5: namespace GoogleCodeJam.NumberSets
6: {
7: public enum NumberType : byte
8: {
9: Unknown = 0, //the default
10: Prime = 1,
11: Composite = 2
12: }
13:
14: //Sieve of Eratosthenes
15: public class PrimeSieve
16: {
17: NumberType[] _values; // NB: this is a zero-based array
18:
19: public PrimeSieve(ulong max) //umax is the upper range limit to check
20: {
21: if (max < 2) throw new ArgumentException();
22:
23: _values = new NumberType[max]; // 0 -> max-1
24: _values[0] = NumberType.Composite; // one is not prime
25: }
26:
27: public List<ulong> ComputePrimes()
28: {
29: List<ulong> primes = new List<ulong>();
30:
31: for (ulong i = 2; i <= (ulong)_values.Length; i++)
32: {
33: if (_values[i - 1] == NumberType.Unknown)
34: {
35: //The next unknown value must be prime
36: _values[i - 1] = NumberType.Prime;
37: primes.Add(i);
38:
39: //All multiples of this prime must be Composite
40: //but we can start at i squared
41: for (ulong j = i * i; j <= (ulong)_values.Length; j += i)
42: {
43: _values[j - 1] = NumberType.Composite;
44: }
45: }
46: }
47: return primes;
48: }
49: }
50:
51: public class DisjointSets
52: {
53: private int _elementCount; // The number of elements in the DisjointSets data structure.
54: private int _setCount; // The number of sets in the DisjointSets data structure.
55: private List<Node> _nodes; // The list of nodes representing the elements
56:
57: // Create an empty DisjointSets data structure
58: public DisjointSets() : this(0) { }
59:
60: // Create a DisjointSet data structure with a specified
61: // number of elements (with element id's from 0 to count-1)
62: public DisjointSets(int count)
63: {
64: _elementCount = 0;
65: _setCount = 0;
66: _nodes = new List<Node>();
67: AddElements(count);
68: }
69:
70: // Returns the number of elements currently in the DisjointSets data structure.
71: public int ElementCount
72: {
73: get { return _elementCount; }
74: }
75:
76: // Returns the number of sets currently in the DisjointSets data structure.
77: public int SetCount
78: {
79: get { return _setCount; }
80: }
81:
82: // Find the set identifier that an element currently belongs to.
83: // Note: some internal data is modified for optimization even though this method is constant.
84: public int FindSet(int elementId)
85: {
86: if (elementId >= _elementCount)
87: throw new ArgumentOutOfRangeException("elementId");
88:
89: // Find the root element that represents the set which `elementId` belongs to
90: Node curNode = _nodes[elementId];
91: while (curNode.Parent != null)
92: curNode = curNode.Parent;
93:
94: Node representative = curNode;
95:
96: // Walk to the representative, updating the parents of `elementId`. Make those elements
97: // the direct children of `representative`. This optimizes the tree for future
98: // FindSet invocations.
99: curNode = _nodes[elementId];
100: while (curNode != representative)
101: {
102: Node next = curNode.Parent;
103: curNode.Parent = representative;
104: curNode = next;
105: }
106:
107: return representative.Index;
108: }
109:
110: // Combine two sets into one. All elements in those two sets will share the
111: // same set id that can be gotten using FindSet.
112: public void Union(int setId1, int setId2)
113: {
114: if (setId1 >= _elementCount) throw new ArgumentOutOfRangeException("setId1");
115: if (setId2 >= _elementCount) throw new ArgumentOutOfRangeException("setId2");
116:
117: Node set1Rep = _nodes[setId1];
118: while (set1Rep.Parent != null)
119: set1Rep = set1Rep.Parent;
120:
121: Node set2Rep = _nodes[setId2];
122: while (set2Rep.Parent != null)
123: set2Rep = set2Rep.Parent;
124:
125: if (set1Rep.Index == set2Rep.Index)
126: return; // already unioned
127:
128: Node set1 = _nodes[setId1];
129: Node set2 = _nodes[setId2];
130:
131: // Determine which node representing a set has a higher rank. The node with the higher rank
132: // is likely to have a bigger subtree so in order to better balance the tree representing
133: // the union, the node with the higher rank is made the parent of the one with the lower
134: // rank and not the other way around.
135: if (set1.Rank > set2.Rank)
136: {
137: set2.Parent = set1;
138: ++set1.Rank;
139: }
140: else if (set1.Rank < set2.Rank)
141: {
142: set1.Parent = set2;
143: ++set2.Rank;
144: }
145: else // set1.Rank == set2.Rank
146: {
147: set2.Parent = set1;
148: ++set1.Rank; // update rank
149: }
150:
151: // Since two sets have fused into one, there is now one less set so update the set count.
152: --_setCount;
153: }
154:
155: // Add a specified number of elements to the DisjointSets data structure.
156: // The element id's of the new elements are numbered
157: // consecutively starting with the first never-before-used elementId.
158: public void AddElements(int addCount)
159: {
160: // insert and initialize the specified number of element nodes to the end of the `_nodes` array
161: for (int i = _elementCount; i < _elementCount + addCount; ++i)
162: {
163: Node newNode = new Node();
164: newNode.Parent = null;
165: newNode.Index = i;
166: newNode.Rank = 0;
167: _nodes.Add(newNode);
168: }
169:
170: // update element and set counts
171: _elementCount += addCount;
172: _setCount += addCount;
173: }
174:
175: // Internal Node data structure used for representing an element.
176: private class Node
177: {
178: public int Rank; // This roughly represent the max height of the node in its subtree.
179: public int Index; // The index of the element the node represents.
180: public Node Parent; // The parent node of the node.
181: }
182: }
183:
184: public class Program
185: {
186: static void Main()
187: {
188: StreamReader file = new System.IO.StreamReader("large.txt");
189: StreamWriter outfile = new System.IO.StreamWriter("output.txt");
190:
191: List<ulong> primes = (new PrimeSieve(1000001)).ComputePrimes();
192:
193: int testCases = Int32.Parse(file.ReadLine());
194: for (int caseNo = 1; caseNo <= testCases; caseNo++) // note this is 1-based
195: {
196:
197: string[] d = (file.ReadLine()).Split(new char[] { ' ' }, StringSplitOptions.None);
198: ulong a = UInt64.Parse(d[0]); // interval start
199: ulong b = UInt64.Parse(d[1]); // interval end
200: ulong p = UInt64.Parse(d[2]); // minimum prime factor
201:
202: int elementCount = (int)(b - a + 1);
203: if (elementCount < 2)
204: {
205: outfile.Write(String.Format("Case #{0}: {1}\r\n", caseNo, 1));
206: }
207: else
208: {
209: DisjointSets sets = new DisjointSets(elementCount);
210:
211: // using a sieve find all prime numbers between P and A
212: foreach (ulong i in primes)
213: {
214: if (i > (ulong)elementCount) break;
215:
216: if (i >= p)
217: {
218: // find all integers in the given range which have this prime factor
219: for (ulong x = (a % i == 0) ? a : (a + i - a % i); x + i <= b; x +=i )
220: {
221: // i is a prime factor of x
222: sets.Union(sets.FindSet((int)(x-a)), sets.FindSet((int)(x+i-a)));
223: }
224: }
225: }
226: outfile.Write(String.Format("Case #{0}: {1}\r\n", caseNo, sets.SetCount));
227: }
228: }
229:
230: file.Close();
231: outfile.Flush();
232: outfile.Close();
233: }
234: }
235: }
236:
Round 1C began with the "Text Messaging Outrage" problem which basically asks that we identify the most efficient letter-to-key assignment on a phone to minimize the number of key presses needed by users. Google quite helpfully provide a frequency distribution for each letter. Given the frequency distribution it's obvious what the optimal assignment is - for the letters that are most frequently used assign them key press combinations that require the fewest key presses. Technically speaking this is a greedy approach and it should be intuitively obvious why it produces the optimal assignment.
