×

Easy

# PROBLEM

Given an integer N, let SN be the string formed by concatenating all the integers between 1 and N, inclusive.

Thus, S20 = 1234567891011121314151617181920

Given an integer K, find the number of times K appears as a substring of N.

# EXPLANATION

This problem was intended to be trivial. A lot of doubts were raised about how many test cases were crunched into a file, but all such questions were intentionally left unanswered.

See, the real limit on T was defined in the problem statement, cheekily, as a limit on sum of N across all test cases in a file. This limit was 1,000,000. An algorithm of the order of O(N) will not take more than O(sum(N)) for a test file. In fact, solutions with complexity O(N log10 K) will pass as well.

The following python-code will solve the problem. (C like code snippets are in the next section)

import re
T = int(raw_input())
for _ in xrange(T):
N, K = raw_input().split()
S = "".join(map(str,range(1,int(N)+1)))
R = [m.start() for m in re.finditer('(?='+K+')', S)]
print len(R)


If only ICPC rules allowed languages besides C/C++ and JAVA!

# CODE COMMENTARY

The problem can be solved by generating the entire string SN for each test case. To achieve faster times, once can pre-compute the string S1000000 and then store the last-indices, up to which the checks should be performed.

The following C-code is enough to solve the problem. It is almost equivalent to the python code above.

char A[10000000];
int main() {
char K[10], nk;
int T, N, t = 0, result = 0;
scanf("%d",&T);
while(T--) {
scanf("%d %s",&N,K);
nk = strlen(K);
t = 0; for(int i=1;i<=N;i++) t += sprintf(A+t, "%d", i);
result = 0; for(int i=0;i<t;i++) result += !strncmp(K,A+i,nk);
printf("%d\n",result);
}
}


Check the tester's solution for an approach that pre-computes S1000000.

Can be here

# TESTER'S SOLUTION

Can be here

This question is marked "community wiki".

2.4k128183169
accept rate: 14%

19.8k350498541

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×3,820
×968
×643
×12

question asked: 03 Nov '13, 13:49

question was seen: 3,987 times

last updated: 13 Nov '13, 17:47