Competition problems

[ETAkoG1T]

Hello I participated in a c++ competition a while ago. I tried my best solving them and got a mediocre score. I never found out how they were done and it has been annoying me ever since. Can someone find a solution and share it with me so I can learn something from the experience?
http://orac.amt.edu.au/cgi-bin/train/problem.pl?set=aio13int&problemid=688
http://orac.amt.edu.au/cgi-bin/train/problem.pl?set=aio13int&problemid=689
http://orac.amt.edu.au/cgi-bin/train/problem.pl?set=aio13int&problemid=690

What I found interesting is that I got a decent score for the first problem, but didn't understand it. The other two problems on the other hand I understood better what I needed to do, but got a worse score.

[ne555]

archery:
worst case: utter defeat. People that won you one day, would be above you in the final ranking.
best case: just for a nose. You manage to recover, you are below that minuscule group that manage to defeat you in both days.


frogs:
compute the best course using the post `k' in the middle.
Then simply compute the maximum over that.

the left and the right post to use with `k' would be `min(begin, k)' and `min(k,end)'
By doing in an incremental way, you can achieve an overall O(n) algorithm, which is optimum.


save-it:
count and modulus
If the price of the article mod 5 is {0,1,2}, then that excedent is free.
You need to count the ones that exceed on 3 or 4.

Adjust the prices to p -= p%5
and sum them all. That would get you a floor, your answer can't be bellow that.

Now consider the 3,4 excedents.
If you buy them by unit, they would cost 5.
If you buy two of `3', that cost 5. (price unit 2.5)
If you buy one 3 and one 4, that cost 5. (price unit 2.5)
If you buy three 4, that cost 10. (price unit 3.33... )

Observe that the combo {3,4} is cheaper than {4,4,4}

[ETAkoG1T]

People that won you one day, would be above you in the final ranking.

What do you mean? You can win over them if for example they had rank 3 day one and you had rank 4 and then you get rank 2 next day and they get rank 3.

[Script Coder]

frogs:
compute the best course using the post `k' in the middle.
Then simply compute the maximum over that.

the left and the right post to use with `k' would be `min(begin, k)' and `min(k,end)'
By doing in an incremental way, you can achieve an overall O(n) algorithm, which is optimum.

How would you get O(n)?
Assuming that you keep track of the min values on either side of k, look at this counter example:
Assume you have the fence as:
3 1 2 5 4 6
And the kth fence is currently the one of height 1. min(0,0)=3 and min(2,5)=2. Now assume you want to increment k. Firstly you would note that 1 is less that your current min on the left side and change min(0,1)=1. But how would you (in linear time) find the min for the right hand side?

I get a fastest algorithm to be O(nlogn).

[ne555]

>> People that won you one day, would be above you in the final ranking.
> What do you mean? You can win over them if for example
worst case.
You can suppose that those that won you, did it in an humiliate way.
Also, in the worst case, you manage no win, at most a tie with all the rest.

Considering that, you cannot overcome the point difference if you were defeated.


> How would you get O(n)?
> Assuming that you keep track of the min values on either side of k
That's because you want to do it all at once, (wink at Duoas)
First calculate the minimum to the left, for all the positions.
Then calculate the minimum to the right, for all the positions.
After that compute the difficulty of each course, and manage the invalids.
Finally, get the highest difficulty.

[Script Coder]

ne555 wrote:

Then calculate the minimum to the right, for all the positions.

How would you do that in linear time?

[ne555]

same way that you would calculate the minimum to the left, except that now you'll traverse in the opposite direction.

the_minimum_to_the_start( v.begin(), v.end(), left.begin() );
the_minimum_to_the_start( v.rbegin(), v.rend(), right.rbegin() );
sum = sum_handling_invalids( left, right );
return max_element( sum );

[Script Coder]

I still do not understand how that works. If you don't mind, will you please provide working code that supports your statement. I am sorry to be such a burden, I am just trying to further my own knowledge.

[ne555]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

#include <vector> #include <iostream> // stores the minimum value in range [start, start+k] in the position output+k template<class inIter, class outIter> void minimum_so_far( inIter begin, inIter end, outIter output ){ for(inIter min = begin; begin not_eq end; ++begin, ++output){ if( *begin < *min ) min = begin; *output = *min; } } int main(int argc, char **argv){ std::vector<int> values = {7, 3, 3, 2, 6, 1, 0, 3, 9, 7}, left(values.size()), right(values.size()); minimum_so_far( values.begin(), values.end(), left.begin() ); minimum_so_far( values.rbegin(), values.rend(), right.rbegin() ); for( auto x : left ) std::cout << x << ' '; std::cout << '\n'; for( auto x : right ) std::cout << x << ' '; std::cout << '\n'; return 0; }

7 3 3 2 2 1 0 0 0 0 0 0 0 0 0 0 0 3 7 7

rbegin(), rend(), return a `reverse iterator' so it would traverse the container ``backwards''

A more specific alternative

std::vector<int> minimum_to_the_right( const std::vector<int> &values){
	std::vector<int> right( values.size() );

	int min = values.size()-1;
	for(int K = values.size()-1; K >= 0; --K){
		if(values[K]<values[min])
			min = K;
		right[K] = values[min];
	}
	return right;
}

Note that left[K] and right[K] includes the `K' element when considering the minimum.
So the sum (if it is valid), would be height[K]-left[K-1] + height[K]-right[K+1]

edit: well, actually if it is valid left[K]==left[K-1] and right[K]==right[K+1]

[Script Coder]

Thank you so much. I understand completely now.