Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Programming challenges
Index -> General Programming
Goto page 1, 2  Next
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
wtd




PostPosted: Tue Aug 24, 2004 5:15 pm   Post subject: Programming challenges

The "Hello world" thread in Spam, which I shamelessly took over, got me thinking about doing more such threads.

The basic idea is:


  • Post a clearly described problem.
  • Others come in and solve the problem in their programming language of choice.


Guidelines:


  • Problems should not involve graphical elements. This is merely to ensure that all languages (some of which don't have integrated solutions for graphics) are on a roughly equal playing field. Also, the majority of the program should involve solving the problem, not manipulating pixels.
  • Each member is allowed to submit a maximum of one solution in Turing, C++, or Java, due to the popularity of these languages.
  • Each member should only submit a maximum of two solutions per day.
  • Submitted solutions should adhere to standard naming conventions for the language they're written in.
  • It's not a contest. There's no best answer. The goal is simply to see both how others would solve the same problem in the same language, and how the problem is solved in other programming languages.
  • Solutions should be tested before being submitted. Members posting problems can specify multiple sets of input to the program and the matching correct output for testing purposes.


Thoughts? Smile
Sponsor
Sponsor
Sponsor
sponsor
bugzpodder




PostPosted: Wed Aug 25, 2004 9:30 am   Post subject: (No subject)

i dont think many ppl are interested in this... btw clearify if hte problems should be algorithmic in nature... if not what should be the problems like
Tony




PostPosted: Wed Aug 25, 2004 3:32 pm   Post subject: (No subject)

bugzpodder wrote:
if not what should be the problems like


I think wtd ment no visualization type of problems. Though those tend to be much more fun since you can visually enchance your results rether than spitting out same sets of numbers as everybody else, but you achieved the result in say ruby rether than turing Confused

point is - there needs to be a goal to be reached (nicest animation), or a limitation (in # of lines... that was fun) or anything that is tangeble (fastest execution) to compare the entries. Something as a driving force to make you program and show that you're better than everybody else is (untill catalyst submits his entry Laughing )
Latest from compsci.ca/blog: Tony's programming blog. DWITE - a programming contest.
wtd




PostPosted: Wed Aug 25, 2004 5:14 pm   Post subject: (No subject)

bugzpodder wrote:
i dont think many ppl are interested in this... btw clearify if hte problems should be algorithmic in nature... if not what should be the problems like


Well, the problems can be "real world" things, but they should lean toward algorithmic.

Real software is layered. You use one set of code, for instance, to determine what moves characters should make, and another to draw those movements. The two shouldn't be mixed.

I think that the emphasis here has typically been on the latter, at the expense of the former, and that concentrating on the algorithms, rather than just manipulating pixels would be a good thing. Smile
Martin




PostPosted: Thu Aug 26, 2004 12:20 pm   Post subject: (No subject)

Okay, here's a warmup. The Barn Door problem, stolen from USACO.

It was a dark and stormy night that ripped the roof and gates off the stalls that hold Farmer John's cows. Happily, many of the cows were on vacation, so the barn was not completely full.

The cows spend the night in stalls that are arranged adjacent to each other in a long line. Some stalls have cows in them; some do not. All stalls are the same width.

Farmer John must quickly erect new boards in front of the stalls, since the doors were lost. His new lumber supplier will supply him boards of any length he wishes, but the supplier can only deliver a small number of total boards. Farmer John wishes to minimize the total length of the boards he must purchase.

Given M (1 <= M <= 50), the maximum number of boards that can be purchased; S (1 <= S <= 200), the total number of stalls; C (1 <= C <= S) the number of cows in the stalls, and the C occupied stall numbers (1 <= stall_number <= S), calculate the minimum number of stalls that must be blocked in order to block all the stalls that have cows in them.

Print your answer as the total number of stalls blocked.
Martin




PostPosted: Fri Aug 27, 2004 11:54 am   Post subject: (No subject)

Here's a hint: sort the gaps.
wtd




PostPosted: Fri Aug 27, 2004 3:02 pm   Post subject: (No subject)

Maybe I'm just stupid, but there doesn't seem to be nearly enough info. How wide is a stall? How many stalls can a board block up? How many cows were in the barn at the time?
Martin




PostPosted: Fri Aug 27, 2004 5:48 pm   Post subject: (No subject)

It's all there.

The stalls are all the same width.

The lumber supplier can deliver any length of boards, but can only deliver so many boards (given by the specific case).

So, if the farmer could have two boards, they could be any length (1 stall to all of the stalls) but he could only have two boards. They don't have to be the same length.
Sponsor
Sponsor
Sponsor
sponsor
Martin




PostPosted: Fri Aug 27, 2004 5:50 pm   Post subject: (No subject)

Input is formatted like so:
Line 1: M, S, and C (space separated)
Lines 2-C+1: Each line contains one integer, the number of an occupied stall.

Here is a sample input.

4 50 18
3
4
6
8
14
15
16
17
21
25
26
27
30
31
40
41
42
43

And the respective output: 25
One minimum arrangement is one board covering stalls 3-8, one covering 14-21, one covering 25-31, and one covering 40-43.
wtd




PostPosted: Fri Aug 27, 2004 6:23 pm   Post subject: (No subject)

Ok... it was a bit confusing as the problem didn't explicitly state the input. Smile
bugzpodder




PostPosted: Sat Aug 28, 2004 10:52 am   Post subject: (No subject)

its called Barn Repair, not Barn Doors :S

there are thousands of algorithm problems on the net
if you want you can just go do and submit them

i am at USACO 4.1 if you want i can post some problems from there (or harder ones if you wish) but i seriously doubt anyone would even bother to look at them, not to mention attempt it... thats why i dont like the idea of algorithms
Martin




PostPosted: Sat Aug 28, 2004 7:07 pm   Post subject: (No subject)

I'm in 2.1

I haven't done it in forever though Sad
Martin




PostPosted: Sun Aug 29, 2004 2:08 am   Post subject: (No subject)

Could you post some of the later section 2 ones please? I'd do them Smile
bugzpodder




PostPosted: Sun Aug 29, 2004 10:58 am   Post subject: (No subject)

i bet you are stuck on Closed Fences, which is a b*tch... i dont see you why have to stick to USACO

try acm.uva.es or www.topcoder.com they both have lots of practice problems and online judge. i try to stay off those questions that require a specific algorithm such is Dijkstra's or Floyd's shortest paths

here is 3 more from section 2:
Quote:
Stringsobits
Kim Schrijvers
Consider an ordered set S of strings of N (1 <= N <= 31) bits. Bits, of course, are either 0 or 1.

This set of strings is interesting because it is ordered and contains all possible strings of length N that have L (1 <= L <= N) or fewer bits that are `1'.

Your task is to read a number I (1 <= I <= sizeof(S)) from the input and print the Ith element of the ordered set for N bits with no more than L bits that are `1'.

PROGRAM NAME: kimbits
INPUT FORMAT
A single line with three space separated integers: N, L, and I.
SAMPLE INPUT (file kimbits.in)
5 3 19

OUTPUT FORMAT
A single line containing the integer that represents the Ith element from the order set, as described.
SAMPLE OUTPUT (file kimbits.out)
10011


Quote:

Money Systems

The cows have not only created their own government but they have chosen to create their own money system. In their own rebellious way, they are curious about values of coinage. Traditionally, coins come in values like 1, 5, 10, 20 or 25, 50, and 100 units, sometimes with a 2 unit coin thrown in for good measure.

The cows want to know how many different ways it is possible to dispense a certain amount of money using various coin systems. For instance, using a system of {1, 2, 5, 10, ...} it is possible to create 18 units several different ways, including: 18x1, 9x2, 8x2+2x1, 3x5+2+1, and many others.

Write a program to compute how many ways to construct a given amount of money using supplied coinage. It is guaranteed that the total will fit into both a signed long long (C/C++) and Int64 (Free Pascal).

PROGRAM NAME: money
INPUT FORMAT
The number of coins in the system is V (1 <= V <= 25).

The amount money to construct is N (1 <= N <= 10,000). Line 1: Two integers, V and N
Lines 2..: V integers that represent the available coins (no particular number of integers per line)


SAMPLE INPUT (file money.in)
3 10
1 2 5

OUTPUT FORMAT
A single line containing the total number of ways to construct N money units using V coins.
SAMPLE OUTPUT (file money.out)
10


haha, try an IOI problem Smile
Quote:

Sorting a Three-Valued Sequence
IOI'96 - Day 2
Sorting is one of the most frequently performed computational tasks. Consider the special sorting problem in which the records to be sorted have at most three different key values. This happens for instance when we sort medalists of a competition according to medal value, that is, gold medalists come first, followed by silver, and bronze medalists come last.

In this task the possible key values are the integers 1, 2 and 3. The required sorting order is non-decreasing. However, sorting has to be accomplished by a sequence of exchange operations. An exchange operation, defined by two position numbers p and q, exchanges the elements in positions p and q.

You are given a sequence of key values. Write a program that computes the minimal number of exchange operations that are necessary to make the sequence sorted.

PROGRAM NAME: sort3
INPUT FORMAT
Line 1: N (1 <= N <= 1000), the number of records to be sorted
Lines 2-N+1: A single integer from the set {1, 2, 3}

SAMPLE INPUT (file sort3.in)
9
2
2
1
3
3
3
2
3
1

OUTPUT FORMAT
A single line containing the number of exchanges required
SAMPLE OUTPUT (file sort3.out)
4

Martin




PostPosted: Sun Aug 29, 2004 12:38 pm   Post subject: (No subject)

I'm not getting the IOI one.

They just want you to sort the list in the least number of moves, and give them that number?
Display posts from previous:   
   Index -> General Programming
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 2  [ 23 Posts ]
Goto page 1, 2  Next
Jump to:   


Style:  
Search: