PROBLEM LINKSDIFFICULTYEasy PREREQUISITESAdHoc PROBLEMGiven an integer N, let S_{N} be the string formed by concatenating all the integers between 1 and N, inclusive. Thus, S_{20} = 1234567891011121314151617181920 Given an integer K, find the number of times K appears as a substring of N. EXPLANATIONThis 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 log_{10} K) will pass as well. The following pythoncode 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 COMMENTARYThe problem can be solved by generating the entire string S_{N} for each test case. To achieve faster times, once can precompute the string S_{1000000} and then store the lastindices, up to which the checks should be performed. The following Ccode 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 precomputes S_{1000000}. SETTER'S SOLUTIONCan be here TESTER'S SOLUTIONCan be here
This question is marked "community wiki".
asked 03 Nov '13, 13:49
