Battle Dev RegionsJob Novembre 2018 - Problème 6

Il y a quelques semaines, j’avais publié une solution de l’exercice 5 du BattleDev de novembre 2018.

C’est avec un peu de retard que je vous donne aujourd’hui une solution pour le problème 6 :)

L’énoncé du problème 6 est le suivant :

On dispose d’une fonction définie sur [0, N] à valeurs dans [0, N]. L’image d’un entier est un entier, et l’image d’un nombre décimal est obtenue par interpolation linéaire entre les deux entiers qui l’entourent.

Voici l’exemple d’une telle fonction :

func0

On pourra représenter chacune des fonctions de ce type par une liste [f(0), f(1), f(2), …, f(N)]. Ici, N=3 et la liste correspondant à la fonction est [1, 3, 0, 2].

On compose ensuite la fonction sur elle-même K fois (par exemple f(f(f(f(f(f(f(x))))))) ou fᴷ(x) si K=7) - il faut déterminer combien de fois cette fonction composée passe par N/2.

La fonction [1, 3, 0, 2] composée pour K=2 et K=3 sont données ici :

func1

func2

Les limites sur les entrées sont N<100 et K<1000.

Résolution du problème

Solution naïve

Il s’agirait ici de trouver simplement la liste d’antécédents de N/2 par f. Dans notre cas, cet ensemble serait [0.25, 1.5, 2.75] qui sont antécédents de 1.5.

On itère ensuite à nouveau pour trouver tous les antécédents de 0.25, 1.5 ou 2.75. Les solutions pour K=2 seraient donc 1.91666, 2.125 (antécédents de 0.25), 0.25, 1.5, 2.75 (antécédents de 1.25), 0.875 et 1.08333 (antécédents de 2.75), soit 7 antécédents de N/2 pour f(f(x)). Pour chacun de ces nombres que l’on notera i, on a f(i)=j de telle sorte que f(j)=N/2. Ces nombres représentent donc effectivement nos solutions pour K=2.

Il suffit d’itérer de la sorte K fois pour avoir la bonne réponse. Cependant, deux problèmes importants se posent à nous :

Premièrement, la précision des nombres flottants induit des petites erreurs qui s’amplifient au fur et à mesure des itérations. On peut déjà le constater sur les antécédents que j’ai calculés plus haut, 1.91666 et 1.08333, qui ont en réalité une infinité de chiffres après la virgule. Pour pallier à ce problème, on pourrait fonctionner en représentation fractionnelle.

Le deuxième souci, non des moindres, est le nombre de solutions : en effet, on peut prouver assez simplement que le nombre d’antécédents est susceptible de grandir exponentiellement au cours des itérations. Prenons par exemple la fonction simple [0, 2, 0], itérée avec K=1, K=2 et K=3:

func3

func4

func5

Le nombre d’antécédents de 1 double à chaque itération. En arrivant à K=1000, on aura donc 2^1000 antécédents dans notre liste, ce qui est impossible à stocker en mémoire et à calculer en temps raisonnable, à moins de disposer d’un supercalculateur quantique !

On doit donc se mettre en quête d’une solution plus optimale.

Solution en programmation dynamique

Contrairement au problème 5, la solution optimale est relativement simple à comprendre et à mettre en oeuvre, la principale difficulté étant de trouver la bonne méthode.

La position exacte des antécédents ne nous intéresse plus, nous souhaitons juste connaître leur nombre. Si l’on compte itérativement le nombre de fois que fᴷ parcourt chaque intervalle unitaire ([0,1], [1,2], [2,3], etc.), on pourra savoir le nombre d’antécédents de N/2 par fᴷ (en prenant le nombre de fois que l’intervalle comprenant N/2 est parcouru).

Par exemple, pour la fonction [1, 3, 0, 2], on parcourt successivement [1,2], [2,3], [3,2], [2,1], [1,0], [0,1], [1,2]. En cumulé, la fonction f passe donc par les intervalles suivants :

func0

  • [0,1] 2 fois
  • [1,2] 3 fois
  • [2,3] 2 fois

De la même manière, f² parcourt les intervalles suivants :

func1

  • [0,1] 5 fois
  • [1,2] 7 fois
  • [2,3] 5 fois

Et enfin le décompte pour f³ :

func2

  • [0,1] 12 fois
  • [1,2] 17 fois
  • [2,3] 12 fois

C’est bien joli de savoir que le nombre de fois qu’on parcourt chaque intervalle unitaire permet d’obtenir la solution, il faut maintenant être capable de le calculer !

Compter ces intervalles est très simple itérativement : on associe à chaque segment unitaire antécédent tous les segments images par f. Reprenons notre fonction préférée :

func0

Le mapping antécédent-images sera :

  • [0,1] -> [1,2] et [2,3]
  • [1,2] -> [0,1], [1,2] et [2,3]
  • [2,3] -> [0,1] et [1,2]

À l’étape 0, on commence avec un seul intervalle unitaire de chaque, qui correspond au fait que l’on étudie la fonction sur [0, N].

À l’étape 1, comme vu précédemment :

  • Le parcours de [0,1] engendre les images [1,2] et [2,3]
  • Le parcours de [1,2] engendre les images [0,1], [1,2] et [2,3]
  • Le parcours de [2,3] engendre les images [0,1] et [1,2]

On aura donc 2 images [0,1], 3 images [1,2] et 2 images [2,3].

Pour l’étape 2, nos antécédents sont les images obtenues à l’étape 1 :

  • Le parcours de [0,1] deux fois engendre deux fois [1,2] et deux fois [2,3]
  • Le parcours de [1,2] trois fois engendre les images [0,1], [1,2] et [2,3] trois fois chacune
  • Le parcours de [2,3] deux fois engendre deux fois [0,1] et deux fois [1,2]

En totalisant les images, on aura donc 5 images [0,1], 7 fois [1,2] et 5 fois [2,3]. On peut voir que ce sont bien les valeurs obtenues précédemment.

Formellement, ces calculs se représentent aussi sous forme matricielle. On commence avec le vecteur initial [1 1 1] qui correspond aux intervalles [0,1] [1,2] et [1,3]. Ensuite, la transition entre deux itérations est faite par la matrice antécédent-image, qui est la suivante dans notre cas :

[0 1 1]
[1 1 1]
[1 1 0]

Dans cette matrice, le coefficient i,j vaut 1 si l’intervalle f([i,i+1]) engendre [j, j+1], et 0 sinon.

À chaque étape, on multiplie le vecteur d’antécédents par la matrice de transition, et cela nous donne le vecteur d’antécédents de la prochaine étape. Après K itérations, on prendra simplement le K/2-ème coefficient du vecteur et cela nous donnera directement la réponse.

Pour mettre un peu de concret là dedans, voici le code qui implémente cette solution :

n = int(input())
f = list(map(int,input().split()))
k = int(input())

transition = []
for i in range(n):
    transition.append(list(range(min(f[i], f[i+1]),max(f[i], f[i+1]))))
    
vec = [1 for _ in range(n)]

for i in range(k):
    newvec = [0 for _ in range(n)]
    for coef in range(n):
        for nxt in transition[coef]:
            newvec[nxt] += vec[coef]
    vec = newvec

print(newvec[n//2]%1000)

C’est la fin de cet article, n’hésitez pas à me suivre sur Twitter pour être informé de mes nouvelles publications !

Written on December 10, 2018
Follow me on Twitter to be informed about new posts !