How to get an answer to your question - Algorithms Discussion Boards

Apologies for the shouting but this is important.

When answering a question please:

Read the question carefully
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar
If a question is poorly phrased then either ask for clarification, ignore it, or mark it down. Insults are not welcome
If the question is inappropriate then click the 'vote to remove message' button

Insults, slap-downs and sarcasm aren't welcome. Let's work to help developers, not make them feel stupid.

cheers,
Chris Maunder

The Code Project Co-founder
Microsoft C++ MVP

For those new to message boards please try to follow a few simple rules when posting your question.

Choose the correct forum for your message. Posting a VB.NET question in the C++ forum will end in tears.
Be specific! Don't ask "can someone send me the code to create an application that does 'X'. Pinpoint exactly what it is you need help with.
Keep the subject line brief, but descriptive. eg "File Serialization problem"
Keep the question as brief as possible. If you have to include code, include the smallest snippet of code you can.
Be careful when including code that you haven't made a typo. Typing mistakes can become the focal point instead of the actual question you asked.
Do not remove or empty a message if others have replied. Keep the thread intact and available for others to search and read. If your problem was answered then edit your message and add "[Solved]" to the subject line of the original post, and cast an approval vote to the one or several answers that really helped you.
If you are posting source code with your question, place it inside <pre></pre> tags. We advise you also check the "Encode "<" (and other HTML) characters when pasting" checkbox before pasting anything inside the PRE block, and make sure "Use HTML in this post" check box is checked.
Be courteous and DON'T SHOUT. Everyone here helps because they enjoy helping others, not because it's their job.
Please do not post links to your question into an unrelated forum such as the lounge. It will be deleted. Likewise, do not post the same question in more than one forum.
Do not be abusive, offensive, inappropriate or harass anyone on the boards. Doing so will get you kicked off and banned. Play nice.
If you have a school or university assignment, assume that your teacher or lecturer is also reading these forums.
No advertising or soliciting.
We reserve the right to move your posts to a more appropriate forum or to delete anything deemed inappropriate or illegal.

cheers,
Chris Maunder

The Code Project Co-founder

Microsoft C++ MVP

T(n)=c if n=1
=2T(n-1)+d if n>1

Find the value of T(n) and thus the time complexity.

My attempt at it got stuck.

T(n)=4T(n-2)+3d
T(n)=8T(n-3)+7d
..
..
..
T(n)=8T(n-k)+7d

It can't be solved further.

Quote:
It can't be solved further

This does not help us in any way or format, why can it not be solved further, did it freeze, were there an error etc. etc.

Start writing things out more fully then look for the pattern in terms of n .

T(1) = c

T(2) = 2T(1) + d
T(2) = 2c + d   -------- take this
			           |
T(3) = 2T(2) + d	   |
			           |
           ____________| and put it here
           |
        /------\
T(3) = 2(2c + d) + d
T(3) = 4c + 2d + d
T(3) = 4c + 3d

T(4) = 2T(3) + d
T(4) = 2(4c + 3d) + d
T(4) = 8c + 6d + d
T(4) = 8c + 7d

T(5) = 2T(4) + d
T(5) = 2(8c + 7d) + d
T(5) = 16c + 14d + d
T(5) = 16c + 15d

"the debugger doesn't tell me anything because this code compiles just fine" - random QA comment
"Facebook is where you tell lies to your friends. Twitter is where you tell the truth to strangers." - chriselst
"I don't drink any more... then again, I don't drink any less." - Mike Mullikins uncle

Googling suggests that time complexity requires 'code'. So as a starting point doesn't one need to write the recursive function first?

A colleague has asked for assistance with the problem stated below. I have searched and tried to create a solution without success. Another colleague suggested I post on this forum. The preferred approach would be in msAccess/vba, but any advice appreciated.

The problem:
Given a set of N participants, divide the participants into teams of m members. There are a number of Activities that take place in Sessions. Assign Teams to each session*activity such that no participant/member is assigned more than once in session, and no participant/member is in same activity more than once. Each team can only participate in 1 activity.

For testing suppose there a 4 activities that occur in 4 sessions, and 8 participants in teams of 2.Is there an algorithmic solution for 4x4 and 2. The underlying question is--is there a scalable solution beyond 4x4 and 2?

Manually, with 8 participants A,B,C,D,E,F,G,H - there is a solution

......... Activities
.........  1  2  3  4
Session 1 AE-CF-DG-BH
Session 2 CG-AH-BE-DF
Session 3 DH-BG-AF-CE
Session 4 BF-DE-CH-AG

modified 3-Nov-23 11:34am.

Reminds of some companies: send you on courses you don't need to fulfill the "educational quota". May as well be talking colored marbles.

"Before entering on an understanding, I have meditated for a long time, and have foreseen what might happen. It is not genius which reveals to me suddenly, secretly, what I have to say or to do in a circumstance unexpected by other people; it is reflection, it is meditation." - Napoleon I

So, you want us to do your homework for you; sorry, that's not what this site is for. And looking at your profile you have been a member long enough to know that.

I'm not asking for you or anyone to do homework. My interest is really whether this is a problem that fits a "family of problem types with an algorithmic solution". I have seen picking marbles etc and how many ways can you do X, but I found this particular problem more complex. Any advice as to how to approach the problem would be helpful.
I do recognize there are 16 teams (4x4) in a solution and that with 8 participants, there are 28 unique teams. But it's not just selecting 16 out of 28.

You have all the information you need in the question. It even provides you with sample data to work out first (4x4 and 2). S otry to draw some diagrams to see how you can fit the respective teams into the different activitie, and if there is a common thread to get to the answer.

Hello!
I need to implement an algorithm to create round-robin tournament schedules, but with the constraint that up to 2 teams – that may play in different leagues – might share the same field on the same time slot of the week, so they must be never be scheduled to play at their home field in the same round of their league schedule.

Simple example:

leagueA = [
  TeamA(plays at FieldA on Sunday),
  TeamB(plays at FieldB on Sunday),
  TeamC(plays at FieldA on Saturday),
  TeamD(plays at FieldD on Saturday)
]
leagueB = [
  TeamE(plays at FieldA on Sunday),
  TeamF(plays at FieldF on Sunday),
  TeamG(plays at FieldG on Saturday),
  TeamH(plays at FieldF on Saturday)
]

I was thinking of generating the schedule for leagueA with the circle algorithm alternating home and away at each round as described in the linked article, and then to approach the scheduling for leagueB by prefilling the slots for the teams that share the field with teams in the other league somehow, but I'm not sure whether it's the right approach and how to actually implement it in a way that is guaranteed to produce schedules do not produce conflicts.

Any help would be highly appreciated!

Sounds like a "static" schedule; which you imply by ignoring winners and losers; so any feasible schedule you generate, first time out, will do. (And "schedules" doesn't come into it).

"Before entering on an understanding, I have meditated for a long time, and have foreseen what might happen. It is not genius which reveals to me suddenly, secretly, what I have to say or to do in a circumstance unexpected by other people; it is reflection, it is meditation." - Napoleon I

Recently, I joined a programming competition and stumble across a question that i consider difficult to answer because I cant even fully understand the problems given, to me this is the hardest question in the competition.
The problem goes like this :

You are given an integer k>0 and a series of k+2 numbers n[1], n[2], …, n[k+2]. You are told
that the numbers in the series are calculated using an equation of the following form for n>0:
n[x] = ((x + a[1]) * (x + a[2]) * (x + a[3]) ... (x + a[k])) / d

You do not know the value of d. You do not know the values for a[1] ... a[k]. You only know
that each (a[i] ≥ 0) and (d > 0) and you can assume that the product in the numerator is evenly
divisible by the integer value d. You can assume that the numerator can be represented by a
32-bit integer. But you know that the formula for n[x] is a polynomial function of degree k and
you know the value of k+2 points for this function. Based on this information, you actually have
enough information to calculate the next number n[k+3] in the sequence! This is your task.
Input
The first line will contain a single positive integer by itself that represents the value k. The
second line will consist of (k+2) integer values separated from each other by a single space.
The values on the second line represent the series n[1] through n[k+2].
The input must be read from standard input.
Output
The output of program should display a single integer on a line by itself representing the value
for n[k+3].
The output must be written to standard output.

Sample Input #1
First Line : 1
Second Line : 3 4 5

Output : 6

Sample Input #2
First Line : 2
Second Line : 1 3 6 10

Output : 15

I dont even understand why this problem is solvable when there is an unknown variable(d) and another function in the sequence(a[x]) and how to get the value of n(k+3)

It's Algebra and Dynamic Programming; converging on a number. (I go blank after x number of words; so it's just a thought).

"Before entering on an understanding, I have meditated for a long time, and have foreseen what might happen. It is not genius which reveals to me suddenly, secretly, what I have to say or to do in a circumstance unexpected by other people; it is reflection, it is meditation." - Napoleon I

There is a bit of extra information in the problem. Maybe they didn't count well the number of equations and unknowns. You have k+1 unknowns (a[1],...a[k] and d) and k+2 equations. We can take only the first k+1 equations and leave the last one for verification. Here is the math:

We can write n[x] as a polynomial with unknown coefficients c[1] to c[k]:

n[x]=x^k + c[1]*x^(k-1)+c[2]*x^(k-2)...+c[k]

We know the values of this polynomial in each of the points 1, 2,...k+1 so we can write the following system of k+1 equations:

1^k + 1^(k-1)*c[1]+...+c[k] = n[1]*d
2^k + 2^(k-1)*c[1]+...+c[k] = n[2]*d
....
k^k + k^(k-1)*c[1]+...+c[k] = n[k]*d
(k+1)^k + (k+1)^(k-1)*c[1]+...+c[k] = n[k+1]*d

Reordering terms, this gives:

-n[1]*d + 1^(k-1)*c[1]+...+c[k] = -1^k
-n[2]*d + 2^(k-1)*c[1]+...+c[k] = -2^k
....
-n[k]*d + k^(k-1)*c[1]+...+c[k] = -k^k
-n[k+1]*d + (k+1)^(k-1)*c[1]+...+c[k] = -(k+1)^k

This is a system of k+1 equations with k+1 unknown that can be solved:

| d  |
|c[1]|
|... | = M^-1 * V
|c[k]|

where M is the coefficients matrix:

-n[1]     1^(k-1) ... 1
-n[2]     2^(k-1) ... 1
...
-n[k+1] (k+1)^(k-1)...1

and V is the free terms vector:

-1^k
-2^k
...
-(k+1)^k

After you've calculated the coefficients finding the value of the polynomial is trivial.

Here is a numerical example for the case k=2

   |-1 1 1 |    |-1|
M= |-4 2 1 | V= |-4|
   |-6 3 1 |    |-9|

after calculating the inverse of M, the end result is d=2 c[1] = 1 c[2] = 0 and the polynomial is n[x] = x^2+ 1*x + 0. n[4]/2 = (16+4)/2 = 10 (matching the extra equation given) and n[5]/2 = (25+5)=15 matching the suggested answer.

Mircea

Why can we rewrite the original equation into this?

n[x]=x^k + c[1]*x^(k-1)+c[2]*x^(k-2)...+c[k]

Where does 'd' goes, Why does x^k until x^(k-k) and why replace a(x) with c(x). Sorry for the inconveniences, I just dont understand.

If you look at the original expression for n(x), you see that each of the values -a[i] is a root of the polynomial (because the term x+a[i] becomes 0). Now, a polynomial with k roots must be a polynomial of degree k, hence we can write it in the form n(x)= x^k + c[1]*x^(k-1) + … c[k]. Moreover, coefficients c[i] are related to roots -a[i] through Vieta's formulas - Wikipedia[^].

Looking at the original assignment, I see that I should have called the polynomial “n1(x)” and say that n(x) = n1(x)/d, or equivalent, n1(x)=n(x)*d. It doesn’t make much difference as we get to the system of equations:

n[1]*d = 1^k + 1^(k-1)*c[1]+… +c[k]
n[2]*d = 2^k + 2^(k-1)*c[2]+… +c[k]
. . .

this is the system of (k+1) equations that needs to be solved to find the values of d, c[1],… c[k]

Mircea

You've been given "2 answers" in the original "question" (assuming it's not a "trick"); including inputs. You can perform 2 direct substitutions to start "converging" on the answer through insight gained.

"Before entering on an understanding, I have meditated for a long time, and have foreseen what might happen. It is not genius which reveals to me suddenly, secretly, what I have to say or to do in a circumstance unexpected by other people; it is reflection, it is meditation." - Napoleon I

The problem in a RTS is that you can move in a limited number of directions. A RTS is not a First Person Shooter or a physics engine, if you collide in a RTS the only options are keep going forward or go back where you came from until you reach the your last path node. Once there you have more options (but still limited to only several directions). For instance if two units move towards the same node, one heading West and the other heading South, South West or South East, I think the unit moving South Something should stop or go back while the other one should keep going.
If two units A and B collide head on you can use the rule “use the right lane”, I tried that it works. However if a third unit already uses what is “the right lane” of unit A, unit A will have nowhere to go. How do you proceed in a situation like this?

If the "nodes" are pixels, it's not a problem ... you have a lot more "nodes" to work with. "The limited number of directions" are what you imposed; it's not a "feature" of RTS per se.

(My units can "slide" around an object, if I let them; much like walking with one hand on a wall)

"Before entering on an understanding, I have meditated for a long time, and have foreseen what might happen. It is not genius which reveals to me suddenly, secretly, what I have to say or to do in a circumstance unexpected by other people; it is reflection, it is meditation." - Napoleon I

>you have a lot more nodes to work with

I think center of a tile or pixel is a question of resolution.

Handling collisions in an RTS is tricky. Use smart pathfinding algorithms like A*, and consider dynamic obstacle avoidance. When collisions happen, prioritize units based on criteria like size or speed. Also, think about predicting collisions and adjusting paths ahead of time. And hey, allowing players to set waypoints can give them more control. It's a bit like orchestrating a dance – you want your units to move smoothly and avoid stepping on each other's toes! 🕺💃

Please stop reposting the same question in multiple places. You already have some feedback in your previous post below. If you have some questions or comments then reply to the people posting the feedback.

Plus, he already knows the answer; he's only posting to test whether we're as "smart" as him. D'Oh! | :doh:

Apparently, he's notorious on other forums as a troll:
Notorious computer science troll, Pete Olcott[^]

"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer