|
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. 
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
|
|
|
|
|
He reminds me of the Grans Negus and his "plain english" bullshit.
|
|
|
|
|
That's because your reputation precedes you.
You don't really discuss. You evaluate the people who respond to you and either discard them, ignore them, or "collect" them, kind of like sports trading cards.
|
|
|
|
|
You're still focused on "the question". At this point, it's irrelevant.
We're focused on YOU and how you treat people. That's why I said your reputation precedes you. Your behavior and treatment of people on other sites killed any discussion you possibly had, and the same is happening here.
Have a nice life.
|
|
|
|
|
A singular point of view. It's easy to go look you up on other sites and read through the threads.
|
|
|
|
|
And you're doing it again. You're using your question as a distraction to prevent you from looking at yourself.
|
|
|
|
|
I already have and I'm not the only one to point this stuff out to you. It's been done on other forums.
|
|
|
|
|
polcott wrote: that I must be wrong without looking at what I actually said
If someone claims that they can prove the sum of angles is not 180 degrees then I am not going to look at what they said.
If someone claims that they have a lossless compression method that can reduce anything down to a couple of bytes I am not going to look at what they said (I have actually seen a claim like that in a forum.)
If someone claims that the world is flat I am not going to look at what they said (I have read articles refuting such claims.)
I do not do that because I have taken the actual educational classes that demonstrate that those claims are false. I actually either did the proofs myself as part of class work or at least did a step by step analysis of the proofs and understood those proofs.
So I do not need to attempt to validate claims by others that they are wrong.
But I already pointed out that if you can prove your contention then write it up and submit it to a real scientific journal.
I also pointed out that if you can do that then there will be significant benefits to you personally by doing so.
So given that then why are you not busy writing up the article?
|
|
|
|
|
polcott wrote: Two people each with masters degrees in computer science
And a heart surgeon promotes homeopathic remedies. So thus those must work?
polcott wrote: He has also agreed that I can quote him on this.
If you are already convinced then why are you posting here?
|
|
|
|
|
polcott wrote: This is the 12th article
I don't care.
There are probably thousands of articles promoting cow urine as a cure for cancer and MBA's in India are presumably producing papers all the time on Astrology since that is a degree program in multiple universities.
What I said was that you should get published in a formal mathematics journal. At a minimal such a journal must not be 'pay per publish'.
|
|
|
|
|
It's a bot.
"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
|
|
|
|
|
Probably because of your attitude and behaviour.
|
|
|
|
|
"For those who code" and do not simply pontificate.
"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
|
|
|
|
|
Please go back to whatever theoretical cave you crawled out of.
I'll stick to the more practical problems today, thank you.
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
