Solving Programming Problems in CF

In this article, we’ll take a look at how I solved FranceIOI / others basic programming problems, using CF, and how you can get into competitive programming too !

Give these problems a go in you favorite language, and then you can check on my CF solutions !

Library Problem

Form (translated):

Form

A library owns nbBooks books, indexed from 0 to nbBooks - 1. Every day, a few clients ask to borrow a book for a certain duration.

Your program should first read two integers on the first line: nbBooks <= 100 and nbDays. For every day, the program will read a line containing a nbClients, and for each client, read 2 other integers, corresponding to the index of the book, and the duration. It will then output a 0 or a 1 for each request, telling if the book is available (line separated).

Machine

  • 2s on a 1GHz machine
  • 8000ko memory

Example IO

Input:

1
2
3
4
5
6
7
8
9
10
11
2 4
2
0 3
1 3
1
0 3
1
1 4
2
0 2
0 5

Output:

1
2
3
4
5
6
1
1
0
0
1
0

Solving it

First, we need to understand the form. It just asks us to accept or decline requests from clients, and keep track of whether or not books are available.

We then need a data structure for our books, since they’re indexed like an array, it seems obvious to use one. All we have left to do is to think about what data we need to store about the book. We could use the date it’s been last borrowed, and have some maths, but, when we think about it, we can just have them on a cooldown. A book can then be a single Int, 0 from the start, which will be set to a positive int when borrowed, representing the duration. Each day, it decreases by 1, and checking if it’s available is as simple as n <= 0.

Coding it

First, we need a way to get input, as we saw earlier, we only have to input ints, simple values, or double, separated by commas. Outputting will be quite simple as well.

1
2
3
4
5
6
7
8
9
10
11
12
single_input :: IO ->> Int
Empty => Int IO.raw_input ""

double_input :: IO ->> (Int, Int)
Empty ~> {
Empty => IO.raw_input "",
raw => String.split raw " ",
[a, b, ...c] => (Int a, Int b),
}
output_val :: Bool ->> IO
True => IO.log <- 1
False => IO.log <- 0

Now we need to manage books. We setup 3 interactions, borrowing (changing 1 value), updating the books every day, and checking if a book os available.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
borrow :: [Int], Int, Int ->> [Int]
books, idx, dur ~> do:
-- using do, to make this code more readable
new_books = Mut Copy Books
new_books[idx] = dur
return Const new_books

day_passing :: [Int] ->> [Int]
-- applying a subtraction to every element
books => books @\ (-1)

available :: [Int], Int ->> Maybe Bool
-- checking for bad indices
book, idx | idx < 0 => Nothing
book, idx | idx > length book => Nothing
-- returns whether or not the book is still borrowed
book, idx => book[idx] <= 0

Now, we just need to deal with the ugly loops, in a do block. Nothing that we haven’t setup yet, it’s just a matter of solving the exact form with its wierd inputs.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
do:
-- read inputs / loops
nbBooks, nbDays = double_input ()
books = fill [0..nbBooks] 0
for day in [0..nbDays]:
for client in [0..single_input ()]:
idx, dur = double_input ()
-- check for availability
avail = available books idx
-- print the result
IO.log <- output_val avail
-- borrow the book only if available
if avail:
borrow books idx dur
-- update books
books = day_passing books

Final Code

Dart Target

Form (translated):

Form

At a bar, you meet dart champions, who practise on square targets.

1
2
3
4
5
6
7
aaaaaaa
abbbbba
abcccba
abcdcba
abcccba
abbbbba
aaaaaaa

Given the side length n, print a similar target

Machine

  • 1s on a 1GHz machine
  • 8000ko memory

Example IO

Input:

1
5

Output:

1
2
3
4
5
6
7
8
9
aaaaaaaaa
abbbbbbba
abcccccba
abcdddcba
abcdedcba
abcdddcba
abcccccba
abbbbbbba
aaaaaaaaa

Solving it

This one kinda messed with my brain at first, but in the end, it wasn’t that hard.
First, we need a way of arranging letters, so that we can use them more simply. We’ll never need more than n letters. Then, we need a good way of associating each tile with a letter. I quickly thought of distance, but as you can see above, it’s not exactly it, as the diagonals aren’t further than the straight lines. I then figured it was the max of the horizontal & vertical distance.

Once we have that distance, which will be an integer, since we’re taking the max of two integers, we can associate each distance with a letter. Since the highest letter is distance 0, I reversed our original letter list, adnd simply took letters[dst] for every tile.

Coding it

First, setup the letter stuff.

1
2
3
4
5
6
7
8
9
10
-- don't import stuff in minimal code comps, it's cheating ;]
Letters = Static "abcdefghijklmnopqrstuvwxyz"

get_letter_count :: IO ->> Int
-- get a single int from the console
Empty => Int IO.raw_input ""

get_letters :: Int ->> String
-- take only count letters, then inverse the sequence
count => Letters[:count][::-1]

Then, a simple helper function, which finds the right side length, using the letter count. (every letter is represented twice, except the middle letter, which appears only once)

1
2
tiles_for_letters :: Int ->> Int
letters => 1 + 2 * (letters-1)

Next is the big fish, we need to get the letter at each index. I thought a 1-d representation would be convinient, so Ihad to compute the (x, y) each time. We can use all the concepts said before to create that big function, which predicts the right letter at any point.

1
2
3
letter_at_index :: Int, String, Int, Int ->> Int
tiles, letters, target, i => letters[Int max (abs x - target) (abs y - target)]
where y = i % tiles, x = i // tiles

Finally, we can think about displaying stuff !
Since the output format is a line per row, we can print them one at a time

1
2
display_line :: Int, [String], Int ->> IO
width, arr, x => IO.log <- " ".join arr[x*width : (x+1)*width]

Now, it’s just a matter of using the functions we defined, and applying that to the inputs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
do:
-- get input
lc = get_letter_count ()
letters = get_letters lc
tile_count = tiles_for_letters lc
target = lc-1

-- partially init our functions, with the input values that won't change
letter_at_index = letter_at_idx tile_count letters target
display = display_line tile_count

-- generate our 1d representation
arr = [0..tile_count**2] @\ letter_at_index
-- display the rows 1 by 1
for x in [0..tile_count]:
display arr x

Final Code

Measure Smoothing

Form (translated):

Form

You have recieved measures. Measure smoothing is the operation of setting each value in the sequence (not first nor last) to the average of the value before and after it.

You have to find how many smoothing operations are needed to get the maxmium difference between two measures below a certain threshold

Inputs are: number of measures, the threshold, then the measures

Machine

  • 2s on a 1GHz machine
  • 8000ko memory

Example IO

Input:

1
2
3
4
5
6
7
8
9
7
1.120
1.292
1.343
3.322
4.789
-0.782
7.313
4.212

Output:

1
13

Solving it

Well, this one was quite a no-brainer. All we have to figure out is a way to perform the smoothing, and a way to check if the difference is below that threshold.
All of those can be solved using simple loops, you’ll see what I mean later.
This problem is more of a coding problem than a thinking problem.

Coding it

First, actually get the list we’ll work with:

1
2
3
get_measures :: Num, IO ->> [Num]
x ~> do:
return [Num IO.raw_input "" for _ in [0..x]]

The, we can define a 1d distance function, and another to check if a difference is in bound of that threshold:

1
2
3
4
5
6
dist :: Num, Num ->> Num
x, y | x == y => 0
x, y => abs(x - y)

in_bounds :: Num, Num, Num ->> Num
x, y, b => dist x y < b

With that, we can create a check function, that recursively checks every element of the array. To save on computing time, I’ll eject out as soon as we get a single False. The function is initially called by check dmax arr Nothing, then starts its recursive business. If we reach the last element while checking, without even having ejected out with a False, we return True.

1
2
3
4
5
6
7
check :: Num, [Num], Maybe Int ->> Bool
dmax, arr, Nothing => _check 0
-- if we haven't ejected yet, return True
_, arr, idx | idx == length arr - 1 => True
-- if the values are in bound, continue checking, else eject with False
dmax, arr, idx => in_bounds arr[idx] arr[idx+1] dmax ? _check idx+1 : False
where _check = check dmax arr <0?>

Now, we just need a function to smooth the measures. I opted for the same recursive option. Apart from the first and last elements for which I return the value, I recursively go through the array and add my averages.

1
2
3
4
5
6
7
8
9
smooth_measures :: [Num], Maybe Int ->> [Num]
arr, Nothing => _smooth 0
-- start with the first element, then starts going through recursion
arr, x | x == 0 => [arr[0], ... _smooth 1]
-- at the end, finish with the last element
arr, x | x == length arr - 1 => arr[-1]
-- does the smoothing & recursion
arr, x => [(arr[x - 1] + arr[x + 1]) / 2, ... _smooth x + 1]
where _smooth = smooth arr <0?>

Finally, we can just have our loop and count the number of checks we need !

1
2
3
4
5
6
7
8
9
10
11
do:
nbMeasures = IO.raw_input ""
diffMax = IO.raw_input ""
measures = Mut get_measures nbMeasures

cnt = Mut 0
while not check diffMax measures 0:
measures = smooth_measures measures 0
++cnt

IO.log <- cnt

Final Code

Frogs

Form (translated):

Form

Frogs are on a race, they’re indexed from 1 to nbFrogs. Every round (from round 1 to nbRounds), a frog jumps forward n times. You need to keep track of the frog who’s been ahead for the longest time

The inputs are the number of frogs, then the number of rounds, then integer pairs for every round: the frog’s index, and the distance it goes forwards by

Machine

  • 1s on a 1GHz machine
  • 16000ko memory

Example IO

Input:

1
2
3
4
5
6
7
8
4
6
2 2
1 2
3 3
4 1
2 2
3 1

Output:

1
2

Solving it

Again, here, there isn’t a huge clever trick, we just need to get the data, and register what’s going on. Though, we can have a lot of fun with CF’s data types.

Coding it

I’m bringing back the code for a double input, no need to show it here again.

Then I talked about data types, we can use those to represent a frog, as we need an index (number), a current distance from the starting blocks, and the time it’s been ahead for.
We’ll also define a data type for a “Leader”, which’ll help quite a lot when sorting the frogs, as we don’t want ties.

1
2
data Frog = (Int nb, Int score, Int ahead)
data Leader = (Int idx, Int score, Bool tied)

Then, we need a basic way of having a list of frogs. From the number of frogs we want, we can generate a list of Mutable objects. Here, we map each index of a range to a new Frog object.

1
2
frog_list :: Int ->> [Mut Frog]
x => [0..x] @\ (n => Mut Frog(n, 0, 0))

Last helpers we need are ways to compare our values. We’ll setup 1 general use function, compare_two, that compares two elements, and returns a Leader object, with al the info we need. We can then compare our Frogs on a specific property with the foldl, or >\ operator to find the best of a list, and know what’s their score, if they’re tied, and their idx, which is all we need to complete the task.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
compare_two :: String, Frog, Leader ->> Leader
-- if both are tied
prop, f, l | f[prop] == l.score => Leader(l.nb, f[prop], True)
-- otherwise, if the frog's better than the current, create a new leader, else, keep the current one
prop, f, l => f[prop] > l.score ? Leader(f.nb, f[prop], False) : l

best_score :: [Frog] ->> Leader
with compare_two_scores
-- foldl to find the best
frogs >\> compare_two_scores "score" Leader(-1, -1, True)

best_lead :: [Frog] ->> Leader
with compare_two_scores
-- foldl to find the best
frogs >\> compare_two_scores "ahead" Leader(-1, -1, True)

Finally, in our do block, we can implement our loops & logic:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
do:
nbFrogs = IO.raw_input ""
frogs = frog_list nb

nbRounds = IO.raw_input ""

for _ in [0..nbRounds]:
leader = best_score frogs
if not leader.tied:
frogs[leader.idx - 1].ahead += 1

idx, dst = double_input ()
frogs[idx - 1].score += dst

IO.log <- (best_lead frogs).idx

Final Code

[MORE COMING SOON]