## Search found 27 matches

Fri Mar 04, 2005 11:26 pm
Forum: Algorithms
Topic: USACO help again
Replies: 5
Views: 2014
I think you used the algorithm I suggested ^_^ I just posted to say this: let be bincoeff(n,k) the binomial coefficient of n elements of class k, we have: bincoeff(n,0) = 1 bincoeff(n,n) = 1 otherwise: bincoeff(n,k) = bincoeff(n-1,k-1) + bincoeff(n-1,k) Don't use factorials, just use DP! Goodbye Ale...
Fri Mar 04, 2005 11:15 pm
Forum: Algorithms
Topic: Help with this problem
Replies: 2
Views: 1131
I solved Clocks (IOI 1994) and it's easily solvable with a breadth-first search (imagine every configuration is a node and every move is an edge). Otherwise, because there are only 4^9 possible configurations, do exaustive search.

Ciao
Ale
Fri Mar 04, 2005 11:07 pm
Forum: Algorithms
Topic: something strange with 8 queen problem
Replies: 4
Views: 1516
This kind of errors are born when you forget to reset some variable. I didn't read the code (I'm tired now ^_^) but try to check for it. But excuse me, can't you write plainer code? I think it's not a good habit to merge two loop in one. *Almost* all the problems I did were straightforward to write,...
Tue Sep 28, 2004 11:57 pm
Forum: Algorithms
Topic: Index Trees
Replies: 2
Views: 1248
Excuse me if this reply is very late; last moths I had things to do and I didn't visited the forum. An Index Tree is a binary tree with every node "controlling" a certain interval, and its children control the two halves of the interval. Example: a node controls interval [1,1000], its left son contr...
Mon Aug 30, 2004 12:07 am
Forum: Algorithms
Topic: For someone who solved Character Recognition (USACO 5.5)
Replies: 1
Views: 1153

### For someone who solved Character Recognition (USACO 5.5)

I'd like to know if some poster has solved this problem - it's a IOI 1997 problem, but the USACO contains an harder version in Section 5.5. I can't find the error in my program. It produces the following output for test case 9: rincewind could scream for help in thirty four la?guages where the corre...
Tue Aug 10, 2004 12:48 am
Forum: Algorithms
Topic: Cycles on graphs
Replies: 2
Views: 1127
Oh, yes... For my high school final exam I presented a work about NP-completeness, and now I remember Hamiltonian cycle is NP-complete of course!

F**k (the problem, not you Larry )
Mon Aug 09, 2004 9:44 pm
Forum: Algorithms
Topic: Cycles on graphs
Replies: 2
Views: 1127

### Cycles on graphs

I propose you a problem about cycles on graphs. Given an undirected unweighted graph and two nodes A and B, I've got to find a path from A to B and then a path from B to A. I can't visit a node more than once (with the exception of node A, that must be visited at the beginning and at the end). I hav...
Wed Aug 04, 2004 1:36 am
Forum: Algorithms
Replies: 3
Views: 1793
Wow, I got it right! Just see the "Network Flow" text at the USACO training program... Near the end you can find the "sample problems", and there is Telecowmunication, with the method I described! Can you do me a favor, for gratitude ? :) How can I solve "All Latin Squares", section 5.1 ? You're at ...
Wed Aug 04, 2004 1:27 am
Forum: Algorithms
Replies: 3
Views: 1793
Maybe I'm completely wrong, now I write my first ideas...

1. Assign edges the weight INFINITY
2. Double the nodes and connect them with a ghost-edge of weight 1
3. Find minimum cut (running maximum flow)

Don't bother me if I'm saying a stupid thing, now I'm tired!
Fri Jul 30, 2004 10:00 pm
Forum: Algorithms
Topic: prime numbers
Replies: 2
Views: 1269
For large numbers you can use probabilistic primality testing. This test give result with a certain % of probability to be correct, but with "small" numbers (with less of 500 ciphers, and such numbers aren't big for numbers theorists) it's OK. But I don't know where you can see the probabilistic pri...
Fri Jul 30, 2004 12:23 am
Forum: Algorithms
Topic: Segmentation Fault
Replies: 6
Views: 1667
Simple solution: throw Windows out of the window and install Linux! I used Windows for years, now I think a true programmer can't bear with its lack of trasparence. Linux is full of instruments and utilities for a programmer. I just use gcc/gdb/gprof from the shell... (Sorry if I made some mistakes ...
Wed Jul 28, 2004 1:49 pm
Forum: Algorithms
Topic: Cowcycles... A VERY hard problem!
Replies: 4
Views: 2313
I understand it's a backtracking search, but I just can't see how to prune the search...

Can you give me some advice?
Sun Jul 25, 2004 10:59 am
Forum: Algorithms
Topic: Cowcycles... A VERY hard problem!
Replies: 4
Views: 2313

### Cowcycles... A VERY hard problem!

Can someone help me about this problem? I found it at the USACO website in section 4.3. Don't be afraid from the lenght of the statement of the problem, the second half is a little bit of explanation. Thanks a lot. ********** Cowcycles Originally by Don Gillies [International readers should note tha...
Sun Jun 27, 2004 9:05 pm
Forum: Other words
Topic: Newcomer problems
Replies: 15
Views: 13949

### Re: Newcomer problems

I heard about adhoc problems,, but how do i know when a problem belong to this category ?? All programming contests problems can be reduced to a few types of problems, mainly: Dynamic Programming Greedy Complete Search Flood Fill Shortest Path Recursive Search Techniques Minimum Spanning Tree Knaps...
Sun Jun 27, 2004 8:59 pm
Forum: Other words
Topic: how to handle large numbers
Replies: 2
Views: 1144
These numbers are also called BigNums. You must implement the operations all by yourself: for further information see "Programming Challenges" by Skiena-Revilla, chapter 5.