You are not logged in. Please login at www.codechef.com to post your questions!

×

SUBSTR - Editorial

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

This question is marked "community wiki".

asked 03 Nov '13, 13:49

gamabunta's gravatar image

1★gamabunta
2.4k128183169
accept rate: 14%

edited 13 Nov '13, 17:47

admin's gravatar image

0★admin ♦♦
19.8k350498541

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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