Thanks. Today I solved this problem using KMP.

Turns out the speed of my ACC program is pretty good (runtime: 0.030 seconds).

So this problem will be good illustration of KMP too.

## Search found 374 matches

- Mon Jan 19, 2009 7:15 pm
- Forum: Algorithms
- Topic: KMP Algorithm - Search for Problems
- Replies:
**8** - Views:
**6999**

- Sun Jan 18, 2009 5:24 pm
- Forum: Volume 1 (100-199)
- Topic: 103 - Stacking Boxes
- Replies:
**200** - Views:
**19515**

### Re: 103 WA

This is in case somebody needs test data. Here is the correct output for the input posted above by Leeon. I hope the input posted by Leeon is not the real Test Input used by the Online Judge. In that case this posting would be a complete spoiler and should be deleted. INPUT 1 1 1 5 2 3 7 8 10 5 2 9 ...

- Sun Jan 18, 2009 1:50 pm
- Forum: Algorithms
- Topic: KMP Algorithm - Search for Problems
- Replies:
**8** - Views:
**6999**

### Re: KMP Algorithm - Search for Problems

Thank you both for your replies. And yes, I looked into problem 10298 and was really able to solve it using KMP. Thanks a lot, mf , this problem is exactly the kind of problem I was looking for. That's because: (1) it is perfect for my goals of showing some typical application of the KMP algorithm (...

- Sun Jan 18, 2009 1:56 am
- Forum: Algorithms
- Topic: KMP Algorithm - Search for Problems
- Replies:
**8** - Views:
**6999**

### KMP Algorithm - Search for Problems

Hello, Are there some problems in UVA which can be solved by KMP (Knuth-Morris-Pratt) and thus used as an illustration of the KMP algorithm? I need to give a couple of lessons and I want to find a couple of problems which are good illustration of some of the Exact String Search Algorithms. I mean no...

- Fri Jan 16, 2009 11:58 pm
- Forum: Volume 115 (11500-11599)
- Topic: 11512 - GATTACA
- Replies:
**23** - Views:
**9318**

### Re: 11512 - GATTACA

I solved this one using two separate programs which implement different algorithms. Program #1 uses Trie-like structure - some simpler version of Suffix Tree but I believe I have some performance flaw in this one (language C with some simple C++ features, no STL usage) Runs (Accepted) in about : 4.9...

- Tue Aug 26, 2008 7:20 pm
- Forum: Volume 102 (10200-10299)
- Topic: 10212 - The Last Non-zero Digit.
- Replies:
**63** - Views:
**30785**

### Re: 10212 - The Last Non Zero Digit

To iggy: I also don't know how some people solved this one in less than 0.010 secs but (if they used a fair algorithm) I guess they tried to generate the numbers instead of iterating through them. What do I mean? Well... My algorithm runs in 3.710 secs and is implemented in C++. Some small hints abo...

- Wed Jul 23, 2008 10:59 pm
- Forum: Volume 3 (300-399)
- Topic: 338 - Long Multiplication
- Replies:
**59** - Views:
**7217**

### Re: 338 Long multiplication

You have PE because of two things. 1) you print two empty lines instead of one after some test cases. 2) you don't print new line char after the last case, although most problems here ask for 'blank line between consecutive test cases' their outputs on the judge actually require you to print an addi...

- Thu Feb 28, 2008 2:24 am
- Forum: Algorithms
- Topic: Path Counting in Special Graph
- Replies:
**0** - Views:
**1093**

### Path Counting in Special Graph

Hello, I have a practical graph problem (I need to use it my job) for a special kind of graph. I am doing a research on this, I need to know how feasible it is (given the current computational power we have in our days). Let's say we a have some directed graph having about 400 nodes in total. Let's ...

- Sun Feb 10, 2008 3:50 pm
- Forum: Volume 113 (11300-11399)
- Topic: 11353 - A Different Kind of Sorting
- Replies:
**17** - Views:
**7535**

### solved it

OK, seems I had almost done it (solved it) by the time I have made my previous post. So you may ignore it, as I have it ACC now with a runtime of about 1/2 second (0.460 secs). Still, I make one assumption up-front which I don't like very much, although everyone can check up-front that this assumpti...

- Sun Feb 10, 2008 2:30 pm
- Forum: Volume 113 (11300-11399)
- Topic: 11353 - A Different Kind of Sorting
- Replies:
**17** - Views:
**7535**

### some thoughts

Although I know what RC's problem is, I myself still cannot figure out a way to generate the numbers in the right order. What is my idea? Well, firstly let's suppose we know all the primes up to 2,000,000. Generating them is an easy task. Secondly, let's suppose we know all the numbers in the set S[...

- Sat Feb 09, 2008 5:51 pm
- Forum: Volume 113 (11300-11399)
- Topic: 11353 - A Different Kind of Sorting
- Replies:
**17** - Views:
**7535**

RC, your program doesn't generate the numbers in the right order. Your program stores the following data ( after the precalculation step): array[148935] = 4 array[148936] = 6 array[148937] = 10 array[148938] = 14 Where is number 9 ? It should come before 10. That's because 9 is smaller than 10 altho...

- Wed Dec 19, 2007 5:57 pm
- Forum: Volume 113 (11300-11399)
- Topic: 11307 - Alternative Arborescence
- Replies:
**22** - Views:
**10881**

Hello all, I have implemented the algorithm described in the OCCP article by Leo G. Kroon, Arunabha Sen, Haiyong Deng and Asim Roy. Check this link (it's a PostScript file): http://www.public.asu.edu/~halla/papers/OCCPWG96.ps I have tested it with several test cases (simple ones) and the answers see...

- Wed Dec 19, 2007 4:55 pm
- Forum: FAQ
- Topic: Firefox hints
- Replies:
**0** - Views:
**4572**

### Firefox hints

Here are several firefox hints for using the new judge site. 1) Accept Cookies from the new site of the judge. 2) Type in the browser address bar (where you normally type URLs) the following: about:config 3) Then find the property named network.http.redirection-limit 4) Set it to some large value fo...

- Fri Sep 14, 2007 3:48 pm
- Forum: Volume 112 (11200-11299)
- Topic: 11260 - Odd Root Sum
- Replies:
**22** - Views:
**11330**

I finally got accepted. I had a bug in my code which was only showing up for numbers of the form (2*N) ^ 2 i.e. for squares of even numbers. For example for 64 my program was giving answer : 164 which is clearly wrong. The right answer is 156. For 16 my answer was wrong - it was answering : 22, the ...