I just solved this coding challenge, but I don't understand why my solution works 🤔

#discuss #help #python #math

I've been trying to do one programming challenge a day on Kattis, and I just solved this one. I really had no idea how to solve it at first, so I just played around with the sample input/output data provided and noticed a pattern:

In the final sample, an input of 10 and 10 gives an output of 91: that's 10 * (10-1) + 1). Taking the first input to be x and the second to be y, this gives a formula of x * (y-1) + 1 which gives the correct output for all the other inputs and passes all test cases:

# https://open.kattis.com/problems/faktor
import sys


def faktor(articles, impact):
    print(int(articles)*(int(impact)-1) + 1)


if __name__ == '__main__':
    a, i = sys.stdin.readline().split()
    faktor(a, i)

The thing is, that formula doesn't seem to have anything to do with the question in the challenge. Maybe I'm missing something 🤔

Top comments (3)

Ganesh Prasad • Sep 3 '19 • Edited

Actually, your formula is correct. Let's derive it mathematically.

The number of articles you want to publish is A, and the impact you want is I. It's given that impact(I) = total_citations(C) / total_articles(A). It's also given that rounding is done only upwards. For example if your impact value is 23.0000001, then it will be rounded up as 24. (That's same as saying rounding is done using math.ceil).

We want to find the minimum number of citations C_min so that our rounded value of impact equals to I. We know that I = math.ceil( C / A ), therefore, the value of (C / A) must be something between I-1 and I. That is, I-1 < (C/A) <= I. From this, we can write, (I-1)*A < C <= I*A.
Now we know that value of C should be strictly higher than (I-1)*A and it should be less than or equal to I*A. C is an integer, therefore the minimum value of C that satisfies the above condition must be (I-1)*A + 1.