530.md (7396B)
1 Source: https://codeforces.com/blog/entry/17177 2 3 In this contest we aimed to show that declarative approach to problemsolving can be more convenient than the traditional imperative. However, the first several problems were supposed to aquaint the competitor with the basic language syntax and its libraries. All reference solutions are written by [kit1980](/profile/kit1980 "Specialist kit1980"). 4 5 #### [530A - Quadratic equation](/contest/530/problem/A "VK Cup 2015 - Wild Card Round 1") 6 7 To solve a quadratic equation, one has to use a library function `sqrt` and an if-then-else construct. Besides, this problem was supposed to show that Picat has foating-point numbers. :-) 8 9 ``` 10 main => 11 A = read_real(), B = read_real(), C = read_real(), 12 D = B * B - 4 * A * C, 13 X1 = (-B - sqrt(D)) / (2 * A), 14 X2 = (-B + sqrt(D)) / (2 * A), 15 if D == 0 then 16 println(X1) 17 else 18 printf("%w %w%n", min(X1, X2), max(X1, X2)) 19 end. 20 ``` 21 22 #### [530B - String inside out](/contest/530/problem/B "VK Cup 2015 - Wild Card Round 1") 23 24 A string manipulation problem: library function `slice` allows to get a substring of the given string, `reverse`, well, reverses it, and `++` is concatenation operator. Alternatively, one could use loops and print the answer character-by-character. 25 26 ``` 27 main => 28 S = read_line(), 29 N = length(S), 30 X = reverse(slice(S, 1, N // 2)) ++ reverse(slice(S, 1 + N // 2)), 31 println(X). 32 ``` 33 34 #### [530C - Diophantine equation](/contest/530/problem/C "VK Cup 2015 - Wild Card Round 1") 35 36 This problem can be solved using complete search (for each X check whether a suitable Y exists). The reference solution uses constraint programming, which effectively implements a search with pruning and allows to get rid of explicit search loop. 37 38 ``` 39 import cp. 40 main => 41 A = read_int(), B = read_int(), C = read_int(), 42 X #> 0, Y #> 0, 43 if A * X + B * Y #= C then 44 Solutions = solve_all([X, Y]) 45 else 46 Solutions = [] 47 end, 48 println(length(Solutions)), 49 foreach ([I, J] in Solutions) 50 printf("%d %d%n", I, J) 51 end. 52 ``` 53 54 Expression `A * X + B * Y #= C` sets variable constraint. At this stage the system can understand that there are no solutions and proceeed to `else` branch. Otherwise `solve_all` function will return a list of all solutions. 55 56 #### [530D - Set subtraction](/contest/530/problem/D "VK Cup 2015 - Wild Card Round 1") 57 58 This problem can be solved in a variety of ways, from imperative loops to constraint programming. The reference solution uses library function `subtract` which subtracts one sorted list from another. `A..B` creates a list of integers from A to B. Output is done using list comprehension. This problem is the only one in which our solution uses `:=` — an exclusively imperative destructive assignment operator. 59 60 ``` 61 import ordset. 62 import util. 63 main => 64 X = 1..1000, 65 N = read_int(), 66 foreach (_I in 1..N) 67 A = read_int(), B = read_int(), 68 X := subtract(X, A..B) 69 end, 70 println(join([to_string(V) : V in [length(X) | X]])). 71 ``` 72 73 #### [530E - Sum and product](/contest/530/problem/E "VK Cup 2015 - Wild Card Round 1") 74 75 This problem can be solved in at least two ways. The "math" way requires noticing that a set of N-2 "1"s, one "2" and one "N+D" is always a valid solution. Of course, other solutions might exist, for example for N = 4, D = 1 a valid solution is 1, 1, 3, 3. 76 77 The reference solution uses constraint programming, that allows to avoid thinking and just translate the problem statement to Picat. 78 79 ``` 80 import cp. 81 import util. 82 main => 83 N = read_int(), D = read_int(), 84 Vals = new_list(N), 85 Vals :: 1..10000, 86 prod(Vals) #= sum(Vals) + D, 87 solve(Vals), 88 println(join([to_string(V) : V in Vals])). 89 ``` 90 91 #### [530F - Jumping frogs](/contest/530/problem/F "VK Cup 2015 - Wild Card Round 1") 92 93 This problem uses breadth-first or depth-first search. In Picat, like in Prolog, depth-first search with backtracking is built-in. Tabling technique is used for memoization and for automated search of maximum: expression `table(+, +, +, max)` means that the first three parameters of the predicate are input, the last one is output, and has to be maximized. `?=>` means non-determinism: call to `jump` itself can return different values for same input parameters, so `table` selects the maximal of them. `best_frog` uses the same technique to avoid an explicit loop over frogs to search for the best frog. 94 95 ``` 96 table(+, +, +, max) 97 jump(X, Y, K, Dist) ?=> 98 ( 99 NewX = X + K, NewY = Y ; 100 NewX = X - K, NewY = Y ; 101 NewX = X, NewY = Y + K ; 102 NewX = X, NewY = Y - K 103 ), 104 land(NewX, NewY), 105 jump(NewX, NewY, K, Dist). 106 jump(X, Y, _K, Dist) => 107 Dist = abs(X) + abs(Y). 108 109 table(-, max) 110 best_frog(K, Dist) ?=> 111 between(1, 10, K), 112 jump(0, 0, K, Dist). 113 114 main => 115 N = read_int(), 116 Facts = [$land(X, Y) : _I in 1..N, X = read_int(), Y = read_int()], 117 cl_facts(Facts), 118 best_frog(_K, Dist), 119 println(Dist). 120 ``` 121 122 #### [530G - Levenshtein distance](/contest/530/problem/G "VK Cup 2015 - Wild Card Round 1") 123 124 A classic dynamic programming problem. The reference solution uses tabling to implement recursion with memoization, similar to problem [530F - Jumping frogs](/contest/530/problem/F "VK Cup 2015 - Wild Card Round 1"). 125 126 ``` 127 table(+, +, min) 128 edit(I, J, Cost) ?=> 129 str(S), goal(G), 130 N = length(S), M = length(G), 131 ( 132 I <= N, J <= M, 133 edit(I + 1, J + 1, NextCost), 134 Cost = abs(ord(S[I]) - ord(G[J])) + NextCost 135 ; 136 I <= N, 137 edit(I + 1, J, NextCost), 138 Cost = ord(S[I]) - 0'a + 1 + NextCost 139 ; 140 J <= M, 141 edit(I, J + 1, NextCost), 142 Cost = ord(G[J]) - 0'a + 1 + NextCost 143 ; 144 I > N, J > M, 145 Cost = 0 146 ). 147 148 main => 149 S = read_line(), G = read_line(), 150 cl_facts([$str(S), $goal(G)]), 151 edit(1, 1, Cost), 152 println(Cost). 153 ``` 154 155 #### [530H - Points in triangle](/contest/530/problem/H "VK Cup 2015 - Wild Card Round 1") 156 157 This problem requires a reasonable search of possible triangle vertices with a check whether all points are inside. The points' coordinates can have values up to 100, so the triangle's vertices never need to have coordinates over 200. 158 159 ``` 160 import cp. 161 main => 162 N = read_int(), 163 A :: 1..200, B :: 1..200, 164 foreach (_I in 1..N) 165 Xi = read_int(), Yi = read_int(), 166 B * Xi #<= A * (B - Yi) 167 end, 168 solve([$min(A * B)], [A, B]), 169 println(A * B / 2). 170 ``` 171 172 #### [530I - Different variables](/contest/530/problem/I "VK Cup 2015 - Wild Card Round 1") 173 174 This problem is in fact a graph coloring problem. The reference solution uses constraint programming with `all_distinct` constraint. To speed up program execution one had to notice that the first variable is always 1. With this observation one could also use `all_different` constraint (these two constraints differ in internal algorithm implementation), without it `all_different` is too slow. 175 176 ``` 177 import cp. 178 import util. 179 main => 180 N = read_int(), K = read_int(), 181 Vars = new_array(N), 182 Vars :: 1..N, Vars[1] #= 1, 183 foreach(_I in 1..K) 184 [_ | Indexes] = [to_integer(A) : A in split(read_line())], 185 all_distinct([Vars[Idx] : Idx in Indexes]) 186 end, 187 List = to_list(Vars), MaxC #= max(List), 188 solve([$min(MaxC)], Vars), 189 println(join([to_string(V) : V in Vars])). 190 ```