0
\$\begingroup\$

ABOUT

  1. For each subsequence, look at its position in the original decimal representation of \$x\$. Let's say that the most significant digit it contained was the \$e\$-th digit, where \$e=0\$ corresponds to the least significant digit of \$x\$. For example, \$388, 822, 442\$ can be split into subsequences "3", "888", "22", "44", "2", where \$e=7\$ for the sequence "888" and \$e=4\$ for the sequence "22".

  2. The value of a subsequence which contains a digit \$d\$ repeated one or more times is \$d \cdot 10^e\$.

    1. \$f(x)\$ is the sum of values of these subsequences. For example, \$f(388, 822, 442) = 3 \cdot 10^8 + 8 \cdot 10^7 + 2 \cdot 10^4 + 4 > \cdot 10^2 + 2 \cdot 10^0\$.

    2. Since this number could be very large, compute it modulo \$109+7\$.

INPUT

  1. The first line of the input contains a single integer denoting the number of cases

  2. The first line of each test case contains two space-separated integers

  3. The second line contains two space-separated integers \$N > 10^{18}\$

from itertools import groupby
def encode(num):
    out , num = [] , list(map(int , str(num)))
    for v, g in groupby( enumerate(num), lambda k: k[1] ):
        l = [*g]
        for i in l:
            out.append((abs(l[0][0]- len(num) + 1)))
    s , value = 0 , False
    for i in range(len(num)): 
        if value == num[i]: pass
        else:
            s += num[i]*10**out[i]
            value = num[i]
    return s

for i in range(int(input())):
    start = list(map( int , input().split()))
    end , output = list(map( int , input().split())) , 0
    for num in range(start[1] , end[1]+1):
        output += encode(num)
    print(output)
\$\endgroup\$
  • 2
    \$\begingroup\$ Is this codechef.com/AUG19B/problems/ENCODING ? \$\endgroup\$ – Martin R Aug 2 at 19:51
  • \$\begingroup\$ kinda but stuck TLE \$\endgroup\$ – code_guest Aug 2 at 19:51
  • \$\begingroup\$ This challenge is using the term "subsequence" in an unconventional way. I'd call them substrings. \$\endgroup\$ – 200_success Aug 2 at 20:18
  • \$\begingroup\$ @200_success i worked on your "substrings" concept and my time dropped about 12 sec but still TLE \$\endgroup\$ – code_guest Aug 5 at 20:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.