Both the recursive and the power solutions run in quadratic
space in worst case (where x is 0 1 and y is 0 1 0 1 0 1 ...).
A method that could run in space proportional to x *&# y :
find, for each server and each position in the query-list, how
many messages could be handled starting at that point in the
list on that server; take the maximum of those to get the largest
run possible at each point; now that looks like the chained-records
problem where each item is the length of the record, so add the
putative record position to the length and extract the 'records',
which are the starting positions of each sequence; count them.
0 >. _2 + [: # 0 {~^:a:~ [: (+ [EMAIL PROTECTED]) 0 ,~ [: >./ (* >:)/\.@:~:"0 1
(I think (* >:)/\. could be coded to run faster.)
Henry Rich
> -----Original Message-----
> From: [EMAIL PROTECTED]
> [mailto:[EMAIL PROTECTED] On Behalf Of R.E. Boss
> Sent: Monday, July 28, 2008 12:03 AM
> To: 'Programming forum'
> Subject: RE: [Jprogramming] Saving the Universe
>
> Same algorithm; 2 boxes per case, servers in first box,
> queries in second.
>
> swtch=: 4 : 0
> c=. >./ y i. x
> (}:c}.y), ({:y)+c<#y
> )
>
> ([EMAIL PROTECTED] [ swtch^:_ ],[EMAIL PROTECTED])&>/"1
>
>
> Most of my time I spent in formatting the output.
>
>
> R.E. Boss
>
>
> > -----Oorspronkelijk bericht-----
> > Van: [EMAIL PROTECTED] [mailto:programming-
> > [EMAIL PROTECTED] Namens Henry Rich
> > Verzonden: maandag 28 juli 2008 1:47
> > Aan: 'Programming forum'
> > Onderwerp: RE: [Jprogramming] Saving the Universe
> >
> > This was my solution (after reading in the testcases):
> >
> > NB. Run one case. servers in first box, queries in second
> > docase =: 3 : 0
> > NB. Convert queries to machine #s. For each machine, find the
> > NB. first match; pick machine with the last first-match. Discard
> > NB. as many as the last first-match.
> > q =. i.&>/ y
> > switches =. 0
> > while. 1 do.
> > if. 0 = #q =. (i.#>{.y) (>./@(i.~) }. ]) q do. break. end.
> > switches =. >: switches
> > end.
> > switches
> > )
> >
> >
> > If it weren't a timed event, for fun I would have tried
> something like
> >
> > 0 >. <: 0: ` (>:@$:@(>./@(i.&(i.#>{.y)) }. ])) @.([EMAIL PROTECTED]) i.&>/
> > y
> >
> >
> > Henry Rich
> >
> >
> > > -----Original Message-----
> > > From: [EMAIL PROTECTED]
> > > [mailto:[EMAIL PROTECTED] On Behalf Of June Kim
> > > Sent: Sunday, July 27, 2008 6:54 PM
> > > To: Programming forum
> > > Subject: [Jprogramming] Saving the Universe
> > >
> > > Following is a problem from google code jam 2008, which is an
> > > interesting contest in the regard that the contest allows any
> > > programming languages.
> > >
> > > http://code.google.com/codejam/contest/dashboard?c=agdjb2RlamF
> > > tcg8LEghjb250ZXN0cxjqOQw
> > >
> > > I have a J solution for the problem but am eager to learn
> from your
> > > solutions. I will post my solution here in a couple of days.
> > >
> > > ----
> > > Problem
> > >
> > > The urban legend goes that if you go to the Google
> homepage and search
> > > for "Google", the universe will implode. We have a secret
> to share...
> > > It is true! Please don't try it, or tell anyone. All
> right, maybe not.
> > > We are just kidding.
> > >
> > > The same is not true for a universe far far away. In that
> universe, if
> > > you search on any search engine for that search engine's name, the
> > > universe does implode!
> > >
> > > To combat this, people came up with an interesting solution. All
> > > queries are pooled together. They are passed to a central
> system that
> > > decides which query goes to which search engine. The
> central system
> > > sends a series of queries to one search engine, and can switch to
> > > another at any time. Queries must be processed in the
> order they're
> > > received. The central system must never send a query to a search
> > > engine whose name matches the query. In order to reduce costs, the
> > > number of switches should be minimized.
> > >
> > > Your task is to tell us how many times the central system
> will have to
> > > switch between search engines, assuming that we program
> it optimally.
> > >
> > > Input
> > >
> > > The first line of the input file contains the number of
> cases, N. N
> > > test cases follow.
> > >
> > > Each case starts with the number S -- the number of
> search engines.
> > > The next S lines each contain the name of a search
> engine. Each search
> > > engine name is no more than one hundred characters long
> and contains
> > > only uppercase letters, lowercase letters, spaces, and
> numbers. There
> > > will not be two search engines with the same name.
> > >
> > > The following line contains a number Q -- the number of incoming
> > > queries. The next Q lines will each contain a query. Each
> query will
> > > be the name of a search engine in the case.
> > >
> > > Output
> > >
> > > For each input case, you should output:
> > >
> > > Case #X: Ywhere X is the number of the test case and Y is
> the number
> > > of search engine switches. Do not count the initial
> choice of a search
> > > engine as a switch.
> > >
> > > Limits
> > >
> > > 0 < N ? 20
> > >
> > > Small dataset
> > >
> > > 2 ? S ? 10
> > >
> > > 0 ? Q ? 100
> > >
> > > Large dataset
> > >
> > > 2 ? S ? 100
> > >
> > > 0 ? Q ? 1000
> > >
> > >
> > >
> > > Sample
> > >
> > >
> > > Input
> > >
> > > 2
> > > 5
> > > Yeehaw
> > > NSM
> > > Dont Ask
> > > B9
> > > Googol
> > > 10
> > > Yeehaw
> > > Yeehaw
> > > Googol
> > > B9
> > > Googol
> > > NSM
> > > B9
> > > NSM
> > > Dont Ask
> > > Googol
> > > 5
> > > Yeehaw
> > > NSM
> > > Dont Ask
> > > B9
> > > Googol
> > > 7
> > > Googol
> > > Dont Ask
> > > NSM
> > > NSM
> > > Yeehaw
> > > Yeehaw
> > > Googol
> > >
> > >
> > > Output
> > >
> > > Case #1: 1
> > > Case #2: 0
> > >
> > >
> > >
> > > In the first case, one possible solution is to start by using Dont
> > > Ask, and switch to NSM after query number 8.
> > > For the second case, you can use B9, and not need to make any
> > > switches.
> > >
> >
> >
> ----------------------------------------------------------------------
> > For information about J forums see
> http://www.jsoftware.com/forums.htm
>
> ----------------------------------------------------------------------
> For information about J forums see
> http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
