SUBSTR - Editorial

editorial
, , , ,
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

Easy

PREREQUISITES

Ad-Hoc

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.

SETTER’S SOLUTION

Can be here

TESTER’S SOLUTION

Can be here

6 Likes