LebGeeks

A community for technology geeks in Lebanon.

You are not logged in.

#1 April 19 2014

m.sabra
Member

[Exercice] Alphabet Stickers

When we were kids, we used to play with some stickers where these stickers contain some (but not necessarily all) lower case English alphabet letters.

Each sticker contains some letters arranged in a single row, where all occurrences of the same letter are adjacent to each other. A sticker can be represented as a string of characters, for example the following are valid stickers’ representations: “aabcc”, “ccccab” and “mmaw”. And the following are not valid (because not all occurrences of the same letter are adjacent to each other): “abacc”, “cccabc” and “mawm”.

Now we found some stickers with some missing letters, but we are sure that all missing letters belong to the visible letters set (that is, for every missing letter, there is at least one visible letter that matches the missing one). In this problem a question mark letter represents a missing letter. Given some stickers’ representations with zero or more missing letters, your task is to count the number of possible original configurations for each sticker.

For example, this sticker “aa??bb” with missing letters could have been one of the following original stickers “aaaabb”, “aaabbb” or “aabbbb”. But it could not have been any of the following original stickers “aababb” (it is invalid sticker) and “aaccbb” (because the letter ‘c’ did not appear in the given configuration).

Input

Your program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1  T  100). Followed by the test cases, each test case is described in one line which contains a non-empty string which consists of up to 10,000 letters, each letter is either a lower case English letter (from ‘a’ to ‘z’) or a question mark (‘ ?’). This string represents a sticker configuration which contains zero or more question marks, it will also contain at least one letter which is not a question mark and there will be at least one valid original configuration for it.

Output

For each test case, print a single line which contains a single integer representing the number of possible original configurations for the sticker, since the result may be very large, print it modulo 1,000,000,007 (10^9 + 7).

-The problem was obtained from here: www.acmacpc.org/Homesite/acpc/acpc2013.pdf
-allowed languages are:C++ and Java (but it's not a competition now so feel free to use any language)
-no need to print with modulo if you are okay with big numbers.
i solved it in Java and will post the solution once others start to submit just to keep it challenging.
and if anybody have the time to make long test cases you're welcome to post them 
example:
??aaaaaaaaawwwwwwww???????????ddddcccc????????zzzzssss???ff???????g????lllooo?????sssss????kkk???kkk???
should give 518400 (if my program was correct).

Last edited by m.sabra (April 19 2014)

Offline

#2 April 20 2014

Ra8
Member

Re: [Exercice] Alphabet Stickers

I participated in this competition when it was held, this was one of the easiest problems given. Anyway this is my solution in PHP:

function doit($str){
    $pattern ="/(\?)+|[a-z]*/";
    $ans=array();
    preg_match_all($pattern, $str, $ans);
    $ans=$ans[0];
    $number=1;
    for($i=2;$i<count($ans);$i++){
        if($ans[$i]==""||$ans[$i][0]=="?")continue;
        if($ans[$i][0]==substr($ans[$i-2],-1))
            continue;
        $interogations=strlen($ans[$i-1]);
        $number=bcmod(bcmul($number,($interogations+1)),1000000007);
    }
    return $number;
}

You can access the judge's input/output here: http://acmacpc.org/Homesite/archive/201 … 3-IO-A.zip to check that it works for almost any input.

Last edited by Ra8 (April 20 2014)

Offline

#3 April 20 2014

m.sabra
Member

Re: [Exercice] Alphabet Stickers

import java.util.*;
public class prog {
	public static void main(String [] args){
		Scanner input = new Scanner(System.in);
		int TestCases = input.nextInt();
                calc sticker = new calc();
		String Case;
		long a=0;
		for (int i=0;i < TestCases;i++) {
			Case = input.next();
                        a=sticker.calculate(Case);
			System.out.println(+a);
			
		}
	}
}
class calc{
	long calculate (String test){
	int b=0;
	long c=1;
              for (int o=1;o <test.length();o++){
                   if (test.charAt(o) == '?'){
                   b=b+1;										
                   }
                   else{
                   if(o != ((test.length())) && test.charAt(o) != '?' && test.charAt(o-(b+1)) != '?' && test.charAt(o) != test.charAt(o-(b+1))){
                       c=c*(b+1);
                    }
                b=0;
                   }
               }
	return c;
	}
}

Java

Offline

#4 September 26 2014

raja
Member

Re: [Exercice] Alphabet Stickers

Wasn't at that competition(last one I participated in was 2010, I think). That's a pretty easy one by their standards(there's usually one of these in every competition that everyone solves).

Anyway, python code:

def num_possibilities(s):
    last_letter = None
    num_marks = 0
    sol = 1
    for c in s:
        if c == "?":
            num_marks += 1
        elif num_marks == 0 or last_letter is None or last_letter == c:
            last_letter = c
            num_marks = 0
        else:
            sol *= (num_marks+1)
            last_letter = c
            num_marks = 0
    return sol

if __name__ == "__main__":
    n = int(raw_input())
    for i in range(n):
        print num_possibilities(raw_input().strip()) % (10**9+7)

Running it:

$ python stickers.py < ~/Downloads/acpc2013-IO-A/sticker.in > /tmp/sticker.out
$ diff -u /tmp/sticker.out ~/Downloads/acpc2013-IO-A/sticker.out
$

Got the I/O correct on the first try, just wrote it out and it worked. So yeah, easy one

Last edited by raja (September 26 2014)

Offline

Board footer