Can you do it better

Problem code: CYDB

All submissions for this problem are available.

Your task is to write a program which computes exactly the same result as Chef's programs below. He was kind enough to provide you with the same program written in three different programming languages. However, your solution should be much faster.

C++

#include <iostream>
#include <string>
using namespace std;

int main() {
	string a, b, c;
	int na, nb, r;
	cin >> a;
	na = a.size();
	cin >> b;
	nb = b.size();
	cin >> c;
	r = 0;
	for (int i = 0; i < nb; i++) {
		for (int j = 1; j < min(na+1, nb-i+1); j++) {
			bool f = true;
			int d = 0;
			for (int k = 0; k < j; k++) {
				if (a[k] != b[i+k]) { 
					if (c[k] == '1')  { d += 1; }
					else { f = false; }
				}
			}
			if (f && d <= 2) { r = (r + j*j) % 1000000007; }
		}
	}
	cout << r << endl;
	return 0;
}

 

Java

import java.util.Scanner;

public class Main {

	static String a, b, c;
	static int na, nb, r;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		a = sc.next();
		na = a.length();
		b = sc.next();
		nb = b.length();
		c = sc.next();
		r = 0;
		for (int i = 0; i < nb; i++) {
			for (int j = 1; j < Math.min(na+1, nb-i+1); j++) {
				boolean f = true;
				int d = 0;
				for (int k = 0; k < j; k++) {
					if (a.charAt(k) != b.charAt(i+k)) { 
						if (c.charAt(k) == '1') { d += 1; }
						else { f = false; }
					}
				}
				if (f && d <= 2) { r = (r + j*j) % 1000000007; }
			}
		}
		System.out.println(r);
	}
}

 

Python

a = raw_input()
na = len(a)
b = raw_input()
nb = len(b)
c = raw_input()
r = 0
for i in range(nb):
	for j in range(1, min(na+1, nb-i+1)):
		f = True
		d = 0
		for k in range(j):
			if (a[k] != b[i+k]):
				if (c[k] == '1'): d +=1
				else: f = False
		if (f and d <= 2): r = (r + j*j) % 1000000007
print r

 

Input

The strings A, B and C are provided in a compressed form to keep the input small enough. Sequence 00000 is encoded with letter 'a', 00001 with 'b' and so on until 'z'. 11010 is represented by 'A' and 11111 by 'F'.

The input consists of three lines of letters a-z, A-F. First line contains at most 200 characters and the second one at most 2 000 000. Third line has the same length as the first line and will contain at most 40 digits 1 when decompressed.

Example

Input:
aBFn
ygFBg
bbdb

Output:
2990

Explanation

After decompression we get strings 00000110111111101101, 1100000110111111101100110 and 00001000010001100001. If we run chef's program with this decompressed input, we will get 2990 as a result.

Author: thocevar
Date Added: 4-12-2011
Time Limit: 3 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

Given C++ program is giving

manoharsingh23 @ 1 Feb 2012 10:52 PM
Given C++ program is giving output 0 for above input sample not 2990 ....

@manoharsingh23: You have to

tomaz_adm @ 2 Feb 2012 12:40 AM
@manoharsingh23: You have to run it with a decompressed input (three strings of ones and zeros from the explanation section). There were however a couple of irrelevant typos which should be fixed anytime now.

The test data for this

admin @ 2 Feb 2012 12:42 AM

The test data for this problem has been updated the submissions have been rejudged. Regret the inconvinience caused.

@admin what's the time-limit?

phaniram @ 2 Feb 2012 11:44 PM
@admin what's the time-limit? mine getting timed-out

@phaniram: It should be clear

tomaz_adm @ 3 Feb 2012 12:37 AM
@phaniram: It should be clear that the time limit is 3 seconds. Provided solutions are way too slow, you need to find a faster method.

"Third line has the same

kchinger @ 3 Feb 2012 07:53 AM
"Third line has the same length as the first line and will contain at most 40 digits 1 when decompressed" I'm not understanding this line. 40 digits 1? Is this something I'm just unfamiliar with?

@kchinger: After

anton_adm @ 3 Feb 2012 08:18 AM
@kchinger: After decompression 'C' will contains only zeros and ones. This sentence means that there are no more 40 ones in 'C'.

Should I decompress the

v__b @ 3 Feb 2012 06:27 PM
Should I decompress the string in my submitting program? Or the input is decompressed?

shud i provide compressed or

daryllopes89 @ 3 Feb 2012 06:44 PM
shud i provide compressed or decompressed input for my program

The inputs are compressed

tomaz_adm @ 3 Feb 2012 07:44 PM
The inputs are compressed strings as demonstrated in the Example section.

The C++ program can cause

yeputons @ 4 Feb 2012 09:39 PM
The C++ program can cause integer overflow in the following line if (f && d <= 2) { r = (r + j*j) % 1000000007; } As I understand (because of Python program), it's a bug, isn't it?

All three implementations

tomaz_adm @ 4 Feb 2012 09:58 PM
All three implementations will give the same results under the given input constraints.

@tomaz_adm, I'm sorry, you're

yeputons @ 5 Feb 2012 08:11 PM
@tomaz_adm, I'm sorry, you're right.

@admin: my program is running

tinku @ 9 Feb 2012 07:59 AM
@admin: my program is running exactly for 1.44 seconds and then showing Time-Limit-exceeded. How come this is possible when given limit is 3sec. Can u check out the problem once,...

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions