Arithmetic Progressions - USACO 1.4.3


arithmeticprogressions - codetrick
An arithmetic progression is a sequence of the form a, a+b, a+2b, ..., a+nb where n=0,1,2,3,... . For this problem, a is a non-negative integer and b is a positive integer.
Write a program that finds all arithmetic progressions of length n in the set S of bisquares. The set of bisquares is defined as the set of all integers of the form p2 + q2 (where p and q are non-negative integers).

TIME LIMIT: 5 secs

PROGRAM NAME: ariprog

INPUT FORMAT

Line 1: N (3 <= N <= 25), the length of progressions for which to search
Line 2: M (1 <= M <= 250), an upper bound to limit the search to the bisquares with 0 <= p,q <= M.

SAMPLE INPUT (file ariprog.in)

5  7  

OUTPUT FORMAT

If no sequence is found, a singe line reading `NONE'. Otherwise, output one or more lines, each with two integers: the first element in a found sequence and the difference between consecutive elements in the same sequence. The lines should be ordered with smallest-difference sequences first and smallest starting number within those sequences first.
There will be no more than 10,000 sequences.

SAMPLE OUTPUT (file ariprog.out)

1 4
37 4
2 8
29 8
1 12
5 12
13 12
17 12
5 20
2 24
http://mangogao.com/read/83.html
首先直接把所有能表示成p2+q2的数算出来,存入一个表中。然后每次从表里选出两个数,以它们的差作为公差,然后扩展,看能否扩展到指定的位。最后将答案进行排序即可。
首先用bool组表示所有范围内的双平方数,枚举每个数列的起点和公差,搜索层数的话用循环分别加0~N-1个公差进行判断。考虑到数据比较大,当首项加上N-1个公差超过了最大范围时break可以稍微优化一点。
int len, q, total = 0;
bool ok, is_pfs[MAX_NUM] = {0};
struct Prog
{
    int a, b;
} ans[MAX_ANS_NUM];
bool compare(Prog x, Prog y)
{
    if (x.b < y.b || (x.b == y.b && x.a < y.a)) return true;
    return false;
}
void get_pfs()
{
    for (int i = 0; i <= q; ++i)
        for (int j = i; j <= q; ++j)
            is_pfs[i * i + j * j] = true;
    // for (int i = 0; i < 2*q*q; ++i)
    // {
    //  if (is_pfs[i]) cout <<"[Debug] pfs: "<<i<<endl;
    // }
}
void solve()
{
    int i, j=0;
    for (i = 0; i <= 2 * q * q; ++i)
    {
        //find the b
        for (j = 1; j <= 2 * q * q; ++j)
        {
            //stop properly
            if ((i + j * (len - 1)) > 2 * q * q) break;
            // suppose it's good
            ok = true;
            // check this prog
            for (int k = 0; k < len; ++k)
                if (!is_pfs[i + j * k])
                {
                    ok = false;
                    break;
                }
            if (ok)
            {
                ans[total++].a = i;
                ans[total - 1].b = j;
                 // cout <<"[Debug] a = "<<i<<" b = " << j <<" "<< total<<endl;
            }
        }
    }
}
int main()
{
    ifstream fin("ariprog.in");
    fin >> len >> q;
    fin.close();
    //get all the pfs
    get_pfs();
    //find the first number of a prog
    solve();
    //sort the answer
    sort(ans, ans + total, compare);
    ofstream fout("ariprog.out");
    if (total == 0)
        fout << "NONE" << endl;
    else
        for (int i = 0; i < total; ++i)
            fout << ans[i].a << " " << ans[i].b << endl;
    fout.close();
    return 0;
}

看了题解发现漏考虑了一个很重要的优化,枚举首项的时候应该直接枚举双平方数,这就要求将双平方数另存一个a[],当然是有序的。其次对于公差,也应该是直接枚举a[]中两个数的差更好。另外两个优化,一个最有效的是我想到的,另一个细节是判断一个数列时从后往前判断。
http://jackneus.com/programming-archives/arithmetic-progressions/
struct prog{
    int base;
    int increm;
    bool operator < (const prog & b) const{
        return increm < b.increm;
    }
};
int N;
vector<prog> progs;
bool valid(vector<bool>& S, int base, int step){
    for(int i = 1; i < N; i++){
        if(!S[base + step * i]) return false;
    }
    return true;
}
int main(){
    ifstream in("ariprog.in");
    ofstream out("ariprog.out");
    int M;
    in >> N >> M;
    vector<bool> S(M * M * 2);
    for(int i = 0; i < S.size(); i++) S[i] = false;
    for(int p = 0; p <= M; p++){
        for(int q = 0; q <= M; q++){
            S[p * p + q * q] = true;
        }
    }
    for(int i = 0; i < S.size(); i++){
        if(S[i]){
            for(int j = 1; j < (S.size() - i) / N + 2 * N; j++){
                if(valid(S, i, j)){
                    prog solut;
                    solut.base = i;
                    solut.increm = j;
                    progs.push_back(solut);
                }
            }
        }
    }
    if(progs.size() != 0){
        sort(progs.begin(), progs.begin() + progs.size());
        for(int i = 0; i < progs.size(); i++){
            out << progs[i].base << " " << progs[i].increm << endl;
        }
    }
    else out << "NONE" << endl;
}
http://leonlu.iteye.com/blog/1125404
首先决定在算术级数中找双平方还是在双平方中找算术级数。直觉是在双平方数中找算术级数,首先生成所有的双平方数,保存在一个boolean数组中,这个数组大小为250×250×2=125000。然后外层循环取a(从1开始在双平方数中取),内层循环取b(从1开始取到(125000-a)/(N-1),因为满足a+(N-1)*b <=125000),得到a,b后要验证是否能构成长度为n的算术级数,若能则储存结果。最后按b,a升序的顺数输出a,b。 

public static void main(String[] args) throws Exception{ BufferedReader in = new BufferedReader(new FileReader("ariprog.in"));
PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(
"ariprog.out")),true);
// read data
int N = Integer.parseInt(in.readLine());
int M = Integer.parseInt(in.readLine());
// max: 250 * 250 * 2 = 125000
int MM2 = M*M*2;
// generate bisquares into a boolean array
// loop times: 251 * 252 /2 = 31626
boolean[] bisquares = new boolean[MM2+1];
for(int p = 0; p <= M; p++)
for(int q = p; q<= M; q++)
bisquares[p*p + q*q] = true;
// search and pruning
List<int[]> res = new ArrayList<int[]>();
for(int a = 0; a < MM2; a++){
if(!bisquares[a]) continue;
label:
for(int b = 1; b <= (MM2-a)/ (N-1); b++){ // a+ (N-1) * b <= MM2
for(int i = 1; i<= N-1; i++){
if(!bisquares[a + b * i])
continue label;
}
res.add(new int[]{a,b});
}
}
// sort and print
Collections.sort(res,new Comparator<int[]>(){
public int compare(int[] o1, int[] o2) {
if(o1[1] < o2[1]) return -1;
if(o1[1] > o2[1]) return 1;
if(o1[0] < o2[0]) return -1;
if(o1[0] < o2[0]) return 1;
return 0;
}});
if(res.size() == 0) out.println("NONE");
for(int[] ab : res)
out.println(ab[0]+ " " + ab[1]);
System.exit(0);
}
http://jusaco.blogspot.com/2013/07/arithmetic-progressions-solution.html
public static void main(String[] args) throws Exception {
BufferedReader in = new BufferedReader(new FileReader("ariprog.in"));
PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(
"ariprog.out")),true);

int N = Integer.parseInt(in.readLine());
int M = Integer.parseInt(in.readLine());
// max: 250 * 250 * 2 = 125000
int MM2 = M*M*2;

boolean[] bisquares = new boolean[MM2+1];
for(int p = 0; p <= M; p++)
for(int q = p; q<= M; q++)
bisquares[p*p + q*q] = true;

List<int[]> res = new ArrayList<int[]>();
for(int a = 0; a < MM2; a++){
if(!bisquares[a]) continue;
label:
for(int b = 1; b <= (MM2-a)/ (N-1); b++){
for(int i = 1; i<= N-1; i++){
if(!bisquares[a + b * i])
continue label;
}
res.add(new int[]{a,b});
}
}

Collections.sort(res,new Comparator<int[]>(){
public int compare(int[] o1, int[] o2) {
if(o1[1] < o2[1]) return -1;
if(o1[1] > o2[1]) return 1;
if(o1[0] < o2[0]) return -1;
if(o1[0] < o2[0]) return 1;
return 0;
}});
if(res.size() == 0) out.println("NONE");
for(int[] ab : res)
out.println(ab[0]+ " " + ab[1]);

System.exit(0);
}
}

https://github.com/TomConerly/Competition-Programming/blob/master/USACO/Chapter1/ariprog.java
Read full article from arithmeticprogressions - codetrick

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts