1 2 3 .
      x|
    x  |
  x   x|
x   x  |
  x   x|
    x  |
      x|

1 2 3 .
      x|
    x  |
  1   x|
1   x  |
  1   x|
    x  |
      x|

1 2 3 .
      x|
    1  |
  1   x|
1   2  |
  1   x|
    1  |
      x|

1 2 3 .
      1|
    1  |
  1   3|
1   2  |
  1   3|
    1  |
      1|

So you've registered. We sent you a welcoming email, to welcome you to code jam. But it's possible that you still don't feel welcomed to code jam. That's why we decided to name a problem "welcome to code jam." After solving this problem, we hope that you'll feel very welcome. Very welcome, that is, to code jam.

If you read the previous paragraph, you're probably wondering why it's there. But if you read it very carefully, you might notice that we have written the words "welcome to code jam" several times: 400263727 times in total. After all, it's easy to look through the paragraph and find a 'w'; then find an 'e' later in the paragraph; then find an 'l' after that, and so on. Your task is to write a program that can take any text and print out how many times that text contains the phrase "welcome to code jam".

To be more precise, given a text string, you are to determine how many times the string "welcome to code jam" appears as a sub-sequence of that string. In other words, find a sequence s of increasing indices into the input string such that the concatenation of input[s[0]], input[s[1]], ..., input[s[18]] is the string "welcome to code jam".

The result of your calculation might be huge, so for convenience we would only like you to find the last 4 digits.

    w e l c o m i n g _ e m a i l _ t o _ w e l c o m e _ y o u _ t o _ c o d e _ j a m

w   +-------------------------------------+
e     +-----------------+-------------------+
l       +-----------------------+-------------+
c         +-------------------------------------+
o           +-------------------------+-----------+
m             +-----------+-------------------------+
e                       +-------------------+---------+
_                                 +-----+---------------+-------+
t                                   +-----------------------------+
o                                     +-----------+---------+-------+
_                                       +---------------+-------+-----+
c                                               +-----------------------+
o                                                 +---------+-------+-----+
d                                                                           +
e                                                                             +
_                                                                               +
j                                                                                 +
a                                                                                   +
m                                                                                     +

    w e l c o m i n g _ e m a i l _ t o _ w e l c o m e _ y o u _ t o _ c o d e _ j a m

w   1-------------------------------------1
e     1-----------------1-------------------2
l       1-----------------------2-------------4
c         1-------------------------------------7
o           1-------------------------1-----------8
m             1-----------1-------------------------10
e                       1-------------------2---------12
_                                 1-----1---------------15------15
t                                   1-----------------------------32
o                                     1-----------1---------1-------33
_                                       1---------------2-------3-----36
c                                               1-----------------------42
o                                                 1---------1-------1-----43
d                                                                           46
e                                                                             46
_                                                                               46
j                                                                                 46
a                                                                                   46
m                                                                                     46

#include "stdio.h"
#include "stdlib.h"
#include "string.h"

//This should leak memory
int main() {
    
    char* hiworld = (char*)malloc(15);
    memcpy(hiworld, "Hello, world!\n", 15);
    printf(hiworld);
    
    return 1;
}

gcc -g vhelloworld.c -o helloworld

valgrind --leak-check=yes ./helloworld

==10877== Memcheck, a memory error detector.
==10877== Copyright (C) 2002-2007, and GNU GPL'd, by Julian Seward et al.
==10877== Using LibVEX rev 1804, a library for dynamic binary translation.
==10877== Copyright (C) 2004-2007, and GNU GPL'd, by OpenWorks LLP.
==10877== Using valgrind-3.3.0-Debian, a dynamic binary instrumentation framework.
==10877== Copyright (C) 2000-2007, and GNU GPL'd, by Julian Seward et al.
==10877== For more details, rerun with: -v
==10877== 
Hello, world!
==10877== 
==10877== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 11 from 1)
==10877== malloc/free: in use at exit: 15 bytes in 1 blocks.
==10877== malloc/free: 1 allocs, 0 frees, 15 bytes allocated.
==10877== For counts of detected errors, rerun with: -v
==10877== searching for pointers to 1 not-freed blocks.
==10877== checked 60,348 bytes.
==10877== 
==10877== 15 bytes in 1 blocks are definitely lost in loss record 1 of 1
==10877==    at 0x4022AB8: malloc (vg_replace_malloc.c:207)
==10877==    by 0x80483F0: main (vhelloworld.c:8)
==10877== 
==10877== LEAK SUMMARY:
==10877==    definitely lost: 15 bytes in 1 blocks.
==10877==      possibly lost: 0 bytes in 0 blocks.
==10877==    still reachable: 0 bytes in 0 blocks.
==10877==         suppressed: 0 bytes in 0 blocks.

char* hiworld = (char*)malloc(15);

#include "stdio.h"
#include "stdlib.h"
#include "string.h"

//This cleans up after itself
int main() {
    
    char* hiworld = (char*)malloc(15);
    memcpy(hiworld, "Hello, world!\n", 15);
    printf(hiworld);
    free(hiworld);
    
    return 1;
}

==10966== Memcheck, a memory error detector.
==10966== Copyright (C) 2002-2007, and GNU GPL'd, by Julian Seward et al.
==10966== Using LibVEX rev 1804, a library for dynamic binary translation.
==10966== Copyright (C) 2004-2007, and GNU GPL'd, by OpenWorks LLP.
==10966== Using valgrind-3.3.0-Debian, a dynamic binary instrumentation framework.
==10966== Copyright (C) 2000-2007, and GNU GPL'd, by Julian Seward et al.
==10966== For more details, rerun with: -v
==10966== 
Hello, world!
==10966== 
==10966== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 11 from 1)
==10966== malloc/free: in use at exit: 0 bytes in 0 blocks.
==10966== malloc/free: 1 allocs, 1 frees, 15 bytes allocated.
==10966== For counts of detected errors, rerun with: -v
==10966== All heap blocks were freed -- no leaks are possible.

def compile_js(st)
  return "".join( [ x.strip() for x in st.split("\n") if x.strip()[0:2]!="//" ] )

Energy Density, Gasoline

Energy Density, Hay

Energy Density, Sugar

Thus

And this is the other thing about the size of the cognitive surplus we're talking about. It's so large that even a small change could have huge ramifications. Let's say that everything stays 99 percent the same, that people watch 99 percent as much television as they used to, but 1 percent of that is carved out for producing and for sharing. The Internet-connected population watches roughly a trillion hours of TV a year. That's about five times the size of the annual U.S. consumption. One per cent of that is 10,000 Wikipedia projects per year worth of participation.


I think that's going to be a big deal. Don't you?


Well, the TV producer did not think this was going to be a big deal; she was not digging this line of thought. And her final question to me was essentially, "Isn't this all just a fad?" You know, sort of the flagpole-sitting of the early early 21st century? It's fun to go out and produce and share a little bit, but then people are going to eventually realize, "This isn't as good as doing what I was doing before," and settle down. And I made a spirited argument that no, this wasn't the case, that this was in fact a big one-time shift, more analogous to the industrial revolution than to flagpole-sitting.


I was arguing that this isn't the sort of thing society grows out of. It's the sort of thing that society grows into. But I'm not sure she believed me, in part because she didn't want to believe me, but also in part because I didn't have the right story yet. And now I do.

I was having dinner with a group of friends about a month ago, and one of them was talking about sitting with his four-year-old daughter watching a DVD. And in the middle of the movie, apropos nothing, she jumps up off the couch and runs around behind the screen. That seems like a cute moment. Maybe she's going back there to see if Dora is really back there or whatever. But that wasn't what she was doing. She started rooting around in the cables. And her dad said, "What you doing?" And she stuck her head out from behind the screen and said, "Looking for the mouse."


Here's something four-year-olds know: A screen that ships without a mouse ships broken. Here's something four-year-olds know: Media that's targeted at you but doesn't include you may not be worth sitting still for. Those are things that make me believe that this is a one-way change. Because four year olds, the people who are soaking most deeply in the current environment, who won't have to go through the trauma that I have to go through of trying to unlearn a childhood spent watching Gilligan's Island, they just assume that media includes consuming, producing and sharing.