THICC '17 P4 - Kenta's Neural Networks

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 0.6s
Python 4.5s
Memory limit: 256M

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Kenta has a lot of neural networks which are trained to output a specific string. He has a copious amount of neural networks, as he is very good at building neural networks and loves them very much. Unfortunately, he has so many that he needs help finding out which of his neural networks is the best!

Each output for the neural network has a value that represents how accurate his neural network is. The accuracy value represents how many changes the neural network needs to make to the string to get the correct string. A change can be adding a character, removing one or editing one. The smaller the accuracy value, the better the neural network.

For example, to go from "horse" to "hose" you'd need one change, and from "almond" to "nut" you'd need six. You always want to use the minimum number of changes.

You'll be given the correct string which all neural networks wish to achieve, n number of neural networks, each accompanied by t different outputs from that same neural network. You'll need to output the results of the best (most accurate) neural network.

Input Specification

The first line will contain the correct string containing only lowercase letters.

The second line will contain n, the number of neural networks.

The following n lines will start with t, followed by t space separated strings, which are the neural networks' outputs.

Output Specification

A real number, the average accuracy value of the best neural network. An absolute or relative error of up to 10^{-6} will be accepted.

Constraints

Subtask 1 [20%]:

1 \le n, t \le 10

1 \le Length of any String \le 10

Subtask 2 [30%]:

1 \le n, t \le 50

1 \le Length of any String \le 50

Subtask 3[50%]:

1 \le n, t \le 100

1 \le Length of any String \le 100

Sample Input

memes
3
2 memes meemes
2 memes same
3 netuhiuoeou eunhouenht oentonhtet

Sample Output

0.5

Explanation

The first neural network has one perfect output. meemes needs the e removed to make memes. (0 + 1) / 2 = 0.5.

The second neural network has a perfect output, and same, which would take 3 moves to turn into memes.

The third is a very bad neural network and need not be considered.


Comments


  • 0
    0xc3  commented on Sept. 24, 2017, 11:42 a.m. edited

    Increase Time Limit?

    My correct solution TLEs 90% of the time, but sometimes it makes it through. At least I'm pretty sure it's correct because I've looked through everyone else's solutions and they all match.......

    EDIT: Today I learned C++14 is like 2x faster than C++11.....


    • 1
      Tearful  commented on Sept. 24, 2017, 12:41 p.m.

      lmao.