codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```