• Sign Up
• Login
• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

_no0B Apr 25th, 2019 95 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. /// Longest common increasing subsequence of A and B in O(n * m)
2. #define MAX 2057
3. int lcis(int n, int* A, int m, int* B){
4.     int i, j, l, res, dp[MAX] = {0};
5.     for (i = 0; i < n; i++){
6.         for (l = 0, j = 0; j < m; j++){
7.             if (A[i] == B[j] && dp[j] <= l) dp[j] = l + 1;
8.             else if (B[j] < A[i] && dp[j] > l) l = dp[j];
9.         }
10.     }
11.     for (i = 0, res = 0; i < m; i++){
12.         if (dp[i] > res) res = dp[i];
13.     }
14.     return res;
15. }
16.
17.
18.
19. /// Knight's Tour In Infinite Chessboard
20. /// Minimum number of knight moves from (x,y) to (0,0) in non-negative infinite chessboard
21. int knight_move(int x, int y){
22.     int a, b, z, c, d;
23.     x = abs(x), y = abs(y);
24.     if (x < y) a = x, x = y, y = a;
25.     if (x == 2 && y == 2) return 4;
26.     if (x == 1 && y == 0) return 3;
27.     if (y == 0 || (y << 1) < x){
28.         c = y & 1;
29.         a = x - (c << 1), b = a & 3;
30.         return ((a - b) >> 1) + b + c;
31.     }
32.     else{
33.         d = x - ((x - y) >> 1);
34.         z = ((d % 3) != 0), c = (x - y) & 1;
35.         return ((d / 3) * 2) + c + (z * 2 * (1 - c));
36.     }
37. }
38.
39.
40. /// Maximum XOR Subest
41. #define MAX 100010
42. #define bitlen(x) ((x) == 0 ? (0) : (64 - __builtin_clzll(x)))
43. long long ar[MAX];
44. long long solve(int n, long long* ar){ /// hash = 220650
45.     vector <long long> v[64];
46.     for (int i = 0; i < n; i++) v[bitlen(ar[i])].push_back(ar[i]);
47.     long long m, x, res = 0;
48.     for (int i = 63; i > 0; i--){
49.         int l = v[i].size();
50.         if (l){
51.             m = v[i][0];
52.             res = max(res, res ^ m);
53.
54.             for (int j = 1; j < l; j++){
55.                 x = m ^ v[i][j];
56.                 if (x) v[bitlen(x)].push_back(x);
57.             }
58.             v[i].clear();
59.         }
60.     }
61.     return res;
62. }
63.
64.
65.
66. /// N queen
67. int n, lim, counter;
68. void backtrack(int i, int c, int l, int r){
69.     if (!i){
70.         counter++;
71.         return;
72.     }
73.     int bitmask, x;
74.     --i, bitmask = lim & ~(l | r | c);
75.     while (bitmask){
76.         x = (-bitmask & bitmask);
77.         if (!x) return;
78.         bitmask ^= x;
79.         backtrack(i, c | x, (l | x) << 1, (r | x) >> 1);
80.     }
81. }
82. int main(){
83.     while (scanf("%d", &n)){
84.         counter = 0, lim = (1 << n) - 1;
85.         backtrack(n, 0, 0, 0);
86.         printf("%d solutions for a %d x %d chessboard\n", counter, n, n);
87.     }
88.     return 0;
89. }
90.
91.
92.
93. /// next small
94. #define MAX 250010
95. int ar[MAX], L[MAX], R[MAX], stack[MAX], time[MAX];
96. void next_small(int n, int* ar, int* L){
97.     int i, j, k, l, x, top = 0;
98.
99.     for (i = 0; i < n; i++){
100.         x = ar[i];
101.         if (top && stack[top] >= x){
102.             while (top && stack[top] >= x) k = time[top--];
103.             L[i] = (i - k + 2);
104.             stack[++top] = x;
105.             time[top] = k;
106.         }
107.         else{
108.             L[i] = 1;
109.             stack[++top] = x;
110.             time[top] = i + 1;
111.         }
112.     }
113. }
114. /*** L[i] contains maximum length of the range from i to the left such that the minimum of this range
115.      is not less than ar[i].
116.      Similarly, R[i] contains maximum length of the range from i to the right such that the minimum
117.      of this range is not less than ar[i]
118.
119.      For example, ar[] = 5 3 4 3 1 2 6
120.                   L[]  = 1 2 1 4 5 1 1
121.                   R[]  = 1 3 1 1 3 2 1
122. ***/
123. void fill(int n, int* ar, int* L, int* R){
124.     int i, j, k;
125.     for (i = 0; i < n; i++) L[i] = ar[n - i - 1];
126.     next_small(n, L, R);
127.     next_small(n, ar, L);
128.     i = 0, j = n - 1;
129.     while (i < j){
130.         k = R[i], R[i] = R[j], R[j] = k;
131.         i++, j--;
132.     }
133. }
134. int main(){
135.     int n, i, j, k;
136.     scanf("%d", &n);
137.     for (i = 0; i < n; i++) scanf("%d", &ar[i]);
138.     fill(n, ar, L, R);
139.     for (i = 0; i < n; i++) printf("%d ", ar[i]);
140.     puts("");
141.     for (i = 0; i < n; i++) printf("%d ", R[i]);
142.     puts("");
143.     for (i = 0; i < n; i++) printf("%d ", L[i]);
144.     puts("");
145.     return 0;
146. }
147.
148.
149.
150. /// output compression
151. int base = 0, mp[256];
152. char digit[256], str[256], temp[256];
153. void Generate(){
154.     int i;
155.     for (i = 32; i < 127; i++){
156.         if (i == 32 || i == 34 || i == 39 || i == 44 || i == 92) continue;
157.         digit[base] = i;
158.         mp[i] = base;
159.         base++;
160.     }
161.     digit[base] = 0;
162. }
163. void encode(char* str, int v){
164.     int i, j, k = 0, l = 0;
165.     do{
166.         temp[k++] = digit[v % base];
167.         v /= base;
168.     } while (v);
169.     for (i = k - 1; i >= 0; i--) str[l++] = temp[i];
170.     str[l] = 0;
171. }
172. int decode(char* str){
173.     int i, v = 0;
174.     for (i = 0; str[i]; i++) v = (v * base) + mp[str[i]];
175.     return v;
176. }
177. int main(){
178.     read();
179.     Generate();
180.     encode(str, 12345);
181.     printf("%d\n", decode(str));
182.     return 0;
183. }
184.
185.
186.
187. /// Permutation Index
188. #define MAX 12
189. #define hash(ar)  dp[ar[0]][ar[1]][ar[2]][ar[3]][ar[4]][ar[5]]
190. #define lexic(ar) pos[ar[0]][ar[1]][ar[2]][ar[3]][ar[4]][ar[5]]
191. char ar[MAX];
192. int n, m, counter, factorial[MAX];
193. int last[1 << MAX], dp[MAX][MAX][MAX][MAX][MAX][MAX], pos[MAX][MAX][MAX][MAX][MAX][MAX];
194. void backtrack(int i, int bitmask, int flag){
195.     if (i == m){
196.         if (flag & 1) hash(ar) = ++counter;
197.         if (flag & 2) lexic(ar) = last[bitmask]++;
198.         return;
199.     }
200.     int j;
201.     for (j = 0; j < n; j++){
202.         if (!(bitmask & (1 << j))){
203.             ar[i] = j;
204.             backtrack(i + 1, bitmask | (1 << j), flag);
205.         }
206.     }
207. }
208. void Generate(){
209.     int i, j;
210.     clr(ar), clr(last);
211.     counter = 0, m = n >> 1, factorial[0] = 1;
212.     for (i = 1; i < MAX; i++) factorial[i] = factorial[i - 1] * i;
213.     if (n & 1){
214.         backtrack(0, 0, 1);
215.         m++;
216.         backtrack(0, 0, 2);
217.         m--;
218.     }
219.     else backtrack(0, 0, 3);
220. }
221. int F(int P[MAX]){
222.     int i, a = 0, b = 0;
223.     char A[6] = {0}, B[6] = {0};
224.     for (i = 0; i < m; i++) A[a++] = P[i];
225.     for (i = m; i < n; i++) B[b++] = P[i];
226.     return ((hash(A) - 1) * factorial[b]) + lexic(B) + 1;
227. }
228. int main(){
229.     int i, j, P[MAX];
230.     while (scanf("%d", &n) != EOF){
231.         Generate();
232.         for (i = 0; i < n; i++) scanf("%d", &P[i]);
233.         for (i = 0; i < n; i++) P[i]--;
234.         int res = F(P);
235.         printf("%d\n", res);
236.     }
237.     return 0;
238. }
239.
240.
241.
242. /// Permutation Rank
243. /// Find's the rank of permutation
244. /// Rank and permutation elements are 1 base indexed
245. long long find_rank(vector <int> permutation){
246.     long long res = 1;
247.     int i, j, n = permutation.size();
248.     vector <bool> visited(n + 1, false);
249.     vector <long long> factorial(n + 1, 1);
250.     for (i = 1; i <= n; i++) factorial[i] = factorial[i - 1] * i;
251.     for (i = 1; i <= n; i++){
252.         for (j = 1; j <= n; j++){
253.             if (!visited[j]){
254.                 if (permutation[i - 1] == j){
255.                     visited[j] = true;
256.                     break;
257.                 }
258.                 res += factorial[n - i];
259.             }
260.         }
261.     }
262.     return res;
263. }
264. /// Find's the k'th permutation of 1 to n
265. /// Rank and permutation elements are 1 base indexed
266. vector <int> find_rank(int n, long long k){
267.     int i, j;
268.     vector <int> res(n, 0);
269.     vector <bool> visited(n + 1, false);
270.     vector <long long> factorial(n + 1, 1);
271.     for (i = 1; i <= n; i++) factorial[i] = factorial[i - 1] * i;
272.     for (i = 1; i <= n; i++){
273.         for (j = 1; j <= n; j++){
274.             if (!visited[j]){
275.                 if (factorial[n - i] >= k){
276.                     visited[j] = true;
277.                     res[i - 1] = j;
278.                     break;
279.                 }
280.                 k -= factorial[n - i];
281.             }
282.         }
283.     }
284.     return res;
285. }
286.
287.
288.
289. /// Josephus
290. /// Josephus problem, n people numbered from 1 to n stand in a circle.
291. /// Counting starts from 1 and every k'th people dies
292. /// Returns the position of the m'th killed people
293. /// For example if n = 10 and k = 3, then the people killed are 3, 6, 9, 2, 7, 1, 8, 5, 10, 4 respectively
294. /// O(n)
295. int josephus(int n, int k, int m){
296.     int i;
297.     for (m = n - m, i = m + 1; i <= n; i++){
298.         m += k;
299.         if (m >= i) m %= i;
300.     }
301.     return m + 1;
302. }
303. /// O(k log(n))
304. long long josephus2(long long n, long long k, long long m){ /// hash = 583016
305.     m = n - m;
306.     if (k <= 1) return n - m;
307.
308.     long long i = m;
309.     while (i < n){
310.         long long r = (i - m + k - 2) / (k - 1);
311.         if ((i + r) > n) r = n - i;
312.         else if (!r) r = 1;
313.         i += r;
314.         m = (m + (r * k)) % i;
315.     }
316.     return m + 1;
317. }
318. int main(){
319.     int n, k, m;
320.     printf("%d\n", josephus(10, 1, 2));
321.     printf("%d\n", josephus(10, 1, 10));
322. }
323.
324.
325.
326. /// IDAStar
327. int ida(int g, int lim, int l, int last, int idx){ /// last = last taken move, don't go there!
328.     int h = heuristic(l);
329.     if (!h){ /// Goal reached
330.         sequence[idx] = 0;
331.         puts(sequence);
332.         return g;
333.     }
334.     int f = g + h;
335.     if (f > lim) return f;
336.     int i, j, res = inf;
337.     for (i = 0; i < 12; i++){
338.         if (dis[l][i] == 1 && i != last){
339.             sequence[idx] = str[i];
340.             swap(str[l], str[i]);
341.             int x = ida(g + 1, lim, i, l, idx + 1);
342.             if (x < res) res = x; /// Update next limit in iterative deepening
343.             swap(str[l], str[i]);
344.             if (res <= lim) return res; /// Since iterative deepening, return if solution found
345.         }
346.     }
347.     return res;
348. }
349. int Solve(int l){
350.     int lim = heuristic(l);
351.     for (; ;){
352.         int nlim = ida(0, lim, l, l, 0);
353.         if (nlim <= lim) return nlim;
354.         else lim = nlim;
355.     }
356.     return -1;
357. }
358.
359.
360.
361. /// Histogram Area
362. #define MAX 2010
363. int n, ar[MAX];
364. /*** Largest area in a histogram ***/
365. /*** Be careful, long long might be required ***/
366. int histogram(int n, int* ar){
367.     int i = 0, j, a, x, top = 0, res = 0;
368.     stack[0] = -1;
369.     while (i < n){
370.         if (!top || (ar[stack[top]] <= ar[i]) ) stack[++top] = i++;
371.         else{
372.             x = stack[top--];
373.             a = ar[x] * (i - stack[top] - 1);
374.             if (a > res) res = a;
375.         }
376.     }
377.     while (top){
378.         x = stack[top--];
379.         a = ar[x] * (i - stack[top] - 1);
380.         if (a > res) res = a;
381.     }
382.     return res;
383. }
384.
385.
386.
387. /// HashMap
388. using namespace std;
389. struct hashmap{
390.     int t, sz, hmod;
391.     vector <int> id;
392.     vector <long long> key, val;
393.     inline int nextPrime(int n){
394.         for (int i = n; ;i++){
395.             for (int j = 2; ;j++){
396.                 if ((j * j) > i) return i;
397.                 if ((i % j) == 0) break;
398.             }
399.         }
400.         return -1;
401.     }
402.     void clear(){t++;}
403.     inline int pos(unsigned long long x){
404.         int i = x % hmod;
405.         while (id[i] == t && key[i] != x) i++;
406.         return i;
407.     }
408.     inline void insert(long long x, long long v){
409.         int i = pos(x);
410.         if (id[i] != t) sz++;
411.         key[i] = x, val[i] = v, id[i] = t;
412.     }
413.     inline void erase(long long x){
414.         int i = pos(x);
415.         if (id[i] == t) key[i] = 0, val[i] = 0, id[i] = 0, sz--;
416.     }
417.     inline long long find(long long x){
418.         int i = pos(x);
419.         return (id[i] != t) ? -1 : val[i];
420.     }
421.     inline bool contains(long long x){
422.         int i = pos(x);
423.         return (id[i] == t);
424.     }
425.     inline void add(long long x, long long v){
426.         int i = pos(x);
427.         (id[i] == t) ? (val[i] += v) : (key[i] = x, val[i] = v, id[i] = t, sz++);
428.     }
429.     inline int size(){
430.         return sz;
431.     }
432.     hashmap(){}
433.     hashmap(int m){
434.         srand(time(0));
435.         m = (m << 1) - ran(1, m);
436.         hmod = nextPrime(max(100, m));
437.         sz = 0, t = 1;
438.         id.resize(hmod + 0x1FF, 0);
439.         key.resize(hmod + 0x1FF, 0), val.resize(hmod + 0x1FF, 0);
440.     }
441. };
442.
443.
444.
445. /// HakmemItem175
446. /// Only for non-negative integers
447. /// Returns the immediate next number with same count of one bits, -1 on failure
448. long long hakmemItem175(long long n){
449.     if (n == 0) return -1;
450.     long long x = (n & -n);
451.     long long left = (x + n);
452.     long long right = ((n ^ left) / x) >> 2;
453.     long long res = (left | right);
454.     return res;
455. }
456. /// Returns the immediate previous number with same count of one bits, -1 on failure
457. long long lol(long long n){
458.     if (n == 0 || n == 1) return -1;
459.     long long res = ~hakmemItem175(~n);
460.     return (res == 0) ? -1 : res;
461. }
462.
463.
464.
465. /// Greedy Coin Change
466. const int n = 10;
467. const long long INF = 0x7FFFFFFFFFFFFFFF;
468. const int coins[] = {0, 1, 5, 10, 20, 50, 100, 200, 500, 1000, 2000}; /// 1 based indexing for coins
469. long long res, counter[44], sum[44]; /// counter[i] = number of coins of type i
470. void backtrack(int i, long long p, long long c){ /// Complexity 2^n
471.     if (p == 0 && c < res) res = c; /// Change min to max here
472.     if (i == 0 || p <= 0) return;
473.
474.     long long k, x = 0;
475.     if ((p - sum[i - 1]) > x) x = p - sum[i - 1];
476.     k = (x / coins[i]) + (x % coins[i] != 0);
477.     if (k <= counter[i]) backtrack(i - 1, p - k * coins[i], c + k);
478.     if (++k <= counter[i]) backtrack(i - 1, p - k * coins[i], c + k); /// Do this multiple times if WA (around 5 or 10 should do)
479. }
480. /// Minimum number of coins required to make s from coin values and count of coin values
481. /// -1 if no solution
482. long long solve(long long s){
483.     int i, j;
484.     for (i = 1; i <= n; i++) sum[i] = sum[i - 1] + coins[i] * counter[i];
485.     res = INF;
486.     backtrack(n, s, 0);
487.     if (res == INF) res = -1;
488.     return res;
489. }
490.
491.
492.
493. /// gray codes
494. long long gray_code(long long x){
495.     return x ^ (x >> 1);
496. }
497. long long inverse_gray_code(long long x){
498.     long long h = 1, res = 0;
499.     do{
500.         if (x & 1) res ^= h;
501.         x >>= 1, h = (h << 1) + 1;
502.     } while (x);
503.     return res;
504. }
505.
506.
507.
508. /// Gambler's ruin problem
509. /// First player has n1 coins, second player has n2 coins
510. /// After each move, first player wins with probability p and second player wins with probability q (p + q == 1)
511. /// The loser gives 1 coin to the winner
512. /// When number of coins reaches 0, a player loses
513. /// Returns the probability of first player winning
514. long double expo(long double x, int n){
515.     if (n == 0) return 1;
516.     if (n & 1) return expo(x, n - 1) * x;
517.     else{
518.         long double res = expo(x, n >> 1);
519.         return res * res;
520.     }
521. }
522. long double gamblers_ruin(int n1, int n2, long double p, long double q){
523.     if (fabs(p - q) <= 1e-9){
524.         return (long double)n2 / (n1 + n2);
525.     }
526.
527.     long double x = 1.0 - expo(q / p, n2);
528.     long double y = 1.0 - expo(q / p, n1 + n2);
529.     return (x / y);
530. }
531.
532.
533.
534. /// Faulhaber's Formula
535. #define MAX 2510
536. #define MOD 1000000007
537. int S[MAX][MAX], inv[MAX];
538. int expo(long long x, int n){
539.     x %= MOD;
540.     long long res = 1;
541.     while (n){
542.         if (n & 1) res = (res * x) % MOD;
543.         x = (x * x) % MOD;
544.         n >>= 1;
545.     }
546.     return (res % MOD);
547. }
548. void Generate(){
549.     int i, j;
550.     for (i = 0; i < MAX; i++) inv[i] = expo(i, MOD - 2);
551.     S[0][0] = 1;
552.     for (i = 1; i < MAX; i++){
553.         S[i][0] = 0;
554.         for (j = 1; j <= i; j++){
555.             S[i][j] = ( ((long long)S[i - 1][j] * j) + S[i - 1][j - 1]) % MOD;
556.         }
557.     }
558. }
559. int faulhaber(long long n, int k){
560.     n %= MOD;
561.     if (!k) return n;
562.     int j;
563.     long long res = 0, p = 1;
564.     for (j = 0; j <= k; j++){
565.         p = (p * (n + 1 - j)) % MOD;
566.         res = (res + (((S[k][j] * p) % MOD) * inv[j + 1])) % MOD;
567.     }
568.     return (res % MOD);
569. }
570. int main(){
571.     Generate();
572.     printf("%d\n", faulhaber(1001212, 1000));
573.     return 0;
574. }
575.
576.
577.
578. /// Faulhaber's Formula (Custom Algorithm)
579. #define MAX 1010
580. #define MOD 1000000007
581. namespace fool{
582.     #define MAXN 10000
583.     tr1::unordered_map <unsigned long long, int> mp;
584.     int inv, P[MAX], binomial[MAX][MAX], dp[MAXN][MAX];
585.     long long expo(long long x, long long n){
586.         x %= MOD;
587.         long long res = 1;
588.         while (n){
589.             if (n & 1) res = (res * x) % MOD;
590.             x = (x * x) % MOD;
591.             n >>= 1;
592.         }
593.         return (res % MOD);
594.     }
595.     void init(){
596.         int i, j;
597.         mp.clear();
598.         inv = expo(2, MOD - 2);
599.         P[0] = 1;
600.         for (i = 1; i < MAX; i++){
601.             P[i] = (P[i - 1] << 1);
602.             if (P[i] >= MOD) P[i] -= MOD;
603.         }
604.         for (i = 0; i < MAX; i++){
605.             for (j = 0; j <= i; j++){
606.                 if (i == j || !j) binomial[i][j] = 1;
607.                 else{
608.                     binomial[i][j] = (binomial[i - 1][j] + binomial[i - 1][j - 1]);
609.                     if (binomial[i][j] >= MOD) binomial[i][j] -= MOD;
610.                 }
611.             }
612.         }
613.         for (i = 1; i < MAXN; i++){
614.             long long x = 1;
615.             for (j = 0; j < MAX; j++){
616.                 dp[i][j] = dp[i - 1][j] + x;
617.                 if (dp[i][j] >= MOD) dp[i][j] -= MOD;
618.                 x = (x * i) % MOD;
619.             }
620.         }
621.     }
622.     /// Returns (1^k + 2^k + 3^k + .... n^k) % MOD
623.     long long F(unsigned long long n, int k){
624.         if (n < MAXN) return dp[n][k];
625.         if (n == 1) return 1;
626.         if (n == 2) return (P[k] + 1) % MOD;
627.         if (!k) return (n % MOD);
628.         if (k == 1){
629.             n %= MOD;
630.             return (((n * (n + 1)) % MOD) * inv) % MOD;
631.         }
632.         unsigned long long h = (n << 10LL) | k; /// Change hash function according to limits of n and k
633.         long long res = mp[h];
634.         if (res) return res;
635.         if (n & 1) res = F(n - 1, k) + expo(n, k);
636.         else{
637.             long long m, z;
638.             m = n >> 1;
639.             res = (F(m, k) * P[k]) % MOD;
640.             m--, res++;
641.             for (int i = 0; i <= k; i++){
642.                 z = (F(m, i) * binomial[k][i]) % MOD;
643.                 z = (z * P[i]) % MOD;
644.                 res += z;
645.             }
646.         }
647.         res %= MOD;
648.         return (mp[h] = res);
649.     }
650.     long long faulhaber(unsigned long long n, int k){
651.         ///fool::init();
652.         return F(n, k);
653.     }
654. }
655. int main(){
656.     fool::init();
657.     int t, i, j;
658.     long long n, k, res;
659.     cin >> t;
660.     while (t--){
661.         cin >> n >> k;
662.         res = fool::faulhaber(n, k);
663.         cout << res << endl;
664.     }
665.     return 0;
666. }
667.
668.
669.
670. /// CKY algo
671. The Cockeâ€“Youngerâ€“Kasami algorithm (alternatively called CYK, or CKY) is a parsing algorithm for context-free grammars,
672. named after its inventors, John Cocke, Daniel Younger and Tadao Kasami. It employs bottom-up parsing and dynamic programming.
673.
674. The standard version of CYK operates only on context-free grammars given in Chomsky normal form (CNF).
675. However any context-free grammar may be transformed to a CNF grammar expressing the same language.
676.
677. The importance of the CYK algorithm stems from its high efficiency in certain situations. Using Landau symbols,
678. the worst case running time of CYK is O(N^3 * |G|), where N is the length of the parsed string and |G| is the
679. size of the CNF grammar G. This makes it one of the most efficient parsing algorithms in terms of worst-case
680. asymptotic complexity, although other algorithms exist with better average running time in many practical scenarios.
681.
682. Pseudocode:
683.
684. let the input be a string S consisting of n characters: a1 ... an.
685. let the grammar contain r nonterminal symbols R1 ... Rr.
686. This grammar contains the subset Rs which is the set of start symbols.
687. let P[n,n,r] be an array of booleans. Initialize all elements of P to false.
688. for each i = 1 to n
689.   for each unit production Rj -> ai
690.     set P[1,i,j] = true
691. for each i = 2 to n -- Length of span
692.   for each j = 1 to n-i+1 -- Start of span
693.     for each k = 1 to i-1 -- Partition of span
694.       for each production RA -> RB RC
695.         if P[k,j,B] and P[i-k,j+k,C] then set P[i,j,A] = true
696. if any of P[n,1,x] is true (x is iterated over the set s, where s are all the indices for Rs) then
697.   S is member of language
698. else
699.   S is not member of language
700.
701.
702.
703. /// Combsort
704. #define MAX 1000010
705. int n, ar[MAX];
706. void combsort(int n, int* ar){
707.     if (n <= 1) return;
708.     int i, j, x, g = n, flag = 0;
709.     while ((g != 1) || flag){
710.         flag = 0;
711.         if (g != 1) g *= 0.77425;
712.         for (i = 0; (i + g) < n; i++){
713.             if (ar[i] > ar[i + g]){
714.                 flag = 1;
715.                 x = ar[i], ar[i] = ar[i + g], ar[i + g] = x;
716.             }
717.         }
718.     }
719. }
720. int main(){
721.     int i, j;
722.     n = MAX - 10;
723.     for (i = 0; i < n; i++) ar[i] = (rand() << 15 ^ rand()) % MAX;
724.     combsort(n, ar);
725.     for (i = 0; (i + 1) < n; i++){
726.         if (ar[i] > ar[i + 1]) puts("fail");
727.     }
728.     return 0;
729. }
730.
731.
732. /// bit hacks
733. unsigned int reverse_bits(unsigned int v){
734.     v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1);
735.     v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2);
736.     v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4);
737.     v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8);
738.     return ((v >> 16) | (v << 16));
739. }
740. /// Returns i if x = 2^i and 0 otherwise
741. int bitscan(unsigned int x){
742.     __asm__ volatile("bsf %0, %0" : "=r" (x) : "0" (x));
743.     return x;
744. }
745. /// Returns next number with same number of 1 bits
746. unsigned int next_combination(unsigned int x){
747.     unsigned int y = x & -x;
748.     x += y;
749.     unsigned int z = x & -x;
750.     z -= y;
751.     z = z >> bitscan(z & -z);
752.     return x | (z >> 1);
753. }
754.
755.
756. /// Bitset Iteration
757. char bithash[67];
758. void init(){
759.     int i;
760.     for (i = 0; i < 64; i++) bithash[(1ULL << i) % 67] = i;
761. }
762. void iterate(unsigned long long x){
763.     while (x){
764.         unsigned long long y = (x & -x);
765.         int i = bithash[y % 67];
766.         x ^= y;
767.         printf("%d\n", i);
768.     }
769. }
770. int main(){
771.     init();
772.     unsigned long long x = 0b100000001011000100100101001010101001010100;
773.     iterate(x);
774.     return 0;
775. }
776.
777.
778.
779. /// Algorithm X + Dancing Links
780. #define MAXR 100010
781. #define MAXC 100010
782. #define MAXNODE 100010
783. /// Define MAX limits appropriately, set to large values for safety
784. /// Dancing Links data structure to solve exact cover problems
785. /// There are some constraints as columns and a number of rows
786. /// Each row satisfies some constraints
787. /// Objective is to select a subset of rows so that each constraint is satisfied exactly once
788. /// Don't forget to initialize first by calling init()
789. namespace dlx{ /// hash = 641985
790.     int row[MAXNODE], col[MAXNODE];
791.     int L[MAXNODE], R[MAXNODE], U[MAXNODE], D[MAXNODE];
792.     int n, idx, len, selected_rows[MAXR], column_count[MAXC];
793.     void init(int ncolumn){ /// initialize first with total number of columns (1 based)
794.         memset(column_count, 0, sizeof(column_count));
795.         n = ncolumn, idx = n + 1;
796.         for (int i = 0; i <= n; i++) U[i] = D[i] = i, L[i] = i - 1, R[i] = i + 1;
797.         L[0] = n, R[n] = 0;
798.     }
799.     /// r = index of row (1 based)
800.     /// the vector columns contain the columns which are satisfied with this row
801.     inline void addrow(int r, vector <int>& columns){ /// hash = 438353
802.         int i, c, l = columns.size(), first = idx;
803.         for (i = 0; i < l; i++){
804.             c = columns[i];
805.             L[idx] = idx - 1, R[idx] = idx + 1, D[idx] = c, U[idx] = U[c];
806.             D[U[c]] = idx, U[c] = idx, row[idx] = r, col[idx] = c;
807.             column_count[c]++, idx++; /// column_count[c] is the number of rows which satisfies constraint column c
808.         }
809.         R[idx - 1] = first, L[first] = idx - 1;
810.     }
811.     /// Removes column c from the structure
812.     inline void remove(int c){ /// hash = 377852
813.         L[R[c]] = L[c], R[L[c]] = R[c];
814.         for (int i = D[c]; i != c; i = D[i]){
815.             for (int j = R[i]; j != i; j = R[j]){
816.                 column_count[col[j]]--;
817.                 U[D[j]] = U[j], D[U[j]] = D[j];
818.             }
819.         }
820.     }
821.     /// Restores the position of column c in the structure
822.     inline void restore(int c){ /// hash = 804101
823.         for (int i = U[c]; i != c; i = U[i]){
824.             for (int j = L[i]; j != i; j = L[j]){
825.                 column_count[col[j]]++;
826.                 U[D[j]] = j, D[U[j]] = j;
827.             }
828.         }
829.         L[R[c]] = c, R[L[c]] = c;
830.     }
831.     /// Recursively enumerate to solve exact cover
832.     bool algorithmX(int depth){ /// hash = 308201
833.         if(R[0] == 0){
834.             len = depth;
835.             return true;
836.         }
837.         int i, j, c = R[0];
838.         for (i = R[0]; i != 0; i = R[i]){ /// Select a column deterministically
839.             if(column_count[i] < column_count[c]) c = i; /// if multiple columns exist, choose the one with minimum count
840.         }
841.         remove(c);
842.         bool flag = false;
843.         for (i = D[c]; i != c && !flag; i = D[i]){ /// While solution is not found
844.             selected_rows[depth] = row[i];
845.             for (j = R[i]; j != i; j = R[j]) remove(col[j]);
846.             flag |= algorithmX(depth + 1); /// May be select rows non-deterministically here with random_shuffle?
847.             for (j = L[i]; j != i; j = L[j]) restore(col[j]);
848.         }
849.         restore(c);
850.         return flag;
851.     }
852.     bool exact_cover(vector<int>& rows){ /// Returns the subset of rows satisfying exact cover, false otherwise
853.         rows.clear();
854.         if(!algorithmX(0)) return false;
855.         for(int i = 0; i < len; i++) rows.push_back(selected_rows[i]);
856.         return true;
857.     }
858. }
859. namespace sudoku{
860.     inline int encode(int n, int a, int b, int c){ /// Encode information
861.         return (a * n * n) + (b * n) + c + 1;
862.     }
863.     inline void decode(int n, int v, int& a, int& b, int& c){ /// Decode information
864.         v--;
865.         c = v % n, v /= n;
866.         b = v % n, a = (v / n) % n;
867.     }
868.     bool solve(int n, int ar[25][25]){
869.         int i, j, k, l, c;
870.         int m = sqrt(n + 0.5); /// m * m sub-grid
871.         int ncolumn = n * n * 4; /// n * n for cells, n * n for rows, n * n for columns and n * n for boxes
872.         dlx::init(ncolumn);
873.         for (i = 0; i < n; i++){
874.             for (j = 0; j < n; j++){
875.                 for (k = 0; k < n; k++){
876.                     if (ar[i][j] == 0 || ar[i][j] == (k + 1)){
877.                         vector <int> columns;
878.                         columns.push_back(encode(n, 0, i, j)); /// Each cell can contain only 1 value
879.                         columns.push_back(encode(n, 1, i, k)); /// Row[i] can contain only ar[i][j], if ar[i][j] != 0, otherwise it can contain any value
880.                         columns.push_back(encode(n, 2, j, k)); /// Column[j] can contain only ar[i][j], if ar[i][j] != 0, otherwise it can contain any value
881.                         columns.push_back(encode(n, 3, (i / m) * m + j / m, k)); /// Similarly for box numbered i / m * m + j / m
882.                         /// Current row selection, place number k in the cell[i][j] and doing so will cover all columns in the columns vector
883.                         int cur_row = encode(n, i, j, k);
884.                         dlx::addrow(cur_row, columns);
885.                     }
886.                 }
887.             }
888.         }
889.         vector<int> res;
890.         if (!dlx::exact_cover(res)) return false;
891.         for (l = 0; l < res.size(); l++){
892.             decode(n, res[l], i, j, k);
893.             ar[i][j] = k + 1;
894.         }
895.         return true;
896.     }
897. }
898.
899.
900.
901. /// 15-Puzzle (Manhattan distance + Linear conflict heuristic)
902. #define inf 1010
903. #define swap(x, y) (x ^= y, y ^= x, x ^= y)
904. #define F(i, j) (abs(((ar[i][j] - 1) >> 2) - i) + abs( ((ar[i][j] - 1) & 3) - j))
905. bool flag;
906. char str[60];
907. char dir[] = "LRUD";
908. int dx[] = {0, 0, -1, 1};
909. int dy[] = {-1, 1, 0, 0};
910. int len[4] = {0}, idx[4][4], ar[4][4], transpose[4][4];
911. int row_conflict(int rc){
912.     int i, j, k, x, y, res = 0;
913.     for (i = 0; i < 4; i++){
914.         x = (ar[rc][i] >> 2);
915.         if (ar[rc][i] != 16) idx[x][len[x]++] = ar[rc][i];
916.     }
917.     for (i = 0; i < 4; i++){
918.         if (len[i] > 1){
919.             for (j = 0; j < len[i]; j++){
920.                 for (k = j + 1; k < len[i]; k++){
921.                     if (idx[i][j] > idx[i][k]) res += 2;
922.                 }
923.             }
924.         }
925.         len[i] = 0;
926.     }
927.     return res;
928. }
929. int column_conflict(int rc){
930.     int i, j, k, x, y, res = 0;
931.     for (i = 0; i < 4; i++){
932.         x = (ar[i][rc] & 3);
933.         if (ar[i][rc] != 16) idx[x][len[x]++] = ar[i][rc];
934.     }
935.     for (i = 0; i < 4; i++){
936.         if (len[i] > 1){
937.             for (j = 0; j < len[i]; j++){
938.                 for (k = j + 1; k < len[i]; k++){
939.                     if (idx[i][j] > idx[i][k]) res += 2;
940.                 }
941.             }
942.         }
943.         len[i] = 0;
944.     }
945.     return res;
946. }
947. int heuristic(int bx, int by){
948.     int i, j, k, l, res, linear_conflict = 0, manhattan_distance = 0;
949.     for (i = 0; i < 4; i++){
950.         for (j = 0; j < 4; j++){
951.             transpose[j][i] = ar[i][j];
952.             if (ar[i][j] != 16){
953.                 manhattan_distance += F(i, j);
954.             }
955.         }
956.         linear_conflict += row_conflict(i);
957.         linear_conflict += column_conflict(i);
958.     }
959.     res = manhattan_distance + linear_conflict;
960.     return res;
961. }
962. int ida(int bx, int by, int lx, int ly, int g, int lim, int d, int h){
963.     if (flag) return;
964.     if (!h){
965.         if (!flag){
966.             flag = true;
967.             str[d] = 0;
968.             puts(str);
969.         }
970.         return g;
971.     }
972.     int f = g + h;
973.     if (f > lim) return f;
974.     int i, k, l, nh, r, res = inf;
975.     for (i = 0; i < 4; i++){
976.         k = bx + dx[i], l = by + dy[i];
977.         if (k >= 0 && k < 4 && l >= 0 && l < 4 && !(k == lx && l == ly)){
978.             nh = h;
979.             nh -= F(k, l);
980.             if (bx != k) nh -= row_conflict(bx), nh -= row_conflict(k);
981.             if (by != l) nh -= column_conflict(by), nh -= column_conflict(l);
982.             swap(ar[bx][by], ar[k][l]);
983.             nh += F(bx, by);
984.             if (bx != k) nh += row_conflict(bx), nh += row_conflict(k);
985.             if (by != l) nh += column_conflict(by), nh += column_conflict(l);
986.             str[d] = dir[i];
987.             r = ida(k, l, bx, by, g + 1, lim, d + 1, nh);
988.             swap(ar[bx][by], ar[k][l]);
989.             if (r < res) res = r;
990.             if (r <= lim) return r;
991.         }
992.     }
993.     return res;
994. }
995. int Solve(int bx, int by){
996.     int res, lim = heuristic(bx, by);
997.     flag = false;
998.     for (; ;){
999.         res = ida(bx, by, bx, by, 0, lim, 0, heuristic(bx, by));
1000.         if (res <= lim) return res;
1001.         else lim = res;
1002.     }
1003. }
1004. bool Solvable(int bx, int by){
1005.     int i, j, r = 0, counter = 0;
1006.     for (i = 0; i < 16; i++){
1007.         if (ar[i >> 2][i & 3] == 16) r = (i >> 2);
1008.         else{
1009.             for (j = i + 1; j < 16; j++){
1010.                 if (ar[j >> 2][j & 3] < ar[i >> 2][i & 3]) counter++;
1011.             }
1012.         }
1013.     }
1014.     return ((counter + r) & 1);
1015. }
1016. int main(){
1017.     int t, i, j, k, bx, by;
1018.     scanf("%d", &t);
1019.     while (t--){
1020.         for (i = 0; i < 4; i++){
1021.             for (j = 0; j < 4; j++){
1022.                 scanf("%d", &ar[i][j]);
1023.                 if (!ar[i][j]){
1024.                     bx = i, by = j;
1025.                     ar[i][j] = 16;
1026.                 }
1027.             }
1028.         }
1029.         if (!Solvable(bx, by)) puts("This puzzle is not solvable.");
1030.         else{
1031.             int res = Solve(bx, by);
1032.             if (res > 50) puts("This puzzle is not solvable.");
1033.         }
1034.     }
1035.     return 0;
1036. }
1037. /*
1038.
1039. 5
1040.
1041. 2 3 4 0
1042. 1 5 7 8
1043. 9 6 10 12
1044. 13 14 11 15
1045.
1046.
1047. 6 2 8 4
1048. 12 14 1 10
1049. 13 15 3 9
1050. 11 0 5 7
1051.
1052. 6 8 4 2
1053. 12 14 1 10
1054. 13 15 3 9
1055. 11 0 5 7
1056.
1057. 13 1 2 4
1058. 5 0 3 7
1059. 9 6 10 12
1060. 15 8 11 14
1061.
1062. 0 12 9 13
1063. 15 11 10 14
1064. 3 7 2 5
1065. 4 8 6 1
1066. */
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!

Top