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.

530A - Quadratic equation

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. :-)

main =>
    A = read_real(), B = read_real(), C = read_real(),
    D = B * B - 4 * A * C,
    X1 = (-B - sqrt(D)) / (2 * A),
    X2 = (-B + sqrt(D)) / (2 * A),
    if D == 0 then
        println(X1)
    else
        printf("%w %w%n", min(X1, X2), max(X1, X2))
    end.

530B - String inside out

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.

main =>
    S = read_line(),
    N = length(S),
    X = reverse(slice(S, 1, N // 2)) ++ reverse(slice(S, 1 + N // 2)),
    println(X).

530C - Diophantine equation

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.

import cp.
main =>
    A = read_int(), B = read_int(), C = read_int(),
    X #> 0, Y #> 0,
    if A * X + B * Y #= C then
        Solutions = solve_all([X, Y])
    else
        Solutions = []
    end,
    println(length(Solutions)),
    foreach ([I, J] in Solutions)
        printf("%d %d%n", I, J)
    end.

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.

530D - Set subtraction

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.

import ordset.
import util.
main =>
    X = 1..1000,
    N = read_int(),
    foreach (_I in 1..N)
        A = read_int(), B = read_int(),
        X := subtract(X, A..B)
    end,
    println(join([to_string(V) : V in [length(X) | X]])).

530E - Sum and product

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.

The reference solution uses constraint programming, that allows to avoid thinking and just translate the problem statement to Picat.

import cp.
import util.
main =>
    N = read_int(), D = read_int(),
    Vals = new_list(N),
    Vals :: 1..10000,
    prod(Vals) #= sum(Vals) + D,
    solve(Vals),
    println(join([to_string(V) : V in Vals])).

530F - Jumping frogs

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.

table(+, +, +, max)
jump(X, Y, K, Dist) ?=>
    (
      NewX = X + K, NewY = Y ;
      NewX = X - K, NewY = Y ;
      NewX = X, NewY = Y + K ;
      NewX = X, NewY = Y - K
    ),
    land(NewX, NewY),
    jump(NewX, NewY, K, Dist).
jump(X, Y, _K, Dist) =>
    Dist = abs(X) + abs(Y).

table(-, max)
best_frog(K, Dist) ?=>
    between(1, 10, K),
    jump(0, 0, K, Dist).

main =>
    N = read_int(),
    Facts = [$land(X, Y) : _I in 1..N, X = read_int(), Y = read_int()],
    cl_facts(Facts),
    best_frog(_K, Dist),
    println(Dist).

530G - Levenshtein distance

A classic dynamic programming problem. The reference solution uses tabling to implement recursion with memoization, similar to problem 530F - Jumping frogs.

table(+, +, min)
edit(I, J, Cost) ?=>
    str(S), goal(G),
    N = length(S), M = length(G),
    (
        I <= N, J <= M,
        edit(I + 1, J + 1, NextCost),
        Cost = abs(ord(S[I]) - ord(G[J])) + NextCost
    ;
        I <= N,
        edit(I + 1, J, NextCost),
        Cost = ord(S[I]) - 0'a + 1 + NextCost
    ;
        J <= M,
        edit(I, J + 1, NextCost),
        Cost = ord(G[J]) - 0'a + 1 + NextCost
    ;
        I > N, J > M,
        Cost = 0
    ).

main =>
    S = read_line(), G = read_line(),
    cl_facts([$str(S), $goal(G)]),
    edit(1, 1, Cost),
    println(Cost).

530H - Points in triangle

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.

import cp.
main =>
    N = read_int(),
    A :: 1..200, B :: 1..200,
    foreach (_I in 1..N)
        Xi = read_int(), Yi = read_int(),
        B * Xi #<= A * (B - Yi)
    end,
    solve([$min(A * B)], [A, B]),
    println(A * B / 2).

530I - Different variables

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.

import cp.
import util.
main =>
    N = read_int(), K = read_int(),
    Vars = new_array(N),
    Vars :: 1..N, Vars[1] #= 1,
    foreach(_I in 1..K)
        [_ | Indexes] = [to_integer(A) : A in split(read_line())],
        all_distinct([Vars[Idx] : Idx in Indexes])
    end,
    List = to_list(Vars), MaxC #= max(List),
    solve([$min(MaxC)], Vars),
    println(join([to_string(V) : V in Vars])).