Computational Wizards and Compression of Strings
All submissions for this problem are available.
The magical kingdom of Qwan has wizards who work on Computational Magic Theory which involves study of magic spells as functions and magic invocations as function calls. They found a new magic spell that is a subroutine for a spell that stores everyday object in very small space. Given a string, the spell encodes it into binary bit stream such that each character in string has a unique binary representation. The encoding is such that the binary bit stream is the shortest possible and unambiguous. For example, “abaaabbbb” is encoded as “010001111” and the length of this bit stream is 9. They have a problem studying this phenomenon in detail. Sometimes they extract bit streams that are part of some other magic in vicinity (and hence do not represent the encoding described). This problem can be solved by using a computer to filter out wrong results but there’s a catch. Though the wizards are good at Magic Computations, they are not very familiar with normal human computers. Model this encoding and given a string and a bitstream help the wizards find whether the bit stream is an encoded version of the string.
First line contains a number T denoting the number of test cases. Each test case conists of U and C which denotes the uncompressed string and compressed bit stream respectively, given in two seperate lines.
For each test case output "yes" if the bit stream C is the most compressed bit-stream of string U, else output "no"(without quotes).
- 1 ≤ T ≤ 100
- 1 ≤ |S| ≤ 1000
- 1 ≤ |U| ≤ 10000
Input: 2 abc 1011 aacd 001011 Output: no yes
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS|
Fetching successful submissions