FP Programmers Algorithmic Problems Thread

[Darwin226]

Hello!

Before I begin, what exactly do I consider 'algorithmic problems'?
It's a type of a programming challenge that doesn't involve making an application. It's not going to do anything useful by itself. The program you write should solve only the given problem in the fastest possible time, using the least amount of memory.
The problems will require more thinking than programming in general and can (should) be solved by using known algorithms.

The goal? Introduce you to the more theoretical and mathsy side of programming.
Introduce you to useful data structures and algorithms that you (most likely) wouldn't be able to think up yourself.

The format I plan to use is
[Problem text] - Don't expect any fancy stories here unless I think that they would explain the problem better
[Hint] - These will be in spoiler tags and will include the names of algorithms you should use to solve the problem or maybe just a note to help you
[Test samples] - These consist of inputs for your program and the correct outputs it should produce. You will be given 2 small samples that you can handwrite in, and 1 sample bordering the limits of input to stress test your program.
[Solution] - A link to a pastebin page that contains a solution to the problem. Naturally there may be other ways to solve it and there probably are. My solutions will most likely be written in C# but anyone with programming experience in C-style languages should be able to understand. I'll try to include as many comments as I can and a short description at the top.

As a sort of a warning to you I have to say this. Most of this algorithms you will not see an implication of in the real world. For example, in a game you would use A* for pathfinding since you don't really care about the shortest possible path and are willing to trade of precision for a speed increase. In these problems you will need to use other algorithms that are designed to give the precise solution.
However, most of the algorithms that you would use in real life are derived from the ones you would use here so they might help you out.

Here we go then.

[B]Problem 1 - Flood fill[/B]

The problem is easy to explain. You will be given a number N.
It will be the dimension of the input square field.
After that you will be given N lines of input, each consisting of N non-separated characters.
Characters will be either '#' or '.'
'#' represents a wall and '.' represents empty space.
Then you will be given 2 numbers, X and Y.
Those are the starting coordinates of the flood fill (starting at 0, not 1, and starting from [0,0] being in the top left corner).
Your task is to write a program that will fill the whole empty area the starting coordinates are in and output the number of "pixels" it has filled including the starting point.
The fill can spread horizontally and vertically but not diagonally.
N will range from 10 to 100 and the starting coordinates will never be in a wall.
The program should finish in under a second.

Hint:
[URL="http://pastebin.com/6WutZcZu"]How do I spoiler?[/URL]

Sample inputs:

==========
IN
5
....#
...#.
..#..
.#...
#....
0 0

OUT
10
==========
IN 
5
.....
..##.
.#..#
.#..#
..##.
2 2

OUT
4
==========
Large sample
[URL]http://pastebin.com/TEnm9Re2[/URL]
==========

The solution:
[URL]http://pastebin.com/wPwXpR2M[/URL]

Have fun and if you have the time, please make some more.

[swift and shift]

[cpp]
#include <cstdlib>
#include <queue>
#include <utility>
using namespace std;

int N, x, y, ans;
char map[102][102];

int main()
{
scanf("%d", &N);
for(int i = 0; i < N; i++) {
scanf("%s", map[i]);
}
scanf("%d %d", &x, &y);
queue<pair<int, int> > q;
q.push(make_pair(x, y));
while(!q.empty()) {
pair<int, int> coords = q.front();
q.pop();
if(map[coords.second][coords.first] != '.') {
continue;
}
ans++;
map[coords.second][coords.first] = '#';
if(coords.second > 0) q.push(make_pair(coords.first, coords.second - 1));
if(coords.second < N - 1) q.push(make_pair(coords.first, coords.second + 1));
if(coords.first > 0) q.push(make_pair(coords.first - 1, coords.second));
if(coords.first < N - 1) q.push(make_pair(coords.first + 1, coords.second));
}
printf("%d\n", ans);
}
[/cpp]

[editline]29th January 2012[/editline]

darwin226, do you do USACO?

[Darwin226]

Well seeing how I'm from Croatia, no I don't. But I'm sure what we do is similar.

In other news, I'll write a new problem now.

[swift and shift]

Mine can handle values of N up to about 3,900 in under a second

[Darwin226]

Oh. Apparently it's worldwide.

[swift and shift]

[QUOTE=Darwin226;34429567]Well seeing how I'm from Croatia, no I don't. But I'm sure what we do is similar.[/quote]

Oh, your flag on the OP says US for some reason.

I do a similar one in Australia called AIO - it's pretty cool

[quote]In other news, I'll write a new problem now.[/QUOTE]

I've got a bunch written up at [url]http://notorac.charlie.bz[/url]. Feel free to steal one.

[editline]29th January 2012[/editline]

we're not having much luck with automerge are we

[Darwin226]

[QUOTE=swift and shift;34429579]Mine can handle values of N up to about 3,900 in under a second[/QUOTE]

Well it should be around O(n^2) since you only visit each pixel once.

[editline]28th January 2012[/editline]

[b]Problem 2 - Mass XOR[/b]

Even simpler that the last one. To explain at least.
Input consists of two numbers, n and m.
Your job is to make a program that will output a number x where x = n XOR (n + 1) XOR (n + 2) XOR ... XOR (m - 2) XOR (m - 1) XOR m
In other word output all the numbers in the [n, m] interval XORed.
1 < n < m < 2^64
Solve in under .5 seconds

Hint:
[URL="http://pastebin.com/Tq8PRxKU"]Still don't know how to spoilers...[/URL]

Sample input:

==========
IN
5 100

OUT
96
==========
IN
24 107

OUT
0
==========
Large sample
IN
1234 1234567890987654

OUT
1234567890983615
==========

Solution:
[url]http://pastebin.com/aJ9hjAKM[/url]

[r0b0tsquid]

We've got a competition for problems like this in the UK as well, it's called the BIO. You should take a look at their website, it's got some pretty nice problems on it.
Here's a cute one from the 2009 final, found on [URL="http://www.olympiad.org.uk/"]their terrible website[/URL]:
[quote=Fair Exchange]It is the holiday season for the spies of Alpha Complex. A time for the giving
of gifts. A time for the receiving of gifts. A time for ensuring your fellow spy does
not receive more than his fair share.

Since secretly giving gifts would feel too much like work, a list has been
published indicating between which spies gifts are to be given. For each pair of
spies on the list, only a single gift is to be given although the list does not indicate
which spy gives and which receives the gift. To keep things fair, the difference
between the total number of gifts a spy receives and gives must be at most 1.
For example, suppose that gifts are to be given between the pairs 1-2, 2-3, 1-3,
3-4 and 1-4. One way of allocating the gifts would be for 1 to give gifts to 2 and 3,
2 to give a gift to 3, 3 to give a gift to 4 and finally 4 to give a gift to 1.

Write a program that determines a fair way of giving the gifts. The first line
of the input will be an integer, n (2 <= n <= 1000) giving the number of spies
(who are numbered from 1 to n). This will be followed by a list of pairs of
spies who are to give gifts, one pair on each line. This list will be terminated
by the line -1 -1. Every spy will be in at least one pair, no pair will be given
twice and each pair will contain two different spies.

You should output a list of pairs, where the first entry in each pair indicates
the spy who is giving the gift and the second indicating the receiving spy.

SAMPLE INPUT
3 7
1 6
2 5
3 4

SAMPLE OUTPUT
0 1
5 7
3 4
[/quote]
They provide sets of test data, which test for progressively more subtle errors - each question is meant to take an hour, so none of them are particularly massive problems. I'd imagine the AIO that turb mentioned runs in a similar vein.

[Darkwater]

[QUOTE=Darwin226;34429604]Still don't know how to spoilers...[/QUOTE]

[sp]sp tag[/sp]

[Darwin226]

I'm thinking about what problem I should write next. I was thinking about something with Djikstra but it's quite similar to the first one so I don't really want to do it.

Anyone got any ideas?

[swift and shift]

[b]Time Limit:[/b] 0.1 seconds

You are to write a program that reads a number i from standard input and writes the ith Fibonacci number modulo 1,024 to standard output.

The sequence begins at i = 1, so fib(1) = 1, fib(2) = 1, and fib(3) = 2.

It is guaranteed that that 1 &#8804; i &#8804; 250,000,000.

[b]Subtasks[/b]

For 33% of the available marks, i will be less than 40.

For 66% of the available marks, i will be less than 10,000,000

[b]Sample Input[/b]
10

[b]Sample Output[/b]
55

[Ziks]

Naïve approach:

[csharp]static void Main( string[] args )
{
int i = int.Parse( Console.ReadLine() );

ushort a = 0;
ushort b = 1;

while ( i-- >= 2 )
{
b += a;
a = (ushort) ( b - a );
b &= 0x03FF;
}

Console.WriteLine( b );
}[/csharp]

Quick 2 minute job because I have a lecture now. I'll think of a more mathsy one in the mean time.

[swift and shift]

[QUOTE=Ziks;34461592]Naïve approach:

[csharp]static void Main( string[] args )
{
int i = int.Parse( Console.ReadLine() );

ushort a = 0;
ushort b = 1;

while ( i-- >= 2 )
{
b += a;
a = (ushort) ( b - a );
b &= 0x03FF;
}

Console.WriteLine( b );
}[/csharp]

Quick 2 minute job because I have a lecture now. I'll think of a more mathsy one in the mean time.[/QUOTE]

that will score 66%

[Darwin226]

[QUOTE=swift and shift;34461600]that will score 66%[/QUOTE]

Would you say that you can figure out the real solution yourself or is it unlikely?
I would guess that there's something about fibonacci numbers and the mod 1024 that let's you skip a bunch.

[swift and shift]

[QUOTE=Darwin226;34461800]Would you say that you can figure out the real solution yourself or is it unlikely?
I would guess that there's something about fibonacci numbers and the mod 1024 that let's you skip a bunch.[/QUOTE]

i've solved it

[editline]31st January 2012[/editline]

there's two very different ways of going about this

[ROBO_DONUT]

I went to Wikipedia to look for a list of Fibonacci numbers, to check for periodicity, and accidentally found the answer. So don't go to Wikipedia.

[Ziks]

[csharp]static void Main( string[] args )
{
int i = int.Parse( Console.ReadLine() );

ushort a = 0;
ushort b = 1;

int p = 0;
while ( --i > 0 )
{
b += a;
a = (ushort) ( b - a );
b &= 0x03FF;

++p;

if ( a == 0 && b == 1 )
i %= p;
}

Console.WriteLine( b );
}[/csharp]

[Darwin226]

[QUOTE=Ziks;34464067][csharp]static void Main( string[] args )
{
int i = int.Parse( Console.ReadLine() );

ushort a = 0;
ushort b = 1;

int p = 0;
while ( --i > 0 )
{
b += a;
a = (ushort) ( b - a );
b &= 0x03FF;

++p;

if ( a == 0 && b == 1 )
i %= p;
}

Console.WriteLine( b );
}[/csharp][/QUOTE]

Nice.
Now that I think of it it makes perfect sense.
There are 1024 possible numbers and 1024 other possible number before the first one in the sequence so there's only 2^20 possible combinations when the top limit goes much higher.

What I was thinking is way more complex. It appears that each bit of the number is also periodical but the pattern grows more and more complex so I couldn't be bothered to find the pattern for the 10th bit...

[DoctorSalt]

Off topic question, but with the A* algorithm, couldn't it find the best solution if your heuristic is good enough?

[ROBO_DONUT]

A*, and (I think) not always. That's basically the definition of a 'heuristic'.

A heuristic gets you a solution that is usually pretty good, but it makes no guarantees. Basically the only heuristic that will get you the best solution is the one that does nothing at all. In which case, A* is exactly Dijkstra's.

[DoctorSalt]

[QUOTE=ROBO_DONUT;34465508]A*, and (I think) not always. That's basically the definition of a 'heuristic'.

A heuristic gets you a solution that is usually pretty good, but it makes no guarantees. Basically the only heuristic that will get you the best solution is the one that does nothing at all. In which case, A* is exactly Dijkstra's.[/QUOTE]
aka Floodfill, right?

EDIT: I see weights as being synonymous with distance.

[Darwin226]

[QUOTE=DoctorSalt;34466000]aka Floodfill, right?[/QUOTE]

No. Floodfill would be more like BFS od DFS. Djikstra works the same, except it works for weighted graphs as well by sorting the links each spread.

[icantread49]

[QUOTE=DoctorSalt;34465480]Off topic question, but with the A* algorithm, couldn't it find the best solution if your heuristic is good enough?[/QUOTE]

yes as long as the heuristic is admissible (i.e. it does not overestimate the distance)

[DoctorSalt]

[QUOTE=icantread49;34466541]yes as long as the heuristic is [B]admissible [/B](i.e. it does not overestimate the distance)[/QUOTE]

Thank you, that was the word I was looking for.

[Darwin226]

I have a good one.

[B]Problem 3 - Party[/B]

So there's this party. N people are attending. The people can know each other in a way that is person A knows person B, person B also knows person A.
When the party starts people start leaving and they do so in the following steps.
First, everyone that doesn't know anyone leaves. Then, everyone who knows only one person (of the ones remaining) leaves. Then everyone who knows 2 people from the ones left leaves.
This goes on until everyone that knows N-1 people of the ones left leaves.
For a given number N, output the maximum amount of people that can be left at the party after all steps of eliminations have been completed.

Hint:
[sp]There's no special algorithm you should know. It will help if you use pen and paper.[/sp]

Sample inputs:

Only one sample. Having more would ruin the problem.
==========
IN
3


OUT
1
==========
Explanation:
There are 4 possible scenarios with 3 people.
1: No one knows anyone.
    It means that they all leave in the first step.
2: They all know each other.
    They all get eliminated in the 3rd step (because each of them knows 2 people)
3: Two of them know each other. Third one doesn't know anyone.
    The third one get eliminated in the first step and the other two in the second.
4: Finally, two of them know the third guy, but not each other.
    The two get eliminated in the second step leaving the third guy with 0 friends left, and since the step where he would get eliminated for that has passed, he stays.

The solution:
[URL]http://pastebin.com/VH5CZLZX[/URL]

[DeadKiller987]

I can't do this one, so hopefully some of you find it hard:
You get a number like 5132 and you need to make it into a valid equation like 5+1=3*2
You can't move the digits around, just add /*-+ and 1 = between them.
Ignore the * and / priority over + and -. This needs to be done simply left to right.

Examples:
2715534
2*7*1+5=5*3+4

12345678987654321
1*2+3*4-5*6-7+8+9=8*7+6-5-4-3*2*1

Good luck. I have no idea how to code the solution and the booklet I got it from doesn't tell me.

[sim642]

[QUOTE=DeadKiller987;34620041]I can't do this one, so hopefully some of you find it hard:
You get a number like 5132 and you need to make it into a valid equation like 5+1=3*2
You can't move the digits around, just add /*-+ and 1 = between them.
Ignore the * and / priority over + and -. This needs to be done simply left to right.

Examples:
2715534
2*7*1+5=5*3+4

12345678987654321
1*2+3*4-5*6-7+8+9=8*7+6-5-4-3*2*1

Good luck. I have no idea how to code the solution and the booklet I got it from doesn't tell me.[/QUOTE]

If you try every possible operator between all pairs of digits there aren't too many different possibilities so it's kind of brute forceable.

[sambooo]

(n-1) * 4^(n-2) possibilities where n is the number of digits, bruteforce is probably feasible for this.

Good luck sim :)

[DeadKiller987]

[QUOTE=sim642;34620181]If you try every possible operator between all pairs of digits there aren't too many different possibilities so it's kind of brute forceable.[/QUOTE]

I forgot to mention this is from a past olimpiade. They have a time limit of 1 second. On a 1.3ghz celeron.

[sim642]

I programmed it in C++: [url]http://ideone.com/clLYA[/url]. There are input samples at the bottom. I made it output all the possible answers, but it's really simple to make it stop after finding first one.