Special Olympics #0

Wanna scratch your problem solving itch? Join the code golf competition with other lainons! The rules are simple: the first post with the text "Roll!" (or anything similar) in the thread decides which problem we will be solving. The post number will be inserted into this simple script as a seed: https://www.ideone.com/1vHLbP First output is the page number (1-79), second output is problem index (0-50) (within the page), problems are taken from here (an ancient high quality source of programming puzzles): https://www.spoj.com/problems/classical/sort=0,start=0 You can solve the problem in any programming language you like, you are free to discuss and comment on other solutions. This is completely optional, but you can submit your solution to SPOJ system to see if it passes all test cases (in this case it should be in one of languages they support), otherwise you can just post it into ideone or any similar system with a bunch of test cases. Other lainons (including me), who are ok with having account on SPOJ, might submit your solution for you to help seeing if passes all test cases, or simply post you some test cases to try.

Roll? Body too long or too empty.

>>43203 Thanks for rolling! Post number is 43203 which means the problem we will be solving is at page 61 index 12: https://www.ideone.com/F8dL6K https://www.spoj.com/problems/classical/sort=0,start=3000 https://www.spoj.com/problems/COLORSEG/

>>43204 https://en.wikipedia.org/wiki/Coprime_integers > In number theory, two integers a and b are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1.[1] Consequently, any prime number that divides a does not divide b, and vice versa. This is equivalent to their greatest common divisor (GCD) being 1.[2] One says also a is prime to b or a is coprime with b. > The numbers 8 and 9 are coprime, despite the fact that neither—considered individually—is a prime number, since 1 is their only common divisor. On the other hand, 6 and 9 are not coprime, because they are both divisible by 3. The numerator and denominator of a reduced fraction are coprime, by definition.

>>43204 Interesting, I'll start pondering this tomorrow, now I'm sleepu and drunk and I barely parsed the problem description. For those who are very new to puzzles like this, here is explanation of the second example (N=3, M=2): Good colorings: 1 1 2 (1+1 coprime to 1+2) 1 2 2 (1+2 coprime to 2+2) 2 1 1 (2+1 coprime to 1+1) 2 2 1 (2+2 coprime to 2+1) Bad colorings: 1 1 1 2 2 2 1 2 1 2 1 2

>>43203 Ah, fuarrrk it. Look ma, it's recursive (and also doesn't memoize a thing) AND it's horribly slow. lisp (import (srfi 1) (chicken format)) (define (coprime-triple? a b c) (define (coprime? a b) (= (gcd a b) 1)) (coprime? (+ a b) (+ b c))) (define (coprime-trip-seq? seq) (cond ((<= (length seq) 2) #t) ((coprime-triple? (car seq) (cadr seq) (caddr seq)) (coprime-trip-seq? (cdddr seq))) (else #f))) (define (coprime-trip-boundary? rev-pre suf) ;; ngl, not proud of this :( (if (and (pair? rev-pre) (pair? (cdr rev-pre)) (cadr rev-pre) (car suf)) (coprime-triple? (car rev-pre) (cadr rev-pre) (car suf)) #t)) (define (coprime-trip-cols sects cols rev-pre) (if (= sects 0) 1 (foldr (lambda (in out) (if (coprime-trip-boundary? rev-pre (list in)) (+ out (coprime-trip-cols (sub1 sects) cols (cons in rev-pre))) out)) 0 (iota cols 1 1)))) (define (summarize-coloring i j) (printf "Triples ~A\nColors ~A\nResult ~A\n" i j (coprime-trip-cols i j '())))

Rolling Something here to make my post long enough

>>43208 > Page 73, problem 47 > https://www.spoj.com/problems/SPLEND1/ Seems annoying Stop banning tor exit nodes

>>43204 I'm gonna sit on this for a while, it's an interesting problem in terms of double penetration dynamic programming.

>>43204 Nice problem, but I need to think

>>43207 I'm gonna register special throwaway account for submissions. If you implement input/output as described in the problem, I can submit it for you to their online system (they support chicken scheme). That system provides some useful output that shows the point at which your solution goes TLE (time limit exceeded) or WA (wrong answer).

>>43215 nah, it will TLE most likely and I can't be bothered to add memoization.

Anons, I fuarrrking did it! From the first fuarrrking try! Locally I was also able to build even the final lookup table fully in compile-time via consexprs, but it requires C++23 and unfortunately SPOJ only supports up to C++14. Anyways, here's the thing: https://ideone.com/V1hoLN #include <array> #include <iostream> #include <vector> using u8 = unsigned char; template <class T> using vec = std::vector<T>; template <class T, int N> using tri_array = std::array<T, (N * (N - 1)) / 2>; const int N = 50; const int M = 50; const int GCD = 101; int idx(int i, int j) { if (i > j) std::swap(i, j); return i * (GCD - 1) - (i * (i - 1)) / 2 + (j - i - 1); } u8 gcd(u8 a, u8 b, const tri_array<u8, GCD> *lookup) { if (a == b) { return a; } else { u8 x = (*lookup)[idx(a, b)]; return x ? x : ((b == 0) ? a : gcd(b, a % b, lookup)); } } tri_array<u8, GCD> build_gcd_lookup() { tri_array<u8, GCD> gcd_lookup{}; for (u8 i = 0; i < GCD; ++i) { for (u8 j = i + 1; j < GCD; ++j) { gcd_lookup[idx(i, j)] = gcd(i, j, &gcd_lookup); } } return gcd_lookup; } const tri_array<u8, GCD> gcd_lookup = build_gcd_lookup(); std::array<long, N * M> build_result_lookup() { std::array<long, N * M> results{}; std::array<long, M * M> original_pair_counts{}; std::array<vec<u8>, M * M> next; for (int i = 1; i <= M; ++i) { for (int j = 1; j <= M; ++j) { int index_ij = (i - 1) * M + (j - 1); original_pair_counts[index_ij] = 1; for (int k = 1; k <= M; ++k) { if (gcd(i + j, j + k, &gcd_lookup) == 1) { next[index_ij].push_back(k); } } } int m = i; int index_1m = (1 - 1) * M + (m - 1); results[index_1m] = m; // n = 1 int index_2m = (2 - 1) * M + (m - 1); results[index_2m] = m * m; // n = 2 } for (int m = 1; m <= M; ++m) { std::array<long, M * M> pair_counts = original_pair_counts; for (int n = 3; n <= N; ++n) { std::array<long, M * M> new_pair_counts{}; for (int i = 1; i <= m; ++i) { for (int j = 1; j <= m; ++j) { int index_ij = (i - 1) * M + (j - 1); for (u8 k : next[index_ij]) { if (k > m) break; int index_jk = (j - 1) * M + (k - 1); new_pair_counts[index_jk] = (new_pair_counts[index_jk] + pair_counts[index_ij]) % 1000003; int index_nm = (n - 1) * M + (m - 1); results[index_nm] = (results[index_nm] + pair_counts[index_ij]) % 1000003; } } } pair_counts = new_pair_counts; } } return results; } int main() { std::array<long, N * M> result_lookup = build_result_lookup(); int t, n, m; std::cin >> t; for (int i = 0; i < t; ++i) { std::cin >> n >> m; std::cout << "Case " << (i + 1) << ": " << result_lookup[(n - 1) * M + (m - 1)] << std::endl; } } The most tricky part is realizing there is no need to keep full prefixes to count all matching combinations - it is enough to keep track of counts of pairs of the last two numbers of sequences at current step, and from those alone, you can build the number of pairs at the next step. I'm sure there are ways to optimize this further with all the fun heuristics which coprimes introduce, but even this already runs impressively well.

>>43238 > From the first fuarrrking try! And by this I mean, all those brutal test cases in SPOJ they sure came up with, all those tight time and memory limits, were passed from the first submission! I unfortunately can't paste better link here because apparently my nickname on SPOJ gets filtered by lainchan, but you can find it here: https://www.spoj.com/status/COLORSEG/

>>43273 I got an easy one lol. Classic me. https://www.spoj.com/problems/NHAY/

My original idea was that there is a single problem per thread so that everyone can look how others solved the same problem and compare code/ideas. The roll mechanic is to make it kinda more fair (ie I didn't pick the problem I already solved). I guess I did a bad job at communicating all this. If everyone solves their own problem it doesn't spawn any discussion so there's little point in the thread. One the other hand, if the problem is so complicated that no one or only a single person can solve it, there is no point either. Maybe I'll try a similar thread but with manually-picked easier problem next time. To make sure it's not too hard, but also not too boringly trivial.

>>43274 https://www.ideone.com/JPpUIM page 56 (1 based) index 12 (0 based) is https://www.spoj.com/problems/TRIISO/ Anyway, soykaf thread, next time OP should just pick the problem on their own and include in OP post, because most of this is way beyond abilities of casuals. Maybe post something hard after people solved 10 medium problems at least, it's not gonna work for just random arbitrary-complexity soykaf that is intended for people who were doing this as a hobby for years or decades regularly.